Pseudoinverse preconditioners and iterative methods for large dense linear least-squares problems. (English) Zbl 1392.65025
Summary: We address the issue of approximating the pseudoinverse of the coefficient matrix for dynamically building preconditioning strategies for the numerical solution of large dense linear least-squares problems. The new preconditioning strategies are embedded into simple and well-known iterative schemes that avoid the use of the, usually ill-conditioned, normal equations. We analyze a scheme to approximate the pseudoinverse, based on Schulz iterative method, and also different iterative schemes, based on extensions of Richardson’s method, and the conjugate gradient method, that are suitable for preconditioning strategies. We present preliminary numerical results to illustrate the advantages of the proposed schemes.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 15A09 | Theory of matrix inversion and generalized inverses |
Keywords:
Schulz method; pseudoinverse; linear least-squares problems; preconditioned Richardson’s method; conjugate gradient methodSoftware:
MatlabReferences:
| [1] | Gambin, A.; Slonimski, P. R., Hierarchical clustering based upon contextual alignment of proteins: a different way to approach phylogeny, Comptes Rendus Biologies, 328:11-22, 11-22, (2005) |
| [2] | Björck, A., Numerical methods for least squares problem, SIAM, Philadelphia, USA, (1996) · Zbl 0847.65023 |
| [3] | Saad, Y., Iterative methods for sparse linear systems, SIAM, Philadelphia, USA, (2003) · Zbl 1002.65042 |
| [4] | Saad, Y.; Sosonkina, M., Enhanced preconditioners for large sparse least squares problem, Technical report, University of Minnesota, USA, (2001) |
| [5] | Trefethen, L. N.; Bau, III, D., Numerical Linear Algebra, SIAM, Philadelphia, USA, (1997) · Zbl 0874.65013 |
| [6] | Saad, Y.; Van der Vorst, Iterative solutions of linear systems in the 20th century, Technical report, University of Minnesota, USA, (1999) |
| [7] | Fasshauer, G. E., Meshfree Approximation Methods with MATLAB, World Scientific Publisher, Singapore, (2007) · Zbl 1123.65001 |
| [8] | Forsman, K.; Gropp, W.; Kettunen, L.; Levine, D.; Salonen, J., Solution of dense systems of linear equations arising from integral equation formulations, Antennas and propagation magazine, 37:96-100, 96-100, (1995) |
| [9] | Yan, Y., Sparse preconditioned iterative methods for dense linear systems, SIAM J. Sci. Comp, 15:1190-1200, 1190-1200, (1994) · Zbl 0813.65067 |
| [10] | Baboulin, M.; Giraud, L.; Gratton, S.; Langou, J., Parallel tools for solving incremental dense least squares problems: application to space geodesy, Journal of Algorithms and Computational Technology, 3:117-133, 117-133, (2009) · Zbl 1226.65029 |
| [11] | Benzi, M.; Giraud, L.; All, G., Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics, Numerical Algorithms, 16:1-15, 1-15, (1997) · Zbl 0895.65017 |
| [12] | Freud, R. W.; Golub, G. H.; Nachtigal, N., Iterative solution of linear systems, Acta Numerica, 1:57-100, 57-100, (1992) · Zbl 0762.65019 |
| [13] | Golub, G.; Plemmons, R., Large scale geodetic least squares adjustment by dissection and orthogonal decomposition, Technical report, Stanford University, USA, (1979) |
| [14] | Kariya, T.; Kurata, H., Generalized Least Squares, John Wiley and Sons Ltd., (2004) · Zbl 1057.62049 |
| [15] | Brezinski, C., Variations on Richardson’s method and acceleration, Bull. Soc. Math. Belg., pp.33-44, 33-44, (1996) · Zbl 0863.65011 |
| [16] | Brezinski, C., Projection methods for systems of equations, North Holland, Amsterdam, (1997) · Zbl 0867.65009 |
| [17] | Schulz, G., Iterative berechnung del reziproken matrix, Z. Angew. Math. Mech., 13:57-59, 57-59, (1933) · JFM 59.0535.04 |
| [18] | Monsalve, M.; Raydan, M., Newton’s method and secant methods: A longstanding relationship from vectors to matrices, Portugaliae Mathematica, 68:431-475, 431-475, (2011) · Zbl 1248.65051 |
| [19] | Héron, B.; Issard-Roch, F.; Picard, C., Analyse numérique, Dunod, Paris, (1999) |
| [20] | Householder, A. S., The Theory of Matrices in Numerical Analysis, Dover Publications, Inc., New York, (1975) · Zbl 0329.65003 |
| [21] | Opfer, G.; Schober, G., {Richardson’s} iteration for nonsymmetric matrices, Linear Algebra Appl, 58:343-361, 343-361, (1984) · Zbl 0565.65012 |
| [22] | Young, D. M., On {Richardson’s} method for solving linear systems with positive definite matrices, J. Math Phys, 32:243-255, 243-255, (1954) · Zbl 0055.11202 |
| [23] | La Cruz, W.; Raydan, M., Residual iterative schemes for large-scale nonsymmetric positive definite linear systems, Computational and applied mathematics, 49:151-173, 151-173, (2008) · Zbl 1167.65018 |
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.
