Packed storage matrix

A packed storage matrix, also known as packed matrix, is a term used in programming for representing an $m\times n$ matrix. It is a more compact way than an m-by-n rectangular array by exploiting a special structure of the matrix.

Typical examples of matrices that can take advantage of packed storage include:

• symmetric or hermitian matrix
• Triangular matrix
• Banded matrix.

Triangular packed matrices

The packed storage matrix allows a matrix to be converted to an array, shrinking the matrix significantly. In doing so, a square $n\times n$ matrix is converted to an array of length Template:Math.

Consider the following upper matrix:

$𝐔=\left(\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& a_{14}\\ & a_{22}& a_{23}& a_{24}\\ & & a_{33}& a_{34}\\ & & & a_{44}\end{array}\right)$

which can be packed into the one array:

$𝐔𝐏=(\underbrace{a_{11}}\underbrace{a_{12}{a}_{22}}\underbrace{a_{13}{a}_{23}{a}_{33}}\underbrace{a_{14},a_{24}{a}_{34}{a}_{44}})$

Similarly the lower matrix:

$𝐋=\left(\begin{array}{cccc}{a}_{11}& & & \\ a_{21}& a_{22}& & \\ a_{31}& a_{32}& a_{33}& \\ a_{41}& a_{42}& a_{43}& a_{44}\end{array}\right).$

can be packed into the following one dimensional array:

$LP=(\underbrace{a_{11}{a}_{21}{a}_{31}{a}_{41}}\underbrace{a_{22}{a}_{32}{a}_{42}}\underbrace{a_{33}{a}_{43}}\underbrace{a_{44}})$

Code examples (Fortran)

Both of the following storage schemes are used extensively in BLAS and LAPACK.

An example of packed storage for Hermitian matrix:

complex :: A(n,n) ! a hermitian matrix
complex :: AP(n*(n+1)/2) ! packed storage for A
! the lower triangle of A is stored column-by-column in AP.
! unpacking the matrix AP to A
do j=1,n
  k = j*(j-1)/2
  A(1:j,j) = AP(1+k:j+k)
  A(j,1:j-1) = conjg(AP(1+k:j-1+k))
end do

An example of packed storage for banded matrix:

real :: A(m,n) ! a banded matrix with kl subdiagonals and ku superdiagonals
real :: AP(-kl:ku,n) ! packed storage for A
! the band of A is stored column-by-column in AP. Some elements of AP are unused.
! unpacking the matrix AP to A
do j = 1, n
  forall(i=max(1,j-kl):min(m,j+ku)) A(i,j) = AP(i-j,j)
end do
print *,AP(0,:) ! the diagonal

See also

• Sparse matrix
• Skyline matrix
• band matrix

Further reading

• https://www.netlib.org/lapack/lug/
• https://www.netlib.org/blas/
• https://github.com/numericalalgorithmsgroup/LAPACK_Examples