The retraction algorithm for factoring banded symmetric matrices Numerical Linear Algebra with Applications

SUMMARY Let A be an n ◊ n symmetric matrix of bandwidth 2m + 1. The matrix need not be positive definite. In this paper we will present an algorithm for factoring A which preserves symmetry and the band structure and limits element growth in the factorization. With this factorization one may solve a linear system with A as the coecient matrix and determine the inertia of A, the number of positive, negative, and zero eigenvalues of A. The algorithm requires between 1/2nm 2 and 5/4nm 2 multiplications and at most (2m+1)n locations compared to nonsymmetric Gaussian elimination which requires between nm 2 and 2nm 2 multiplications and at most (3m +1 )n locations. Our algorithm reduces A to block diagonal form with 1◊ 1a nd 2◊2 blocks on the diagonal. When pivoting for stability and subsequent transformations produce nonzero elements outside the original band, column/row transformations are used to retract the bandwidth. To decrease the operation count and the necessary storage, we use the fact that the correction outside the band is rank-1 and invert the process, applying the transformations that would restore the bandwidth first, followed by a modified correction. This paper contains an element growth analysis and a computational comparison with LAPACKs nonsymmetric band routines and the Snap-back code of Irony and Toledo. Copyright c 2000 John Wiley & Sons, Ltd.