On the computation of null spaces of sparse rectangular matrices

Craig Gotsman, Sivan Toledo

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

Computing the null space of a sparse matrix is an important part of some computations, such as embeddings and parametrization of meshes. We propose an efficient and reliable method to compute an orthonormal basis of the null space of a sparse square or rectangular matrix (usually with more rows than columns). The main computational component in our method is a sparse LU factorization with partial pivoting of the input matrix; this factorization is significantly cheaper than the QR factorization used in previous methods. The paper analyzes important theoretical aspects of the new method and demonstrates experimentally that it is efficient and reliable.

Original languageEnglish (US)
Pages (from-to)445-463
Number of pages19
JournalSIAM Journal on Matrix Analysis and Applications
Volume30
Issue number2
DOIs
StatePublished - 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis

Keywords

  • Inverse iteration
  • LU factorization
  • Null space
  • Rectangular matrices
  • sparse matrices polynomial

Fingerprint

Dive into the research topics of 'On the computation of null spaces of sparse rectangular matrices'. Together they form a unique fingerprint.

Cite this