×

zbMATH — the first resource for mathematics

A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows. (English) Zbl 1406.65015
To solve a large linear least squares problem \(Ax=b\), \(A\in\mathbb{R}^{m\times n}\), \(m\geq n\), in which \(A\) consists of sparse rows \(A_s\) and nearly dense rows \(A_d\), it is worthwhile to treat these separately. In their previous paper [SIAM J. Sci. Comput. 39, No. 6, A2422–A2437 (2017; Zbl 1377.65050)], the authors have considered preconditioned iterative methods to deal with the dense part. In this paper, they use a Schur complement method instead. After eliminating \(r_s\), the sparse part of the residual, the reduced augmented normal equations have a \(2\times 2\) block matrix \(K\). The Schur complement method gives a block \(LDL^T\) factorization of \(K\). An incomplete Cholesky factor of \(\tilde{C}_s=C_s+\alpha I\) is used to approximate the Cholesky factor of \(C_s=A_s^TA_s\) (Tikhonov regularization). These replace the true factors in the Schur complement method which serves as a preconditioner. After solving the approximate system, only a few iterative steps are needed to solve the original problem. It is efficient to explicitly separate the zero columns in \(A_s\) from those that are not. If the size of \(\tilde{C}_s\) (the number of dense rows) becomes too large for a direct method, an iterative method can be used instead. Both the direct and the iterative methods are tested on a number of realistic problems.

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65F10 Iterative numerical methods for linear systems
65K05 Numerical mathematical programming methods
65F50 Computational methods for sparse matrices
65F08 Preconditioners for iterative methods
65F20 Numerical solutions to overdetermined systems, pseudoinverses
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, E.D., Gondzio, J, Mészáros, C., Xu, X.: Implementation of Interior Point Methods for Large Scale Linear Programming. HEC/Université de Genève (1996) · Zbl 0874.90127
[2] Andersen, K.D: A modified Schur complement method for handling dense columns in interior point methods for linear programming (1996) · Zbl 0884.65049
[3] Anderson, OD, An improved approach to inverting the autocovariance matrix of a general mixed autoregressive moving average time process, Australian J. Statist., 18, 73-75, (1976)
[4] Anderson, OD, On the inverse of the autocovariance matrix for a general moving average process, Biometrika, 63, 391-394, (1976) · Zbl 0329.62069
[5] Avron, H.; Ng, E.; Toledo, S., Using perturbed \(Q\)\(R\) factorizations to solve linear least-squares problems, SIAM J. Matrix Anal. Appl., 31, 674-693, (2009) · Zbl 1195.65048
[6] Benzi, M., Preconditioning techniques for large linear systems: a survey, J. Comput. Phys., 182, 418-477, (2002) · Zbl 1015.65018
[7] Björck, Å, A general updating algorithm for constrained linear least squares problems, SIAM J. Sci. Statist. Comput., 5, 394-402, (1984) · Zbl 0562.65018
[8] Björck, Å: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996) · Zbl 0734.65031
[9] Davis, Timothy A.; Hu, Yifan, The university of Florida sparse matrix collection, ACM Transactions on Mathematical Software, 38, 1-25, (2011) · Zbl 1365.65123
[10] Diniz, P.S.R.: Adaptive Filtering: Algorithms and Practical Implementation. Springer, 4th ed 2013 edition (2012) · Zbl 1257.93001
[11] Dollar, HS; Scott, JA, A note on fast approximate minimum degree orderings for matrices with some dense rows, Numer. Linear Algebra Appl., 17, 43-55, (2010) · Zbl 1240.65140
[12] Duff, IS, MA57—a code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Softw., 30, 118-154, (2004) · Zbl 1070.65525
[13] Fong, DC-L; Saunders, MA, LSMR: an iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput., 33, 2950-2971, (2011) · Zbl 1232.65052
[14] George, A.; Heath, MT, Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Appl., 34, 69-83, (1980) · Zbl 0459.65025
[15] Gill, P.E., Murray, W., Ponceleon, D.B., Saunders, M.A.: Solving reduced KKT systems in barrier methods for linear and quadratic programming. Technical Report SOL 91-7, Department of Operations Research Stanford University (1991) · Zbl 0815.65080
[16] Gill, PE; Saunders, MA; Shinnerl, JR, On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Matrix Anal. Appl., 17, 35-46, (1996) · Zbl 0878.49020
[17] Goldfarb, D.; Scheinberg, K., A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming, Math. Program. Series A, 99, 1-34, (2004) · Zbl 1055.90090
[18] Golub, GH; Loan, CF, Unsymmetric positive definite linear systems, Linear Algebra Appl., 28, 85-97, (1979) · Zbl 0419.65025
[19] Gould, NIM; Orban, D.; Toint, PhL, CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl., 60, 545-557, (2015) · Zbl 1325.90004
[20] Gould, NIM; Scott, JA, The state-of-the-art of preconditioners for sparse linear least squares problems, ACM Trans. Math. Softw., 43, 36,1-35, (2017) · Zbl 1380.65064
[21] Greif, C., He, S., Liu, P.: SYM-ILDL C++ package for incomplete factorizations of symmetric indefinite matrices https://github.com/inutard/matrix-factor (2013)
[22] Hogg, JD; Reid, JK; Scott, JA, Design of a multicore sparse Cholesky factorization using DAGs, SIAM J. Sci. Comput., 32, 3627-3649, (2010) · Zbl 1221.65088
[23] Hogg, J.D., Scott, J.A.: HSL_MA97: A bit-compatible multifrontal code for sparse symmetric systems. Technical Report RAL-TR-2011-024 Rutherford Appleton Laboratory (2011)
[24] HSL: A collection of Fortran codes for large-scale scientific computation. http://www.hsl.rl.ac.uk (2017)
[25] Kalman, RE, A new approach to linear filtering and prediction problems, Trans. ASME-J. Basic Eng., 82, 35-45, (1960)
[26] Karypis, G., Kumar, V.: METIS: software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices (version 3.0). Technical report, University of Minnesota Department of Computer Science and Army HPC Research Center (1997)
[27] Lin, C-J; Moré, JJ, Incomplete Cholesky factorizations with limited memory, SIAM J. Sci. Comput., 21, 24-45, (1999) · Zbl 0941.65033
[28] Lustig, IJ; Marsten, RE; Shanno, DF, Computational experience with a primal-dual interior point method for linear programming, Linear Algebra Appl., 152, 191-222, (1991) · Zbl 0731.65049
[29] Manteuffel, TA, An incomplete factorization technique for positive definite linear systems, Math. Comput., 34, 473-497, (1980) · Zbl 0422.65018
[30] Marxen, A.: Primal barrier methods for linear programming. Technical Report SOL 89-6, Department of Operations Research Stanford University (1989)
[31] MUMPS: A MUltifrontal Massively Parallel sparse direct Solver. http://graal.ens-lyon.fr/MUMPS/ (2016)
[32] Ng, E., A scheme for handling rank-deficiency in the solution of sparse linear least squares problems, SIAM J. Sci. Statist. Comput., 12, 1173-1183, (1991) · Zbl 0733.65024
[33] Okulicka-DłuŻewska, F.; Rozložník, M.; Smoktunowicz, A., Cholesky-like factorization of symmetric indefinite matrices and orthogonalization with respect to bilinear forms, SIAM J. Matrix Anal. Appl., 36, 727-751, (2015) · Zbl 1317.65105
[34] Orban, D., Limited-memory LDL⊤ factorization of symmetric quasi-definite matrices with application to constrained optimization, Numer. Algor., 70, 9-41, (2015) · Zbl 1325.65042
[35] Orban, D., Arioli, M.: Iterative Solution of Symmetric Quasi-Definite Linear Systems, volume 3 of SIAM Spotlights Society for Industrial and Applied Mathematics. SIAM, Philadelphia (2017) · Zbl 1409.65004
[36] Paige, CC; Saunders, MA, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629, (1975) · Zbl 0319.65025
[37] Paige, CC; Saunders, MA, Algorithm 583; LSQR: Sparse linear equations and least-squares problems, ACM Trans. Math. Softw., 8, 195-209, (1982)
[38] Paige, CC; Saunders, MA, LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw., 8, 43-71, (1982) · Zbl 0478.65016
[39] Reid, JK; Scott, JA, An out-of-core sparse Cholesky solver, ACM Trans. Math. Softw., 36, 9,1-9,33, (2009) · Zbl 1364.65071
[40] Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003) · Zbl 1002.65042
[41] Saad, Y.; Schultz, MH, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869, (1986) · Zbl 0599.65018
[42] Saunders, M.A.: Cholesky-based methods for sparse least squares: The benefits of regularization. Technical Report SOL 95-1, Department of Operations Research, Stanford University, 1995. In: Adams, L., Nazareth, J. L. (eds.) Linear and Nonlinear Conjugate Gradient-Related Methods, pp 92-100. SIAM, Philadelphia (1996)
[43] Sayed, A.H: Fundamentals of Adaptive Filtering. Wiley (2003)
[44] Scott, JA, On using Cholesky-based factorizations for solving rank-deficient sparse linear least-squares problems, SIAM J. Sci. Comput., 39, c319-c339, (2017) · Zbl 1372.65094
[45] Scott, JA; Tůma, M., HSL_MI28: an efficient and robust limited-memory incomplete Cholesky factorization code, ACM Trans. Math. Softw, 40, 24,1-19, (2014) · Zbl 1371.65031
[46] Scott, JA; Tůma, M., On positive semidefinite modification schemes for incomplete Cholesky factorization, SIAM J. Sci. Comput., 36, a609-a633, (2014) · Zbl 1298.65049
[47] Scott, JA; Tůma, M., On signed incomplete Cholesky factorization preconditioners for saddle-point systems, SIAM J. Sci. Comput., 36, a2984-a3010, (2014) · Zbl 1310.65036
[48] Scott, JA; Tůma, M., Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods, SIAM J. Sci. Comput., 39, a2422-a2437, (2017) · Zbl 1377.65050
[49] Sun, C.: Dealing with dense rows in the solution of sparse linear least squares problems. Research Report CTC95TR227, Advanced Computing Research Institute Cornell Theory Center; Cornell University (1995)
[50] Sun, C., Parallel solution of sparse linear least squares problems on distributed-memory multiprocessors, Parallel Comput., 23, 2075-2093, (1997) · Zbl 0903.68095
[51] Vanderbei, RJ, Splitting dense columns in sparse linear systems, Linear Algebra Appl., 152, 107-117, (1991) · Zbl 0727.65034
[52] Vanderbei, RJ, Symmetric quasidefinite matrices, SIAM J. Optim., 5, 100-113, (1995) · Zbl 0822.65017
[53] WSMP: Watson sparse matrix package (WSMP). http://researcher.watson.ibm.com/researcher/view_group.php?id=1426 (2016)
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.