Sparse Matrix - Band Matrix

Band Matrix

An important special type of sparse matrices is band matrix, defined as follows. The lower bandwidth of a matrix A is the smallest number p such that the entry aij vanishes whenever i > j + p. Similarly, the upper bandwidth is the smallest p such that aij = 0 whenever i < jp (Golub & Van Loan 1996, §1.2.1). For example, a tridiagonal matrix has lower bandwidth 1 and upper bandwidth 1. As another example, the following sparse matrix has lower and upper bandwidth both equal to 3. Notice that zeros are represented with dots.


\left(
\begin{smallmatrix}
X & X & X & . & . & . & . &\\
X & X & . & X & X & . & . &\\
X & . & X & . & X & . & . &\\
. & X & . & X & . & X & . &\\
. & X & X & . & X & X & X &\\
. & . & . & X & X & X & . &\\
. & . & . & . & X & . & X &\\
\end{smallmatrix}
\right)

Matrices with reasonably small upper and lower bandwidth are known as band matrices and often lend themselves to simpler algorithms than general sparse matrices; or one can sometimes apply dense matrix algorithms and gain efficiency simply by looping over a reduced number of indices.

By rearranging the rows and columns of a matrix A it may be possible to obtain a matrix A’ with a lower bandwidth. A number of algorithms are designed for bandwidth minimization.

Read more about this topic:  Sparse Matrix

Famous quotes containing the words band and/or matrix:

    There was a young lady called Gloria
    Who was had by Sir Gerald Du Maurier
    And then by six men
    And Sir Gerald again
    And the band of the Waldorf-Astoria.
    Anonymous.

    In all cultures, the family imprints its members with selfhood. Human experience of identity has two elements; a sense of belonging and a sense of being separate. The laboratory in which these ingredients are mixed and dispensed is the family, the matrix of identity.
    Salvador Minuchin (20th century)