$O( n^2 )$ Reduction Algorithms for the Construction of a Band Matrix from Spectral Data
Gregory S. Ammar, William B. Gragg · SIAM Journal on Matrix Analysis and Applications · 1991
Efficient rotation patterns are presented that provide stable $O( n^2 )$ algorithms for the construction of a real symmetric band matrix having specified eigenvalues and first p components of its normalized eigenvectors. These methods can also be used in the second phase of the construction of a band matrix from the interlacing eigenvalues as described in [Linear Algebra Appl ., 40 (1981), pp. 79–87]. Previously presented algorithms for these reductions that use elementary orthogonal similarity transformations require $O(n^3)$ arithmetic operations.