A Recursive Formulation of Cholesky Factorization of a Matrix in Packed Storage Format | Bjarne Stig Andersen, Fred Gustavson, Jerzy Wasniewski
| | Abstract | A new compact way to store a symmetric or triangular matrix
called RPF for Recursive Packed Format is fully described.
Novel ways to transform RPF to and from standard packed format
are included. A new algorithm, called RPC for Recursive Packed Cholesky
that operates on the RPF format is presented. Algorithm RPC is based
on level-3 BLAS and requires variants of algorithms {\bf TRSM} and
{\bf SYRK} that work on RPF. We call these {\bf RP\_TRSM} and
{\bf RP\_SYRK} and find that they do
most of their work by calling {\bf GEMM}. It follows that most of the execution
time of RPC lies in {\bf GEMM}.
The advantage of this storage scheme compared to traditional packed
and full storage is demonstrated. First, the RPC storage format uses the
minimal amount of storage for the symmetric or triangular matrix.
Second, RPC gives a level-3 implementation of Cholesky factorization
whereas standard packed implementations are only level 2. Hence, the
performance of
our RPC implementation is decidedly superior. Third, unlike fixed block size
algorithms, RPC requires no block size tuning parameter.
We present performance measurements on several current architectures
that demonstrate improvements over the traditional packed
routines. Also SMP parallel computations on the IBM SMP computer are
made. The graphs that are attached in the appendix of the paper, show
that the RPC algorithms are superior by a factor between 1.6 and 7.4
for order around 1000, and between 1.9 and 10.3 for order around 3000 over the
traditional packed algorithms. For some architectures, the RPC
performance results
are almost the same or even better than the traditional full-storage
algorithm results. | | Keywords | real symmetric matrices, complex Hermitian matrices, positive definite matrices, Choleski factorization and solution, recursive algorithms, novel packed data strucrures, linear systems of equations | | Type | Journal paper [With referee] | | Journal | ACM Transactions on Mathematical Software | | Editors | John Reid | | Year | 2001 Month June Vol. 27 No. 2 pp. 214-244 | | Publisher | ACM | | Address | New York, USA | | Series | Transactions on Mathematical Software | | BibTeX data | [bibtex] | | IMM Group(s) | Scientific Computing |
|