PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 20 February 2004

A new sparse out-of-core symmetric indefinite factorization algorithm

Omer Meshar and Sivan Toledo
Tel-Aviv University
Israel
email: stoledo@tau.ac.il

We present a new out-of-core sparse symmetric-indefinite factorization algorithm. The most significant innovation of the new algorithm is a dynamic partitioning method for the sparse factor. This partitioning method results in very low input-output traffic and allows the algorithm to run at high computational rates even though the factor is stored on a slow disk. Our implementation of the new code compares well with both high-performance in-core sparse symmetric-indefinite codes and with a high-performance out-of-core sparse Cholesky code. More specifically, the new code provides a new capability that none of these existing codes has: it can factor symmetric indefinite matrices whose factors are larger than main memory; it is somewhat slower, but not by much. For example, it factors, on a conventional 32-bit workstation, an indefinite finite-element matrix whose factor size is about 10 GB in less than an hour.

Home page