Collaborative Research: An Optimal Algorithm for Orthogonal Eigenvectors of Symmetric Tridiagonals

研究人员将设计，实现，并执行一个新的稳定算法的三对角特征向量问题的彻底的理论和数值分析。该项目不仅将推动数值线性代数领域的发展，而且将立即影响所有使用数学模型的研究领域，这些模型的计算瓶颈是特征值/特征向量算法。许多自然现象（例如，热传递，湍流，波传播等）都是由微分方程控制的，这在离散时导致特征值/特征向量问题。这种新算法不仅可以降低在现有应用中获得准确结果的成本，而且还可以使目前计算成本过高的应用成为可能。该项目将为本科生和研究生提供研究培训机会。新的特征向量算法将比现有算法更精确，但在效率上与现有最佳算法竞争，并具有最优的复杂度。计算的特征向量不仅具有传统的精度特性，如残差小和相对于通常的相对间隙误差界的精度，而且还具有与工作精度正交和每个特征向量具有正确的符号变化数的真正对应物的数学特性。后两个性质是由数据很好地确定的，它们源于对称三对角矩阵与完全非负矩阵（所有小矩阵非负）的联系。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The investigators will design, implement, and perform a thorough theoretical and numerical analysis of a new stable algorithm for the tridiagonal eigenvector problem. This project will not only advance the field of numerical linear algebra, but will also immediately impact all areas of research which use mathematical models whose computational bottlenecks are eigenvalue/eigenvector algorithms for their study and development. Many natural phenomena (e.g., heat transfer, turbulence, wave propagation, etc.) are governed by differential equations, which result in an eigenvalue/eigenvector problem when discretized. This new algorithm will not only reduce the cost of obtaining accurate results in existing applications but also enable applications which may currently be computationally cost prohibitive. The project will provide research training opportunities for both undergraduate and graduate students. The new eigenvector algorithm will be more accurate than the existing algorithms, yet competitive in its efficiency with the best existing ones and have optimal complexity. The computed eigenvectors will not only have the traditional accuracy properties such as small residuals and accuracy with respect to the usual relative gap error bound, but will also possess the mathematical properties of their true counterparts of being orthogonal to working precision and having the correct number of sign changes in each eigenvector. The latter two properties are well determined by the data and stem from the connection of the symmetric tridiagonal matrices with the totally nonnegative matrices (matrices with all minors nonnegative).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.