Geodesic
Locality of reference in sparse Cholesky factorization methods
Electronic transactions on numerical analysis, Tome 21 (2005), pp. 81-106.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: This paper analyzes the cache efficiency of two high-performance sparse Cholesky factorization algorithms: the multifrontal algorithm and the left-looking algorithm. These two are essentially the only two algorithms that are used in current codes; generalizations of these algorithms are used in general-symmetric and general-unsymmetric sparse triangular factorization codes. Our theoretical analysis shows that while both algorithms sometimes enjoy a high level of data reuse in the cache, they are incomparable: there are matrices on which one is cache efficient and the other is not, and vice versa. The theoretical analysis is backed up by detailed experimental evidence, which shows that our theoretical analyses do predict cache-miss rates and performance in practice, even though the theory uses a fairly simple cache model. We also show, experimentally, that on matrices arising from finite-element structural analysis, the left-looking algorithm consistently outperforms the multifrontal algorithm. Di- rect cache-miss measurements indicate that the difference in performance is largely due to differences in the number of level-2 cache misses that the two algorithms generate. Finally, we also show that there are matrices where the multifrontal algorithm may require significantly more memory than the left-looking algorithm. On the other hand, the left-looking algorithm never uses more memory than the multifrontal one.
Classification : 15A23, 65F05, 65F50, 65Y10, 65Y20
Keywords: Cholesky factorization, sparse Cholesky, multifrontal methods, cache-efficiency, locality of reference 
@article{ETNA_2005__21__a3,
     author = {Rozin, Elad and Toledo, Sivan},
     title = {Locality of reference in sparse {Cholesky} factorization methods},
     journal = {Electronic transactions on numerical analysis},
     pages = {81--106},
     publisher = {mathdoc},
     volume = {21},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2005__21__a3/}
}
TY  - JOUR
AU  - Rozin, Elad
AU  - Toledo, Sivan
TI  - Locality of reference in sparse Cholesky factorization methods
JO  - Electronic transactions on numerical analysis
PY  - 2005
SP  - 81
EP  - 106
VL  - 21
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ETNA_2005__21__a3/
LA  - en
ID  - ETNA_2005__21__a3
ER  - 
%0 Journal Article
%A Rozin, Elad
%A Toledo, Sivan
%T Locality of reference in sparse Cholesky factorization methods
%J Electronic transactions on numerical analysis
%D 2005
%P 81-106
%V 21
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ETNA_2005__21__a3/
%G en
%F ETNA_2005__21__a3
Rozin, Elad; Toledo, Sivan. Locality of reference in sparse Cholesky factorization methods. Electronic transactions on numerical analysis, Tome 21 (2005), pp. 81-106. http://geodesic.mathdoc.fr/item/ETNA_2005__21__a3/