×

Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations. (English) Zbl 1348.65066

Summary: The efficient solution of the normal equations corresponding to a large sparse linear least squares problem can be extremely challenging. Robust incomplete factorization (RIF) preconditioners represent one approach that has the important feature of computing an incomplete \(LL^T\) factorization of the normal equations matrix without having to form the normal matrix itself. The right-looking implementation of Benzi and Tuma has been used in a number of studies but experience has shown that in some cases it can be computationally slow and its memory requirements are not known a priori. Here a new left-looking variant is presented that employs a symbolic preprocessing step to replace the potentially expensive searching through entries of the normal matrix. This involves a directed acyclic graph (DAG) that is computed as the computation proceeds. An inexpensive but effective pruning algorithm is proposed to limit the number of edges in the DAG. Problems arising from practical applications are used to compare the performance of the right-looking approach with a left-looking implementation that computes the normal matrix explicitly and our new implicit DAG-based left-looking variant.

MSC:

65F08 Preconditioners for iterative methods
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices
15A06 Linear equations (linear algebraic aspects)
15A23 Factorization of matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. V. Aho, M. R. Garey, and J. D. Ullman, {\it The transitive reduction of a directed graph}, SIAM J. Comput., 1 (1972), pp. 131-137. · Zbl 0247.05128
[2] M. Arioli and I. S. Duff, {\it Preconditioning linear least-sqaures problems by identifying a basis matrix}, SIAM J. Sci. Comput., 37 (2015), pp. S544-S561. · Zbl 1325.65041
[3] H. Avron, P. Maymounkov, and S. Toledo, {\it Blendenpik: Supercharging LAPACK’s least squares solver}, SIAM J. Sci. Comput., 32 (2010), pp. 1217-1236. · Zbl 1213.65069
[4] C. Benoit, {\it Note sur une méthode de résolution des équations normales provenant de l’application de la méthode des moindres carrés a un systeme d’équations linéaires en nombre inférieur a celui des inconnues. application de la méthode a la résolution d’un systeme défini d’équations linéaires}, Bull. Géodésique, 2 (1924), pp. 5-77.
[5] M. Benzi, J. K. Cullum, and M. Tůma, {\it Robust approximate inverse preconditioning for the conjugate gradient method}, SIAM J. Sci. Comput., 22 (2000), pp. 1318-1332. · Zbl 0985.65035
[6] M. Benzi, C. D. Meyer, and M. Tůma, {\it A sparse approximate inverse preconditioner for the conjugate gradient method}, SIAM J. Sci. Comput., 17 (1996), pp. 1135-1149. · Zbl 0856.65019
[7] M. Benzi and M. Tůma, {\it Orderings for factorized sparse approximate inverse preconditioners}, SIAM J. Sci. Comput., 21 (2000), pp. 1851-1868. · Zbl 0959.65047
[8] M. Benzi and M. Tůma, {\it A robust incomplete factorization preconditioner for positive definite matrices}, Numer. Linear Algebra Appl., 10 (2003), pp. 385-400. · Zbl 1071.65528
[9] M. Benzi and M. Tůma, {\it A robust preconditioner with low memory requirements for large sparse least squares problems}, SIAM J. Sci. Comput., 25 (2003), pp. 499-512. · Zbl 1042.65030
[10] \AA. Björck, {\it Numerical Methods for Least Squares Problems}, SIAM, Philadelphia, 1996. · Zbl 0847.65023
[11] A. Björck and J. Y. Yuan, {\it Preconditioners for least squares problems by \(LU\) factorization}, Electron. Trans. Numer. Anal., 8 (1999), pp. 26-35. · Zbl 0924.65034
[12] R. Bridson and W.-P. Tang, {\it Ordering, anisotropy, and factored sparse approximate inverses}, SIAM J. Sci. Comput., 21 (1999), pp. 867-882. · Zbl 0955.65018
[13] R. Bridson and W.-P. Tang, {\it Refining an approximate inverse}, J. Comput. Appl. Math., 123 (2000), pp. 293-306. · Zbl 0982.65035
[14] R. Bru, J. Marín, J. Mas, and M. Tůma, {\it Preconditioned iterative methods for solving linear least squares problems}, SIAM J. Sci. Comput., 36 (2014), pp. A2002-A2022. · Zbl 1303.65021
[15] T. A. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Software, 38 (2011), pp. 1:1-1:25. · Zbl 1365.65123
[16] J. E. Dennis, Jr. and R. B. Schnabel, {\it Numerical Methods for Unconstrained Optimization and Nonlinear Equations}, Classics in Appl. Math. 16, SIAM, Philadelphia, 1996.
[17] I. S. Duff, {\it MA28–A Set of Fortran Subroutines for Sparse Unsymmetric Linear Equations}, Harwell Report UK AERE-R.8730, Harwell Laboratories, 1980.
[18] I. S. Duff and J. K. Reid, {\it The multifrontal solution of indefinite sparse symmetric linear equations}, ACM Trans. Math. Software, 9 (1983), pp. 302-325. · Zbl 0515.65022
[19] S. Eisenstat and J.-W. H. Liu, {\it The theory of elimination trees for sparse unsymmetric matrices}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 686-705. · Zbl 1079.65025
[20] S. C. Eisenstat, M. C. Gursky, M. H. Schultz, and A. H. Sherman, {\it The Yale Sparse Matrix Package (YSMP)—{\it I}: The symmetric codes}, Internat. J. Numer. Methods Engrg., 18 (1982), pp. 1145-1151. · Zbl 0492.65012
[21] S. C. Eisenstat and J.-W. H. Liu, {\it Exploiting structural symmetry in unsymmetric sparse symbolic factorization}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 202-211. · Zbl 0746.65023
[22] J. R. Gilbert, {\it Predicting structure in sparse matrix computations}, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 62-79. · Zbl 0796.65061
[23] J. R. Gilbert and J. W. H. Liu, {\it Elimination structures for unsymmetric sparse LU factors}, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 334-352. · Zbl 0769.65010
[24] J. R. Gilbert and T. Peierls, {\it Sparse partial pivoting in time proportional to arithmetic operations}, SIAM J. Sci. Statist. Comput., 9 (1988), pp. 862-874. · Zbl 0656.65036
[25] N. I. M. Gould, D. Orban, and P. L. Toint, {\it CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization}, Comput. Optim. Appl., 60 (2015), pp. 545-557. · Zbl 1325.90004
[26] N. I. M. Gould and J. A. Scott, {\it The State-of-the-Art of Preconditioners for Sparse Linear Least Squares Problems}, Technical Report RAL-P-2015-010, Rutherford Appleton Laboratory, 2015. · Zbl 1380.65064
[27] N. I. M. Gould and J. A. Scott, {\it The State-of-the-Art of Preconditioners for Sparse Linear Least Squares Problems: The Complete Results}, Technical Report RAL-TR-2015-009 (revision 1), Rutherford Appleton Laboratory, 2016.
[28] M. R. Hestenes and E. Stiefel, {\it Methods of conjugate gradients for solving linear systems}, J. Res. National Bureau of Standards, 49 (1952), pp. 409-435. · Zbl 0048.09901
[29] HSL, {\it A Collection of Fortran Codes for Large-Scale Scientific Computation}, (2016).
[30] A. Jennings and M. A. Ajiz, {\it Incomplete methods for solving \(A^TAx=b\)}, SIAM J. Sci. Statist. Comput., 5 (1984), pp. 978-987. · Zbl 0559.65013
[31] J. Kopal, M. Rozložník, A. Smoktunowicz, and M. Tůma, {\it Rounding error analysis of orthogonalization with a non-standard inner product}, BIT, 52 (2012), pp. 1035-1058. · Zbl 1259.65069
[32] P. Läuchli, {\it Jordan-Elimination und Ausgleichung nach kleinsten Quadraten}, Numer. Math., 3 (1961), pp. 226-240. · Zbl 0117.10902
[33] N. Li and Y. Saad, {\it MIQR: A multilevel incomplete QR preconditioner for large sparse least-squares problems}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 524-550. · Zbl 1113.65036
[34] J. W. H. Liu, {\it The role of elimination trees in sparse factorizations}, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 134-172. · Zbl 0697.65013
[35] X. Meng, M. A. Saunders, and M. W. Mahoney, {\it LSRN: A parallel iterative solver for strongly over- or underdetermined systems}, SIAM J. Sci. Comput., 36 (2014), pp. C95-C118. · Zbl 1298.65053
[36] K. Morikuni and K. Hayami, {\it Inner-iteration Krylov subspace methods for least squares problems}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1-22. · Zbl 1269.65039
[37] O. Østerby and Z. Zlatev, {\it Direct Methods for Sparse Matrices}, Lecture Notes in Comput. Sci. 157, Springer-Verlag, Berlin, 1983. · Zbl 0516.65011
[38] A. T. Papadopoulus, I. S. Duff, and A. J. Wathen, {\it A class of incomplete orthogonal factorization methods. II: Implementation and results}, BIT, 45 (2005), pp. 159-179. · Zbl 1080.65028
[39] G. Peters and J. H. Wilkinson, {\it The least squares problem and pseudo-inverse}, Comput. J., 131 (1970), pp. 309-316. · Zbl 0195.44804
[40] Y. Saad, {\it Preconditioning techniques for nonsymmetric and indefinite linear systems}, J. Comput. Appl. Math., 24 (1988), pp. 89-105. · Zbl 0662.65028
[41] J. A. Scott and M. Tůma, {\it HSL_MI28: An efficient and robust limited-memory incomplete Cholesky factorization code}, ACM Trans. Math. Software, 40 (2014), pp. 24:1-24:19. · Zbl 1371.65031
[42] J. A. Scott and M. Tůma, {\it On positive semidefinite modification schemes for incomplete Cholesky factorization}, SIAM J. Sci. Comput., 36 (2014), pp. A609-A633. · Zbl 1298.65049
[43] X. Wang, K. A. Gallivan, and R. Bramley, {\it CIMGS: An incomplete orthogonal factorization preconditioner}, SIAM J. Sci. Comput., 18 (1997), pp. 516-536. · Zbl 0871.65033
[44] Z. Zlatev, {\it Computational Methods for General Sparse Matrices}, Kluwer, Dordrecht, the Netherlands, 1991. · Zbl 0746.65041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.