Абстракт. The symmetric tridiagonal eigenvector problem has been a central research topic in numerical linear algebra since its inception. Of the myriad of algorithms today, none is provably optimal and accurate at the same time. “Optimal” means, a subset of k eigenvectors is computed in O(kn) time. “Accurate” means that the computes eigenvectors are orthogonal and satisfy the typical relative gap error bound.

In this talk, we focus our attention on a neglected oscillating property of the eigenvectors: the i-th eigenvector has exactly i – 1 changes of sign in its entries. Long considered irrelevant, because the tiny entries of the eigenvectors don’t seem to be of any practical importance, this property may hold the key to accurate eigenvectors computed in optimal time!

Such an approach is not without precedent: the preservation of the mathematical properties of the computed objects has lead to major progress in various computations.

We present a new algorithm that computes individual eigenvectors in optimal, O(n) time, each guaranteed to have the correct number of sign changes, and satisfying the conventional relative gap error bound. The numerical experiments in this work in progress look promising in that the computed eigenvectors seem to also be orthogonal.