Packed storage matrix

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

Matrix Storage Schemes

• Full storage: a matrix A is stored in a two-dimensional array a, with the matrix element aij stored in the array element a(i,j).

• Packed storage scheme allows you to store symmetric, Hermitian, or triangular matrices more compactly: the upper or lower triangle of the matrix is packed by columns in a one-dimensional array.

• Band storage: an m-by-n band matrix with kl sub-diagonals and ku superdiagonals is stored compactly in a two-dimensional array ab with kl+ku+1 rows and n columns. Columns of the matrix are stored in the corresponding columns of the array, and diagonals of the matrix are stored in rows of the array.

• Rectangular Full Packed (RFP) storage: the upper or lower triangle of the matrix is packed combining the full and packed storage schemes. This combination enables using half of the full storage as packed storage while maintaining efficiency by using Level 3 BLAS/LAPACK kernels as the full storage.

These are most notably used in BLAS and LAPACK. Various storage schemes for sparse matrices can also be regarded as packed storage.

Packed Storage

A packed vector is an alternate representation for a triangular, symmetric, or Hermitian matrix. An array is packed into a vector by storing the elements sequentially column by column into the vector. Space for the diagonal elements is always reserved, even if the values of the diagonal elements are known, such as in a unit diagonal matrix.

An upper triangular matrix or a symmetric matrix whose upper triangle is stored in general storage in the array A, can be transferred to packed storage in the array AP as shown below. This code comes from the comment block of the LAPACK routine

   JC = 1
    DO J = 1, N
       DO I = 1, J
          AP(JC+I-1) = A(I,J)
       END DO
       JC = JC + J
   END DO

Similarly, a lower triangular matrix or a symmetric matrix whose lower triangle is stored in general storage in the array A, can be transferred to packed storage in the array AP as shown below:

   JC = 1
   DO J = 1, N
      DO I = J, N
         AP(JC+I-1) = A(I,J)
      END DO
      JC = JC + N - J + 1
   END DO

For a symmetric, hermitian or triangular matrix, only the lower or upper triangle of the matrix needs to be stored. A banded matrix can be represented by storing the band only. Packed storage saves memory at the cost of more complicated access to matrix elements. Because of this tradeoff, it is not always beneficial.

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