Block tridiagonalization of "effectively" sparse symmetric matrices
Lists
Only you see this
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...