Prestructuring sparse matrices with dense rows and columns via null space methods.

DOI10.1002/NLA.2133MaRDI QIDQ4637401zbMATH OpenOpenAlexFDO

Authors Jason Howell

Publication date 18 April 2018

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

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

zbMATH Keywords

direct methodsaddle point problemnull space methoddense rowdense columnprestructuring

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50)

Abstract: Several applied problems may produce large sparse matrices with a small number of dense rows and/or columns, which can adversely affect the performance of commonly used direct solvers. By posing the problem as a saddle point system, an unconventional application of a null space method can be employed to eliminate dense rows and columns. The choice of null space basis is critical in retaining the overall sparse structure of the matrix. A one-sided application of the null space method is also presented to eliminate either dense rows or columns. These methods can be considered techniques that modify the nonzero structure of the matrix before employing a direct solver, and may result in improved direct solver performance.

Recommendations

• A comparative study of null-space factorizations for sparse symmetric saddle point systems.
• A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows
• scientific article; zbMATH DE number 1069171
• State-of-the-art sparse direct solvers
• An application of the Dulmage-Mendelsohn decomposition to sparse null space bases of full row rank matrices

Cited in

(1)

• A null-space approach for large-scale symmetric saddle point systems with a small and non zero \((2, 2)\) block

This page was built for publication: Prestructuring sparse matrices with dense rows and columns via null space methods.

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