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.