×

zbMATH — the first resource for mathematics

On using Cholesky-based factorizations and regularization for solving rank-deficient sparse linear least-squares problems. (English) Zbl 1372.65094

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Arioli, I. S. Duff, and P. P. M. Rijk, On the augmented system approach to sparse least-squares problem, Numer. Math., 55 (1989), pp. 667–684, . · Zbl 0678.65024
[2] M. Benzi, Preconditioning techniques for large linear systems: A survey, J. Comput. Phys., 182 (2002), pp. 418–477, . · Zbl 1015.65018
[3] \AA. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996, .
[4] R. Bru, J. Marín, J. Mas, and M. T\ruma, Preconditioned iterative methods for solving linear least squares problems, SIAM J. Sci. Comput., 36 (2014), pp. A2002–A2022, .
[5] A. Buttari, Fine-grained multithreading for the multifrontal \(QR\) factorization of sparse matrices, SIAM J. Sci. Comput., 35 (2013), pp. C323–C345, . · Zbl 1362.65031
[6] Y. Chen, T. A. Davis, W. H. Hager, and S. Rajamanickam, Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate, ACM Trans. Math. Software, 35 (2008), pp. 22:1–22:14, .
[7] E. Chow and A. Patel, Fine-grained parallel incomplete LU factorization, SIAM J. Sci. Comput., 37 (2015), pp. C169–C193, . · Zbl 1320.65048
[8] E. Chow and Y. Saad, Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 86 (1997), pp. 387–414, . · Zbl 0891.65028
[9] T. A. Davis, Algorithm 915: SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, ACM Trans. Math. Software, 38 (2011), pp. 8:1–8:22, . · Zbl 1365.65122
[10] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Software, 38 (2011), pp. 1:1–1:25, . · Zbl 1365.65123
[11] I. S. Duff, MA57—A code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Software, 30 (2004), pp. 118–154, . · Zbl 1070.65525
[12] I. S. Duff, N. I. M. Gould, J. K. Reid, J. A. Scott, and K. Turner, The factorization of sparse symmetric indefinite matrices, IMA J. Numer. Anal., 11 (1991), pp. 181–204, . · Zbl 0739.65018
[13] I. S. Duff and J. Koster, The design and use of algorithms for permuting large entries to the diagonal of sparse matrices, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 889–901, . · Zbl 0947.65048
[14] D. C.-L. Fong and M. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput., 33 (2011), pp. 2950–2971, . · Zbl 1232.65052
[15] A. George and M. A. Saunders, Solution of Sparse Linear Equations Using Cholesky Factors of Augmented Systems, Research Report SOL 99-1, Department of EESOR, Stanford University, Stanford, CA, 1999.
[16] P. E. Gill, W. Murray, D. B. Ponceleón, and M. A. Saunders, Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 292–311, . · Zbl 0749.65037
[17] P. E. Gill, M. A. Saunders, and J. R. Shinnerl, On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 35–46, . · Zbl 0878.49020
[18] G. H. Golub and C. F. Van Loan, Unsymmetric positive definite linear systems, Linear Algebra Appl., 28 (1979), pp. 85–97, . · Zbl 0419.65025
[19] N. I. M. Gould, D. Orban, and Ph. L. Toint, CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl., 60 (2015), pp. 545–557, . · Zbl 1325.90004
[20] N. I. M. Gould and J. A. Scott, The State-of-the-Art of Preconditioners for Sparse Linear Least Squares Problems: The Complete Results, Technical Report RAL-TR-2015-009, Rutherford Appleton Laboratory, Oxfordshire, UK, 2015; available online at .
[21] N. I. M. Gould and J. A. Scott, The state-of-the-art of preconditioners for sparse linear least-squares problems, ACM Trans. Math. Software, 43 (2017), pp. 36:1–36:35, . · Zbl 1380.65064
[22] C. Greif, S. He, and P. Liu, SYM-ILDL: Incomplete \(LDL^T\) Factorization of Symmetric Indefinite and Skew-Symmetric Matrices, Technical report, Department of Computer Science, The University of British Columbia, Vancouver, Canada, 2015; software available from . · Zbl 1380.65061
[23] A. Gupta, WSMP Watson Sparse Matrix Package (Part II: Direct Solution of General Sparse Systems), Technical Report RC 21888 (98472), IBM T. J. Watson Research Center, Yorktown Heights, NY, 2000.
[24] J. D. Hogg, E. Ovtchinnikov, and J. A. Scott, A sparse symmetric indefinite direct solver for GPU architectures, ACM Trans. Math. Software, 42 (2016), pp. 1:1–1:25, . · Zbl 1347.65086
[25] J. D. Hogg, J. K. Reid, and J. A. Scott, Design of a multicore sparse Cholesky factorization using DAGs, SIAM J. Sci. Comput., 32 (2010), pp. 3627–3649, . · Zbl 1221.65088
[26] J. D. Hogg and J. A. Scott, The Effects of Scalings on the Performance of a Sparse Symmetric Indefinite Solver, Technical Report RAL-TR-2008-007, Rutherford Appleton Laboratory, Oxfordshire, UK, 2008.
[27] J. D. Hogg and J. A. Scott, HSL_MA97: A Bit-Compatible Multifrontal Code for Sparse Symmetric Systems, Technical Report RAL-TR-2011-024, Rutherford Appleton Laboratory, Oxfordshire, UK, 2011; available online at .
[28] J. D. Hogg and J. A. Scott, A Study of Pivoting Strategies for Tough Sparse Indefinite Systems, Technical Report RAL-TR-2012-009, Rutherford Appleton Laboratory, Oxfordshire, UK, 2012; available online at . · Zbl 1295.65054
[29] J. D. Hogg and J. A. Scott, New parallel sparse direct solvers for multicore architectures, Algorithms, 6 (2013), pp. 702–725, .
[30] J. D. Hogg and J. A. Scott, Pivoting strategies for tough sparse indefinite systems, ACM Trans. Math. Software, 40 (2013), pp. 4:1–4:19, . · Zbl 1295.65054
[32] G. Karypis and V. Kumar, METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices (Version 4.0), Technical report, Department of Computer Science and Army HPC Research Center, University of Minnesota, Minneapolis, MN, 1998.
[33] N. Li and Y. Saad, Crout versions of ILU factorization with pivoting for sparse symmetric matrices, Electron. Trans. Numer. Anal., 20 (2005), pp. 75–85. · Zbl 1075.65045
[34] N. Li and Y. Saad, 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
[35] C.-J. Lin and J. J. Moré, Incomplete Cholesky factorizations with limited memory, SIAM J. Sci. Comput., 21 (1999), pp. 24–45, . · Zbl 0941.65033
[36] K. Morikuni and K. Hayami, Inner-iteration Krylov subspace methods for least squares problems, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1–22, . · Zbl 1269.65039
[37] K. Morikuni and K. Hayami, Convergence of inner-iteration GMRES methods for rank-deficient least squares problems, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 225–250, . · Zbl 1315.65041
[39] D. Orban, Limited-memory LDL\(^{\mathsf{T}}\) factorization of symmetric quasi-definite matrices with application to constrained optimization, Numer. Algorithms, 70 (2015), pp. 9–41, . · Zbl 1325.65042
[40] C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617–629, . · Zbl 0319.65025
[41] C. C. Paige and M. A. Saunders, Algorithm 583: LSQR: Sparse linear equations and least squares problems, ACM Trans. Math. Software, 8 (1982), pp. 195–209, .
[42] C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8 (1982), pp. 43–71, . · Zbl 0478.65016
[44] J. K. Reid and J. A. Scott, An out-of-core sparse Cholesky solver, ACM Trans. Math. Software, 36 (2009), pp. 9:1–9:33, . · Zbl 1364.65071
[45] D. Ruiz, A Scaling Algorithm to Equilibrate both Rows and Columns Norms in Matrices, Technical Report RAL-TR-2001-034, Rutherford Appleton Laboratory, Oxfordshire, UK, 2001.
[46] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003, . · Zbl 1031.65046
[47] Y. Saad and M. H. Schulz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856–869, . · Zbl 0599.65018
[48] M. A. Saunders, Solution of sparse rectangular systems using LSQR and CRAIG, BIT, 35 (1995), pp. 588–604, . · Zbl 0844.65029
[49] M. A. Saunders, Cholesky-based methods for sparse least squares: The benefits of regularization, in Linear and Nonlinear Conjugate Gradient-Related Methods, Proceedings of the AMS-IMS-SIAM Summer Research Conference, L. Adams and J. L. Nazareth, eds., SIAM, Philadelphia, 1996, pp. 92–100. · Zbl 0865.65022
[50] J. Scott and M. T\ruma, 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
[51] J. Scott and M. T\ruma, On positive semidefinite modification schemes for incomplete Cholesky factorization, SIAM J. Sci. Comput., 36 (2014), pp. A609–A633, . · Zbl 1298.65049
[52] J. Scott and M. T\ruma, On signed incomplete Cholesky factorization preconditioners for saddle-point systems, SIAM J. Sci. Comput., 36 (2014), pp. A2984–A3010, .
[53] J. Scott and M. T\ruma, Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners, Numer. Linear Algebra Appl., (2017), .
[54] S. W. Sloan, An algorithm for profile and wavefront reduction of sparse matrices, Internat. J. Numer. Methods Engrg., 23 (1986), pp. 239–251, . · Zbl 0601.65027
[55] A. van der Sluis, Condition numbers and equilibration of matrices, Numer. Math., 14 (1969), pp. 14–23, . · Zbl 0182.48906
[56] R. J. Vanderbei, Symmetric quasidefinite matrices, SIAM J. Optim., 5 (1995), pp. 100–113, . · Zbl 0822.65017
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.