MIQR: a multilevel incomplete QR preconditioner for large sparse least-squares problems 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 is 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 preconditioner, and the algebraic recursive multilevel solver (on normal equations).

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Al Daas, Hussam; Jolivet, Pierre; Scott, Jennifer A.: A robust algebraic domain decomposition preconditioner for sparse normal equations (2022)
  2. Jiao, Xiangmin; Chen, Qiao: Approximate generalized inverses with iterative refinement for (\epsilon)-accurate preconditioning of singular systems (2022)
  3. Song, Sheng-Zhong; Huang, Zheng-Da: A modified SSOR-like preconditioner for non-Hermitian positive definite matrices (2021)
  4. Cerdán, J.; Guerrero, D.; Marín, J.; Mas, J.: Preconditioners for rank deficient least squares problems (2020)
  5. Gould, Nicholas; Scott, Jennifer: The state-of-the-art of preconditioners for sparse linear least-squares problems (2017)
  6. Scott, Jennifer: On using Cholesky-based factorizations and regularization for solving rank-deficient sparse linear least-squares problems (2017)
  7. Scott, Jennifer; Tuma, Miroslav: Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations (2016)
  8. Arioli, Mario; Duff, Iain S.: Preconditioning linear least-squares problems by identifying a basis matrix (2015)
  9. Aoto, Daisuke; Ishiwata, Emiko; Abe, Kuniyoshi: A variable preconditioned GCR((m)) method using the GSOR method for singular and rectangular linear systems (2010)
  10. Niu, Qiang; Lu, Lin-Zhang: Fourier analysis of frequency filtering decomposition preconditioners (2010)
  11. Li, Na; Saad, Yousef: MIQR: a multilevel incomplete QR preconditioner for large sparse least-squares problems (2006)