Premium
The retraction algorithm for factoring banded symmetric matrices
Author(s) -
Kaufman Linda
Publication year - 2007
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.529
Subject(s) - mathematics , gaussian elimination , diagonal , algorithm , factorization , cuthill–mckee algorithm , band matrix , block matrix , eigenvalues and eigenvectors , diagonal matrix , matrix (chemical analysis) , combinatorics , symmetric matrix , gaussian , square matrix , geometry , physics , materials science , quantum mechanics , composite material
Let A be an n × n symmetric matrix of bandwidth 2 m + 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 coefficient matrix and determine the inertia of A , the number of positive, negative, and zero eigenvalues of A . The algorithm requires between 1/2 nm 2 and 5/4 nm 2 multiplications and at most (2 m + 1) n locations compared to non‐symmetric Gaussian elimination which requires between nm 2 and 2 nm 2 multiplications and at most (3 m + 1) n locations. Our algorithm reduces A to block diagonal form with 1 × 1 and 2 × 2 blocks on the diagonal. When pivoting for stability and subsequent transformations produce non‐zero 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 non‐symmetric band routines and the Snap‐back code of Irony and Toledo. Copyright © 2007 John Wiley & Sons, Ltd.