### Abstract

We consider systems of equations of the form AA^{T}x = 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 AA^{T} 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 AA^{T} in terms of the solution of systems involving SS^{T} using either conjugate-gradient techniques or the Sherman-Morrison-Woodbury formula. This approach has the difficulty that SS^{T} is often rank-deficient even when AA^{T} 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 language | English (US) |
---|---|

Pages (from-to) | 107-117 |

Number of pages | 11 |

Journal | Linear Algebra and Its Applications |

Volume | 152 |

Issue number | C |

DOIs | |

State | Published - Jul 1 1991 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

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