# Splitting dense columns in sparse linear systems

Research output: Contribution to journalArticlepeer-review

16 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 language English (US) 107-117 11 Linear Algebra and Its Applications 152 C https://doi.org/10.1016/0024-3795(91)90269-3 Published - Jul 1 1991 Yes

## 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8921497,"math_prob":0.52698976,"size":1414,"snap":"2021-31-2021-39","text_gpt3_token_len":307,"char_repetition_ratio":0.095744684,"word_repetition_ratio":0.0,"special_character_ratio":0.208628,"punctuation_ratio":0.046025105,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9639569,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-19T15:37:59Z\",\"WARC-Record-ID\":\"<urn:uuid:3520e9fd-01e0-4b7b-b984-67e0de7e4b08>\",\"Content-Length\":\"47508\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6840d187-678a-40c7-ba63-dfd0fbf5aebb>\",\"WARC-Concurrent-To\":\"<urn:uuid:cad7abc4-672f-4110-b81a-e823295dfa72>\",\"WARC-IP-Address\":\"3.90.122.189\",\"WARC-Target-URI\":\"https://collaborate.princeton.edu/en/publications/splitting-dense-columns-in-sparse-linear-systems\",\"WARC-Payload-Digest\":\"sha1:KWFXKISUOH6ZY3EHLMGZELQUEZYF7GHN\",\"WARC-Block-Digest\":\"sha1:4QLAOSOXBQSLRDJOESMRS4QIWHIFOPX4\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780056890.28_warc_CC-MAIN-20210919125659-20210919155659-00415.warc.gz\"}"}