next up previous contents index
Next: Tridiagonal and Bidiagonal Matrices Up: Matrix Storage Schemes Previous: Packed Storage   Contents   Index


Band Storage

An m-by-n band matrix with kl subdiagonals and ku superdiagonals may be stored compactly in a two-dimensional array with kl+ku+1 rows and n columns. Columns of the matrix are stored in corresponding columns of the array, and diagonals of the matrix are stored in rows of the array. This storage scheme should be used in practice only if $kl, ku \ll \min(m,n)$, although LAPACK routines work correctly for all values of kl and ku. In LAPACK, arrays that hold matrices in band storage have names ending in `B'.

To be precise, aij is stored in AB(ku+1+i-j,j) for $\max(1,j-ku) \leq i \leq \min(m,j+kl)$. For example, when m = n = 5, kl = 2 and ku = 1:

Band matrix A Band storage in array AB
$
\left( \begin{array}{ccccc}
a_{11} & a_{12} & & & \\
a_{21} & a_{22} & a_{23}...
..._{43} & a_{44} & a_{45} \\
& & a_{53} & a_{54} & a_{55}
\end{array} \right)
$ $
\begin{array}{ccccc}
\ast & a_{12} & a_{23} & a_{34} & a_{45} \\
a_{11} & a_...
... a_{43} & a_{54} & \ast \\
a_{31} & a_{42} & a_{53} & \ast & \ast
\end{array}$

The elements marked $\ast$ in the upper left and lower right corners of the array AB need not be set, and are not referenced by LAPACK routines.

Note: when a band matrix is supplied for LU factorization, space must be allowed to store an additional kl superdiagonals, generated by fill-in as a result of row interchanges. This means that the matrix is stored according to the above scheme, but with kl + ku superdiagonals.

Triangular band matrices are stored in the same format, with either kl = 0 if upper triangular, or ku = 0 if lower triangular.

For symmetric or Hermitian band matrices with kd subdiagonals or superdiagonals, only the upper or lower triangle (as specified by UPLO) need be stored:

For example, when n = 5 and kd = 2:

UPLO Hermitian band matrix A Band storage in array AB
`U' $
\left( \begin{array}{ccccc}
a_{11} & a_{12} & a_{13} & & \\
\bar{a}_{12} & a_...
...44} & a_{45} \\
& & \bar{a}_{35} & \bar{a}_{45} & a_{55}
\end{array} \right)
$ $
\begin{array}{ccccc}
\ast & \ast & a_{13} & a_{24} & a_{35} \\
\ast & a_{12...
...3} & a_{34} & a_{45} \\
a_{11} & a_{22} & a_{33} & a_{44} & a_{55}
\end{array}$
`L' $
\left( \begin{array}{ccccc}
a_{11} & \bar{a}_{21} & \bar{a}_{31} & & \\
a_{21...
... & a_{44} & \bar{a}_{54} \\
& & a_{53} & a_{54} & a_{55}
\end{array} \right)
$ $
\begin{array}{ccccc}
a_{11} & a_{22} & a_{33} & a_{44} & a_{55} \\
a_{21} & a...
... a_{43} & a_{54} & \ast \\
a_{31} & a_{42} & a_{53} & \ast & \ast
\end{array}$

EISPACK routines use a different storage scheme for band matrices, in which rows of the matrix are stored in corresponding rows of the array, and diagonals of the matrix are stored in columns of the array (see Appendix D).


next up previous contents index
Next: Tridiagonal and Bidiagonal Matrices Up: Matrix Storage Schemes Previous: Packed Storage   Contents   Index
Susan Blackford
1999-10-01