MIQR: A multilevel incomplete QR preconditioner for large sparse least-squares problems

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

This paper describes a multilevel incomplete QR factorization for solving large sparse least-squares problems. The algorithm builds the factorization by exploiting structural orthogonality in general sparse) matrices. At any given step, the algorithm finds an independent set of columns, i.e., a set of columns that have orthogonal patterns. The other columns are then block orthogonalized against columns of the independent set, and the process is repeated recursively for a certain number of levels on these remaining columns. The final level matrix in processed with a standard QR or incomplete QR factorization. Dropping strategies are employed throughout the levels in order to maintain a good level of sparsity. A few improvements to this basic scheme are explored. Among these is the relaxation of the requirement of independent sets of columns. Numerical tests are proposed which compare this scheme with the standard incomplete QR preconditioner, the robust incomplete factorization preconditioncr. and the algebraic recursive multilevel solver (on normal equations).

Original languageEnglish (US)
Pages (from-to)524-550
Number of pages27
JournalSIAM Journal on Matrix Analysis and Applications
Volume28
Issue number2
DOIs
StatePublished - 2006

Keywords

  • CGLS
  • Incomplete QR
  • Iterative mothods
  • Large least-squares problems
  • Multilevel incomplete QR factorization
  • Normal equations
  • Orthogonal factorization
  • Preconditioning
  • QR factorization

Fingerprint Dive into the research topics of 'MIQR: A multilevel incomplete QR preconditioner for large sparse least-squares problems'. Together they form a unique fingerprint.

Cite this