×

zbMATH — the first resource for mathematics

Preconditioning linear least-squares problems by identifying a basis matrix. (English) Zbl 1325.65041

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65F08 Preconditioners for iterative methods
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. R. Amestoy, I. S. Duff, and C. Puglisi, Multifrontal QR factorization in a multiprocessor environment, Numer. Linear Algebra Appl., 3 (1996), pp. 275–300. · Zbl 0907.65040
[2] M. Arioli and G. Manzini, Null space algorithm and spanning trees in solving Darcy’s equation, BIT, 43 (2003), pp. 839–848. · Zbl 1046.65017
[3] M. Arioli and G. Manzini, A network programming approach in solving Darcy’s equations by mixed finite-element methods, Electron. Trans. Numer. Anal., (2006), pp. 41–70. · Zbl 1112.65023
[4] M. Arioli and D. Orban, Iterative Methods for Symmetric Quasi-Definite Linear Systems Part I: Theory, Technical Report Cahier du GERAD G-2013-32, GERAD, Montreal, Quebec, 2013. · Zbl 1409.65004
[5] M. Benzi and M. T\accent23uma, 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
[6] \AA. Björck, Conjugate gradient method for symmetric quasi-definite linear systems, private communication.
[7] \AA. Björck, Stability analysis of the method of seminormal equations for least squares problems, Linear Algebra Appl., 88/89 (1987), pp. 31–48. · Zbl 0616.65043
[8] \AA. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996.
[9] \AA. Björck and J. Yuan, Preconditioners for least squares problems by LU factorization, Electron. Trans. Numer. Anal., 8 (1999), pp. 26–35.
[10] F. Brezzi and M. Fortin, Mixed and Hybrid Finite Element Methods, Springer Ser. Comput. Math. 15, Springer-Verlag, New York, 1991. · Zbl 0788.73002
[11] T. A. Davis, Algorithm \(915\), SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, ACM Trans. Math. Software, 38 (2011), article 8. · Zbl 1365.65122
[12] T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), article 1. · Zbl 1365.65123
[13] H. S. Dollar and A. J. Wathen, Approximate factorization constraint preconditioners for saddle-point matrices, SIAM J. Sci. Comput., 27 (2006), pp. 1555–1572. · Zbl 1105.65047
[14] B. Fischer, Polynomial Based Iteration Methods for Symmetric Linear Systems, SIAM, Philadephia, 2011. · Zbl 1223.65023
[15] R. W. Freund, G. H. Golub, and N. M. Nachtigal, Iterative solutions of linear systems, Acta Numer., 1 (1992), pp. 57–100. · Zbl 0762.65019
[16] G. Gallo and S. Pallottino, Shortest path methods: A unifying approach, Math. Programming Stud., 26 (1986), pp. 38–64. · Zbl 0605.90123
[17] A. George, K. Ikramov, and A. B. Kucherov, Some properties of symmetric quasi-definite matrices, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1318–1323. · Zbl 0960.65038
[18] P. E. Gill, W. Murray, and M. A. Saunders, SNOPT: An SQP aloprithm for large-scale constrained optimization, SIAM Rev., 47 (2005), pp. 99–131. · Zbl 1210.90176
[19] P. E. Gill, M. A. Saunders, and J. R. Shinnerl, On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Optim., 17 (1996), pp. 35–46. · Zbl 0878.49020
[20] G. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), pp. 205–224. · Zbl 0194.18201
[21] S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, How to Find a Good Submatrix, technical report, 2008. · Zbl 1215.65078
[22] S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, How to Find a Good Submatrix, in Matrix Methods: Theory, Algorithms, Applications, V. Olshevsky and E. Tyrtyshnikov, eds., World Scientific, Hackensack, NJ, 2010, pp. 247–256. · Zbl 1215.65078
[23] S. A. Goreinov and E. E. Tyrtyshnikov, The maximal-volume concept in approximation by low-rank matrices, Contemp. Math., 208 (2001), pp. 47–51. · Zbl 1003.15025
[24] S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudoskeleton approximations, Linear Algebra Appl., 261 (1997), pp. 1–21. · Zbl 0877.65021
[25] M. Hegland, On the computation of breeding values, in Proceedings of CONPAR 90–VAPP IV Joint International Conference on Vector and Parallel Processing, H. Burkhart, ed., Lecture Notes in Comput. Sci. 457, Springer-Verlag, Berlin, 1990, pp. 232–242.
[26] M. Hegland, Description and Use of Animal Breeding Data for Large Least Squares Problems, Technical Report TR/PA/93/50, CERFACS, Toulouse, France, 1993.
[27] HSL, HSL \(2013:\) A Collection of Fortran Codes for Large-Scale Scientific Computation, \burlhttp://www.hsl.rl.ac.uk, 2013.
[28] A. Jennings and M. Ajiz, Incomplete methods for solving \(A^T Ax = b\), SIAM J. Sci. Statist. Comput., 5 (1984), pp. 978–987. · Zbl 0559.65013
[29] D. E. Knuth, Semi-optimal bases for linear dependencies, Linear and Multilinear Algebra, 17 (1985), pp. 1–4. · Zbl 0556.15001
[30] 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
[31] H. M. Markowitz, The elimination form of the inverse and its application to linear programming, Management Sci., 3 (1957), pp. 255–269. · Zbl 0995.90592
[32] K. G. Murthy, Network Programming, Prentice-Hall, Englewood Cliffs, NJ, 1992.
[33] 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
[34] C. C. Paige and M. A. Saunders, Toward a generalized singular value decomposition, SIAM J. Numer. Anal., 18 (1981), pp. 398–405. · Zbl 0471.65018
[35] M. Saunders, Sparse least squares by conjugate gradients: A comparison of preconditioning methods, in Proceedings of Computer Science and Statistics: 12th Annual Symposium on the Interface, J. F. Gentleman, ed., AMS-IMS-SIAM Summer Research Conferences, University of Waterloo, Waterloo, Ontario, 1979, pp. 15–20; available online at http://stanford.edu/group/SOL/classics/saunders1979-LUpreconditioning.pdf.
[36] M. A. Saunders, Solution of sparse rectangular systems using LSQR and CRAIG, BIT, 35 (1995), pp. 588–604. · Zbl 0844.65029
[37] M. A. Saunders, LUSOL: Sparse LU for \(Ax = b\), \burlhttp://web.stanford.edu/group/SOL/software/lusol/, 2009.
[38] D. S. Scott, How to make the Lanczos algorithm converge slowly, Math. Comp., 33 (1979), pp. 239–247. · Zbl 0405.65016
[39] R. E. Tarjan, Data Structures and Network Algorithms, SIAM, Philadelphia, 1983. · Zbl 0584.68077
[40] A. Taylor and D. J. Higham, CONTEST: A controllable test matrix toolbox for MATLAB, ACM Trans. Math. Software, 35 (2009), article 26.
[41] R. J. Vanderbei, Symmetric quasi-definite 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.