liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Matrix stretching for sparse least squares problems
Linkoping Univ, Dept Math, SE-58183 Linkoping, Sweden.
Linkoping Univ, Dept Math, SE-58183 Linkoping, Sweden.
2000 (English)In: Numerical Linear Algebra with Applications, ISSN 1070-5325, E-ISSN 1099-1506, Vol. 7, no 2, 51-65 p.Article in journal (Refereed) Published
Abstract [en]

For linear least squares problems min(x) parallel to Ax - b parallel to(2) where A is sparse except for a few dense rows, a straightforward application of Cholesky or QR factorization will lead to catastrophic fill in the factor R. We consider handling such problems by a matrix stretching technique, where the dense rows are split into several more sparse rows. We develop both a recursive binary splitting algorithm and a more general splitting method. We show that for both schemes the stretched problem has the same set of solutions as the original least squares problem. Further. the condition number of the stretched problem differs from that of the original by only a modest factor, and hence the approach is numerically stable. Experimental results from applying the recursive binary scheme to a set of modified matrices from the Harwell-Boeing collection are given. We conclude that when A has a small number of dense rows relative to its dimension, there is a significant gain in sparsity of the factor R. A crude estimate of the optimal number of splits is obtained by analysing a simple model problem. Copyright (C) 2000 John Wiley & Sons, Ltd.

Place, publisher, year, edition, pages
2000. Vol. 7, no 2, 51-65 p.
Keyword [en]
matrix stretching, linear least squares, sparse problems, dense rows
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:liu:diva-49759OAI: oai:DiVA.org:liu-49759DiVA: diva2:270655
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-12

Open Access in DiVA

No full text

In the same journal
Numerical Linear Algebra with Applications
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 52 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf