AF: SMALL: Provable Algorithms for Nonhermitian Matrices

AF：SMALL：非埃尔米特矩阵的可证明算法

• 批准号: 2009011
• 负责人: Nikhil Srivastava
• 金额: $ 49.73万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2009011&HistoricalAwards=false
• 关键词: AF; SMALL; Provable; Algorithms; Nonhermitian

Finding the eigenvalues and eigenvectors of a matrix is among the mostfundamental computational tasks. These quantities correspond to resonantfrequencies and modes of physical, statistical, and mathematical systems andappear in essentially every area of science and engineering. First yearcollege students are taught how to compute them on small examples, and two ofthe ``top 10 algorithms of the twentieth century'' --- the QR Algorithm andthe Arnoldi algorithm --- were designed to do so on large instances. When thematrices involved are symmetric, these methods come with provable guaranteesshowing that they are accurate, fast, and correct. However, the generalnon-symmetric case remains poorly understood, and rigorously analyzing thesealgorithms in general has been a decades-old mystery in numerical analysis,despite their being implemented in standard software packages. The main goalof this project is to solve these and related mysteries using modern tools ofrandom-matrix theory and theoretical computer science. Doing so will put alarge branch of computational practice on solid theoretical footing, andideally foster deeper interaction between the numerical analysis, mathematics,and theoretical computer science research communities.Specifically, the project will aim to analyze the two (currently heuristic)algorithms mentioned above, with the following concrete major goals: (1) finda shifting strategy for the shifted QR method which provably converges rapidlyfor every matrix; (2) formalize a widely held belief precisely relating theoutput of the Arnoldi algorithm to the pseudospectrum of the input matrix.Secondarily, the award will study the adjacent problem of efficientlycomputing an approximation of the Jordan normal form of a given rationalmatrix in the variable precision model of computation, for which goodcomplexity bounds are not known. The project will likely use techniques fromrandom-matrix theory, dynamical systems, algebra, and numerical analysis,building on recent progress of the investigator and collaborators in some ofthese areas.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

查找矩阵的特征值和特征向量是最基本的计算任务之一。这些量对应于物理、统计和数学系统的共振频率和模式，并且基本上出现在科学和工程的每个领域。大学一年级学生要学习如何在小实例上计算它们，而“二十世纪十大算法”中的两种——QR 算法和 Arnoldi 算法——就是为了在大型实例上进行计算而设计的。当涉及的矩阵是对称的时，这些方法具有可证明的保证，表明它们是准确、快速和正确的。然而，人们对一般的非对称情况仍然知之甚少，并且严格分析这些算法在数值分析中一直是几十年来的谜团，尽管它们是在标准软件包中实现的。该项目的主要目标是使用随机矩阵理论和理论计算机科学的现代工具来解决这些及相关的谜团。这样做将为计算实践的一大分支奠定坚实的理论基础，并理想地促进数值分析、数学和理论计算机科学研究界之间更深入的互动。具体来说，该项目将旨在分析上述两种（目前为启发式）算法，其具体主要目标如下：（1）为移位 QR 方法找到一种移位策略，该策略可证明对每个矩阵都能快速收敛； (2) 形式化广泛持有的信念，精确地将 Arnoldi 算法的输出与输入矩阵的伪谱相关联。其次，该奖项将研究在可变精度计算模型中有效计算给定有理矩阵的 Jordan 范式近似值的邻接问题，而该模型的复杂性界限尚不清楚。 该项目可能会使用随机矩阵理论、动力系统、代数和数值分析等技术，以研究者和合作者在其中一些领域的最新进展为基础。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Many Nodal Domains in Random Regular Graphs

随机正则图中的许多节点域

• DOI: 10.1007/s00220-023-04709-6
• 发表时间: 2023
• 期刊: Communications in Mathematical Physics
• 影响因子: 2.4
• 作者: Ganguly, Shirshendu;McKenzie, Theo;Mohanty, Sidhanth;Srivastava, Nikhil
• 通讯作者: Srivastava, Nikhil

A Spectral Approach to Polytope Diameter

多面体直径的光谱方法

• 发表时间: 2022
• 期刊: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022
• 作者: Narayanan, Hariharan;Shah, Rikhav;Srivastava, Nikhil
• 通讯作者: Srivastava, Nikhil

The Complexity of Diagonalization

对角化的复杂性

• DOI: 10.1145/3597066.3597145
• 发表时间: 2023
• 期刊: ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
• 作者: Srivastava, Nikhil

Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization

Jordan 范式的位复杂度和多项式谱分解

• 发表时间: 2023
• 期刊: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023
• 作者: Dey, Papri;Kannan, Ravi;Ryder, Nick;Srivastava, Nikhil
• 通讯作者: Srivastava, Nikhil

Support of closed walks and second eigenvalue multiplicity of graphs

图的封闭游走和第二特征值重数的支持

• DOI: 10.1145/3406325.3451129
• 发表时间: 2021
• 期刊: STOC 2021
• 作者: McKenzie, Theo;Rasmussen, Peter Michael;Srivastava, Nikhil
• 通讯作者: Srivastava, Nikhil