On solving sparse band systems with three algorithms of the ABS family (Q911214)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On solving sparse band systems with three algorithms of the ABS family |
scientific article |
Statements
On solving sparse band systems with three algorithms of the ABS family (English)
0 references
1991
0 references
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.
0 references
Abaffy-Broyden-Spedicato methods
0 references
ABS methods
0 references
sparse band systems
0 references
implicit Cholesky algorithm
0 references
tridiagonal matrices
0 references
cyclic band matrices
0 references
Huang algorithm
0 references