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.