We present a superfast divide-and-conquer method for finding all the eigenvalues as well as all the eigenvectors (in a structured form) of a class of symmetric matrices with off-diagonal ranks or numerical ranks bounded by $r$, as well as the approximation accuracy of the eigenvalues due to off-diagonal compression. More specifically, the complexity is $O(r^{2}n\log n)+O(rn\log^{2}n)$, where $n$ is the order of the matrix. Such matrices are often encountered in practical computations with banded matrices, Toeplitz matrices (in Fourier space), and certain discretized problems. They can be represented or approximated by hierarchically semiseparable (HSS) matrices. We show how to preserve the HSS structure throughout the dividing process that involves recursive updates and how to quickly perform stable eigendecompositions of the structured forms. Various other numerical issues are discussed, such as computation reuse and deflation. The structure of the eigenvector matrix is also shown. We further analyze the...
['James E. Vogel', 'Jianlin Xia', 'Stephen F. Cauley', 'Venkataramanan Balakrishnan']
Superfast Divide-and-Conquer Method and Perturbation Analysis for Structured Eigenvalue Solutions