On solving sparse band systems with three algorithms of the ABS family (Q911214)

We examine three algorithms in the ABS family and consider their storage requirements on sparse band systems. It is shown that, when using the implicit Cholesky algorithm on a band matrix with band width \(2q+1\), only q additional vectors are required. Indeed, for any matrix with upper band width q, only q additional vectors are needed. More generally, if \(a_{kj}\neq 0\), \(j>k\), then the jth row of \(H_ i\) is effectively nonzero if \(j>i>k\). The arithmetic operations involved in solving a band matrix by this method are dominated by \((1/2)n^ 2q.\) Special results are obtained for q-band tridiagonal matrices and cyclic band matrices. The implicit Cholesky algorithm may require pivoting if the matrix A does not possess positive-definite principal minors, so two further algorithms were considered that do not require this property. When using the implicit QR algorithm, a matrix with bandwidth q needs at most 2q additional vectors. Similar results for q-band tridiagonal matrices and cyclic band matrices are obtained. For the symmetric Huang algorithm, a matrix with bandwidth q requires q-1 additional vectors. The storage required for q-band tridiagonal matrices and cyclic band matrices are again analyzed.