Packed storage matrix

A packed storage matrix, also known as packed matrix, is a term used in programming for representing an ${\displaystyle 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.

The packed storage matrix allows a matrix to be converted to an array, shrinking the matrix significantly. In doing so, a square ${\displaystyle n\times n}$ matrix is converted to an array of length ⁠n(n+1)/2⁠.¹

Consider the following upper matrix:

${\displaystyle \mathbf {U} ={\begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\&a_{22}&a_{23}&a_{24}\\&&a_{33}&a_{34}\\&&&a_{44}\\\end{pmatrix}}}$

which can be packed into the one array:

${\displaystyle \mathbf {UP} =(\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:

${\displaystyle \mathbf {L} ={\begin{pmatrix}a_{11}&&&\\a_{21}&a_{22}&&\\a_{31}&a_{32}&a_{33}&\\a_{41}&a_{42}&a_{43}&a_{44}\\\end{pmatrix}}.}$

can be packed into the following one dimensional array:

${\displaystyle 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}} )}$²

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