1 of 1

Heuristics for Robust Factorization of Sparse Symmetric Indefinite Matrices

Scientific Achievement

During the factorization of sparse symmetric indefinite matrices maintaining sparsity and symmetry while keeping it stable is a challenging task.
Numerical pivoting is needed in order to achieve these goals.
Supernodes are group of columns with almost identical sparsity pattern
Utilizing supernode structure in Cholesky factorization is a key to achieve high performance
We propose two heuristics which utilize supernode structure as much as possible in the indefinite matrix factorization together with Bunch-Kaufman pivoting which was developed for dense matrices
Our initial experiments show that proposed methods are better than the state-of-the-art methods in terms of error and sparsity

Performance profiles show the relative performance of the proposed parent and end methods together with the state-of-the-art MA57 and MUMPS methods with different threshold values in terms of the error and the number of nonzeros in the factor. For a given method, 1-p(𝜏) is the fraction of test problems that the method is worse than the best solver by a factor of 𝜏. The proposed methods are comparable where the parent is slightly better than the end in terms of error, whereas the end is slightly better than the parent in terms of the number of nonzeros. Both proposed methods seems better than the state-of-the-art methods.

Technical Approach

In our methods the main idea is keeping the pivoting in a supernode does not disturb the sparsity
We perform Bunch-Kaufman pivoting if the respective columns are in the same supernode
Otherwise we delay the bad column to the beginning of the parent supernode or to the end of the current supernode, in our parent and end methods, respectively
As also used in other methods we use decreasing threshold for pivot selection in order to increase the chance of accepting the current diagonal element as pivot to main sparsity at the expense of decreased stability

LOCAL LAB POC:

TALKING POINTS:

Please include three to five bulleted talking points.
Talking points should be ready to read, verbatim by the presenter of this slide.
These talking points should be written for an educated, lay audience. Think about your ASCR program manager or ASCR management delivering this slide to Hill staffers or members of the public.
These talking points should express the most important aspects of the work being highlighted. These amount to the “elevator speech” for this work.

METADATA:

Name of the associated awarded project:

PI name(s): Patrick McCormick (LANL), Alex Aiken (Stanford)

Name of the program manager: Supporting technology supported by both ECP and ASCR research (Laura Biven)

CITATIONS:

The notes section should also include full citations (including the DOI) to any important and associated publications, datasets or code developed as part this work.

For publications, please make sure full-text copies of the accepted manuscripts have been submitted to OSTI.
Please ensure that there is at least one publication associated with the highlight. This citation should be included in the slide.

AWARDS:

If this work has received any awards at conference or otherwise, please note them here.

REPRODUCIBILITY:

If this work has received any badges or recognitions for reproducibility, please note them here. (Alternatively, can associated these with specific publications listed above)

BACKGROUND AND CONTEXT INFORMATION:

You may include further background or other information that would be helpful in understanding and delivering the full impact of this research.