# 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
Full Text:
##### References:
  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  Andersen, K.D: A modified Schur complement method for handling dense columns in interior point methods for linear programming (1996) · Zbl 0884.65049  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)  Anderson, OD, On the inverse of the autocovariance matrix for a general moving average process, Biometrika, 63, 391-394, (1976) · Zbl 0329.62069  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  Benzi, M., Preconditioning techniques for large linear systems: a survey, J. Comput. Phys., 182, 418-477, (2002) · Zbl 1015.65018  Björck, Å, A general updating algorithm for constrained linear least squares problems, SIAM J. Sci. Statist. Comput., 5, 394-402, (1984) · Zbl 0562.65018  Björck, Å: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996) · Zbl 0734.65031  Davis, Timothy A.; Hu, Yifan, The university of Florida sparse matrix collection, ACM Transactions on Mathematical Software, 38, 1-25, (2011) · Zbl 1365.65123  Diniz, P.S.R.: Adaptive Filtering: Algorithms and Practical Implementation. Springer, 4th ed 2013 edition (2012) · Zbl 1257.93001  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  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  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  George, A.; Heath, MT, Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Appl., 34, 69-83, (1980) · Zbl 0459.65025  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  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  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  Golub, GH; Loan, CF, Unsymmetric positive definite linear systems, Linear Algebra Appl., 28, 85-97, (1979) · Zbl 0419.65025  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  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  Greif, C., He, S., Liu, P.: SYM-ILDL C++ package for incomplete factorizations of symmetric indefinite matrices https://github.com/inutard/matrix-factor (2013)  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  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)  HSL: A collection of Fortran codes for large-scale scientific computation. http://www.hsl.rl.ac.uk (2017)  Kalman, RE, A new approach to linear filtering and prediction problems, Trans. ASME-J. Basic Eng., 82, 35-45, (1960)  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)  Lin, C-J; Moré, JJ, Incomplete Cholesky factorizations with limited memory, SIAM J. Sci. Comput., 21, 24-45, (1999) · Zbl 0941.65033  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  Manteuffel, TA, An incomplete factorization technique for positive definite linear systems, Math. Comput., 34, 473-497, (1980) · Zbl 0422.65018  Marxen, A.: Primal barrier methods for linear programming. Technical Report SOL 89-6, Department of Operations Research Stanford University (1989)  MUMPS: A MUltifrontal Massively Parallel sparse direct Solver. http://graal.ens-lyon.fr/MUMPS/ (2016)  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  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  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  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  Paige, CC; Saunders, MA, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629, (1975) · Zbl 0319.65025  Paige, CC; Saunders, MA, Algorithm 583; LSQR: Sparse linear equations and least-squares problems, ACM Trans. Math. Softw., 8, 195-209, (1982)  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  Reid, JK; Scott, JA, An out-of-core sparse Cholesky solver, ACM Trans. Math. Softw., 36, 9,1-9,33, (2009) · Zbl 1364.65071  Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003) · Zbl 1002.65042  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  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)  Sayed, A.H: Fundamentals of Adaptive Filtering. Wiley (2003)  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  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  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  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  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  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)  Sun, C., Parallel solution of sparse linear least squares problems on distributed-memory multiprocessors, Parallel Comput., 23, 2075-2093, (1997) · Zbl 0903.68095  Vanderbei, RJ, Splitting dense columns in sparse linear systems, Linear Algebra Appl., 152, 107-117, (1991) · Zbl 0727.65034  Vanderbei, RJ, Symmetric quasidefinite matrices, SIAM J. Optim., 5, 100-113, (1995) · Zbl 0822.65017  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.