Block tridiagonalization of "effectively" sparse symmetric matrices

Yihua Bai, Wilfried N. Gansterer, Robert C. WardACM Trans. Math. Softw 2004 · DOI · OpenReview

Abstract

A block tridiagonalization algorithm is proposed for transforming a sparse (or "effectively" sparse) symmetric matrix into a related block tridiagonal matrix, such that the eigenvalue error remains bounded by some prescribed accuracy tolerance. It is based on a heuristic for imposing a block tridiagonal structure on matrices with a large percentage of zero or "effectively zero" (with respect to the given accuracy tolerance) elements. In the light of a recently developed block tridiagonal divide-and-conquer eigensolver [Gansterer, Ward, Muller, and Goddard, III, SIAM J. Sci. Comput. 25 (2003), pp. 65--85], for which block tridiagonalization may be needed as a preprocessing step, the algorithm also provides an option for attempting to produce at least a few very small diagonal blocks in the block tridiagonal matrix. This leads to low time complexity of the last merging operation in the block divide-and-conquer method. Numerical experiments are presented and various block tridiagonalization strategies are compared.
BibTeX
@article{bai2004block,
  author = {Yihua Bai and Wilfried N. Gansterer and Robert C. Ward},
  title = {{Block tridiagonalization of "effectively" sparse symmetric matrices}},
  journal = {ACM Trans. Math. Softw.},
  year = {2004},
  doi = {10.1145/1024074.1024078},
}

Loading related content...

Figure