Jianlin Xia
Fast and superfast eigensolvers for structured matrices

Department of Mathematics
Purdue University
West Lafayette
IN 47907
xiaj@math.purdue.edu

For structured symmetric matrices such as Toeplitz problems and matrices with certain rank structures, we show a fast iterative eigensolver based on bisection and a superfast direct eigensolver based on divide-and-conquer. The fast eigensolver can quickly update LDL factorizations and the inertia evaluation for varying shifts. It costs about $O(n^2)$ to find all the $n$ eigenvalues. The superfast method hierarchically reduces the eigenvalue problem into smaller structured eigenvalue computations. We show how the structures can be preserved in the divide-and-conquer process. In particular, appropriate ranks remain controlled. The superfast method needs only about $O(n)$ flops to find all the eigenvalues. We also show that, when only few largest eigenvalues are desired, then the fast method can be extended to more general problems via low-rank approximations. This is joint work with James Vogel and Yuanzhe Xi.