MIQR swMATH ID: 7242 Software Authors: Li, Na; Saad, Yousef Description: 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). Homepage: http://dl.acm.org/citation.cfm?id=1132367.1151269 Keywords: multilevel incomplete QR factorization; CGLS; QR factorization; orthogonal factorization; preconditioning; iterative methods; large least-squares problems; normal equations; numerical examples; algorithm Related Software: SparseMatrix; SuiteSparseQR; HSL; SuitSparseQR; LSQR; CRAIG; LSMR; CIMGS; HSL_MI28; CUTEst; HSL_MA87; MUMPS; CHOLMOD; SYM-ILDL; HSL_MA97; WSMP; MA57; ParILUT; hypre; qr_mumps Cited in: 12 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year MIQR: a multilevel incomplete QR preconditioner for large sparse least-squares problems. Zbl 1113.65036Li, Na; Saad, Yousef 2006 all top 5 Cited by 20 Authors 5 Scott, Jennifer A. 2 Tůma, Miroslav 1 Abe, Kuniyoshi 1 Aoto, Daisuke 1 Arioli, Mario 1 Cerdán, Juana 1 Chen, Qiao 1 Daas, Hussam Al 1 Duff, Iain S. 1 Gould, Nicholas Ian Mark 1 Huang, Zhengda 1 Ishiwata, Emiko 1 Jiao, Xiangmin 1 Jolivet, Pierre 1 Li, Na 1 Lu, Linzhang 1 Mas, José 1 Niu, Qiang 1 Saad, Yousef 1 Song, Sheng-Zhong all top 5 Cited in 7 Serials 4 SIAM Journal on Scientific Computing 2 Journal of Computational and Applied Mathematics 2 SIAM Journal on Matrix Analysis and Applications 1 ACM Transactions on Mathematical Software 1 Applied Mathematics and Computation 1 BIT 1 Applied Numerical Mathematics Cited in 4 Fields 12 Numerical analysis (65-XX) 1 Combinatorics (05-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Partial differential equations (35-XX) Citations by Year