EECS Publication
Block-Tridiagonalization of 'Effectively' Sparse Symmetric Matrices
Yihua Bai, Wilfried N. Gansterer and Robert C. Ward
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-andconquer eigensolver [6], for which block tridiagonalization is 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-andconquer method. Numerical experiments are presented and various potential block tridiagonalization strategies are compared.
Published 2002-11-01 05:00:00 as ut-cs-02-492 (ID:238)