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

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

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.