Splitting dense columns in sparse linear systems

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

We consider systems of equations of the form AATx = b, where A is a sparse matrix having a small number of columns which are much denser than the other columns. These dense columns in A cause AAT to be very (or even completely) dense, which greatly limits the effectiveness of sparse-matrix techniques for directly solving the above system of equations. In the literature on interior-point methods for linear programming, the usual technique for dealing with this problem is to split A into a sparse part S and a dense part D, A = [S D], and to solve systems involving AAT in terms of the solution of systems involving SST using either conjugate-gradient techniques or the Sherman-Morrison-Woodbury formula. This approach has the difficulty that SST is often rank-deficient even when AAT has full rank. In this paper we propose an alternative method which avoids the rank-deficiency problem and at the same time allows for the effective use of sparse-matrix techniques. The resulting algorithm is both efficient and robust.

Original languageEnglish (US)
Pages (from-to)107-117
Number of pages11
JournalLinear Algebra and Its Applications
Volume152
Issue numberC
DOIs
StatePublished - Jul 1 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Splitting dense columns in sparse linear systems'. Together they form a unique fingerprint.

  • Cite this