A Recursive Formulation of Cholesky Factorization of a Matrix in Packed Storage Format

Bjarne Stig Andersen, Fred Gustavson, Jerzy Wasniewski

AbstractA 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.
Keywordsreal symmetric matrices, complex Hermitian matrices, positive definite matrices, Choleski factorization and solution, recursive algorithms, novel packed data strucrures, linear systems of equations
TypeJournal paper [With referee]
JournalACM Transactions on Mathematical Software
EditorsJohn Reid
Year2001    Month June    Vol. 27    No. 2    pp. 214-244
PublisherACM
AddressNew York, USA
SeriesTransactions on Mathematical Software
BibTeX data [bibtex]
IMM Group(s)Scientific Computing