Editing Packed storage matrix

{{Short description|Programming term}}
{{More sources needed|date=December 2009}}

A '''packed storage matrix''', also known as '''packed matrix''', is a term used in [[Mathematical programming|programming]] for representing an <math>m\times n</math> [[Matrix (mathematics)|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 matrix|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 <math>n \times n</math> matrix is converted to an array of length {{math|{{sfrac|n(n+1)|2}}}}.<ref>{{cite book |last1=Golub |first1=Gene H. |last2=Van Loan |first2=Charles F. |title=Matrix Computations |date=2013 |edition=4th |publisher=Johns Hopkins University Press |location=Baltimore, MD |page=170 |isbn=9781421407944}}</ref>

Consider the following upper matrix:
:<math>\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}</math>
which can be packed into the one array:
:<math> \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}})
</math><ref name = blackford>{{cite web |last=Blackford |first=Susan |title=Packed Storage |url=https://www.netlib.org/lapack/lug/node123.html |website=Netlib |publisher=LAPACK Users' Guide |date=1999-10-01 |access-date=2024-10-01 |archive-url=https://web.archive.org/web/20240401131450/https://www.netlib.org/lapack/lug/node123.html |archive-date=2024-04-01}}</ref>


Similarly the lower matrix:
:<math>\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}.</math>
can be packed into the following one dimensional array:
:<math>
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}})
</math><ref name=blackford/>

==Code examples (Fortran)==
Both of the following storage schemes are used extensively in BLAS and LAPACK.

An example of packed storage for Hermitian matrix:
<syntaxhighlight lang="fortran">
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
</syntaxhighlight>

An example of packed storage for banded matrix:
<syntaxhighlight lang="fortran">
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
</syntaxhighlight>


==See also==
* [[Sparsity|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

==References==
{{Reflist}}

{{DEFAULTSORT:Packed Storage Matrix}}
[[Category:Arrays]]
[[Category:Matrices (mathematics)]]

{{matrix-stub}}