On the minimum FLOPs problem in the sparse Cholesky factorization

DOI10.1137/130912438MaRDI QIDQ2877076zbMATH OpenOpenAlexWikidataFDO

Authors Robert Luce, Esmond G. Ng

Publication date 21 August 2014

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.1754

zbMATH Keywords

computational complexitysparse Cholesky factorizationminimum operation countminimum fill

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Prior to computing the Cholesky factorization of a sparse, symmetric positive definite matrix, a reordering of the rows and columns is computed so as to reduce both the number of fill elements in Cholesky factor and the number of arithmetic operations (FLOPs) in the numerical factorization. These two metrics are clearly somehow related and yet it is suspected that these two problems are different. However, no rigorous theoretical treatment of the relation of these two problems seems to have been given yet. In this paper we show by means of an explicit, scalable construction that the two problems are different in a very strict sense. In our construction no ordering, that is optimal for the fill, is optimal with respect to the number of FLOPs, and vice versa. Further, it is commonly believed that minimizing the number of FLOPs is no easier than minimizing the fill (in the complexity sense), but so far no proof appears to be known. We give a reduction chain that shows the NP hardness of minimizing the number of arithmetic operations in the Cholesky factorization.

Recommendations

• On Optimal Reorderings of Sparse Matrices for Parallel Cholesky Factorizations
• Minimum communication cost reordering for parallel sparse Cholesky factorization
• Finding optimal ordering of sparse matrices for column-oriented parallel Cholesky factorization
• Minimal orderings revisited
• A column approximate minimum degree ordering algorithm

Cited in

(8)

• A survey of direct methods for sparse linear systems
• Exact solution of sparse linear systems via left-looking roundoff-error-free Lu factorization in time proportional to arithmetic work
• Finding optimal ordering of sparse matrices for column-oriented parallel Cholesky factorization
• Algorithm 1050: SPEX Cholesky, LDL, and backslash for exactly solving sparse linear systems
• Expediting exact linear programming solvers via integer preserving factorization
• The average parallel complexity of Cholesky factorization
• Reordering strategy for blocking optimization in sparse linear solvers
• Exactly solving sparse rational linear systems via roundoff-error-free Cholesky factorizations

This page was built for publication: On the minimum FLOPs problem in the sparse Cholesky factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2877076)