AF: SMALL: Provable Algorithms for Nonhermitian Matrices

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

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.