Generalized approximate inverse preconditioners for least squares problems. (English) Zbl 1171.65390
Summary: This paper is concerned with a new approach for preconditioning large sparse least squares problems. Based on the idea of the approximate inverse preconditioner, which was originally developed for square matrices, we construct a generalized approximate inverse \(M\) which approximately minimizes \(\| I-MA\|_{\text{F}}\) or \(\| I-AM\| _{\text{F}}\). Then, we also discuss the theoretical issues such as the equivalence between the original least squares problem and the preconditioned problem. Finally, numerical experiments on problems from Matrix Market collection and random matrices show that although the preconditioning is expensive, it pays off in certain cases.
MSC:
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
Keywords:
approximate inverse; preconditioning; rectangular matrix; large sparse least squares problems; numerical experiments; random matricesReferences:
| [1] | R.E. Bank and C. Wagner, Multilevel ILU decomposition. Numer. Math.,82 (1999), 543–574. · Zbl 0938.65063 · doi:10.1007/s002110050430 |
| [2] | S.T. Barnard, L.M. Bernardo and H.D. Simon, An MPI implementation of the SPAI preconditioner on the T3E. Int. J. High Perform. Comput. Appl.,13 (1999), 107–128. · doi:10.1177/109434209901300202 |
| [3] | M.W. Benson, Iterative Solution of Large Scale Linear Systems. Master’s Thesis, Lakehead Universeity, Thunder Bay, ON, Canada, 1973. |
| [4] | M.W. Benson and P.O. Frederickson, Iterative solution of large sparse linear systems arising in certain multidimensional approximataion problems. Utilitas Math.,22 (1982), 127–140. · Zbl 0502.65020 |
| [5] | M. Benzi, Preconditioning techniques for large linear systems: a survey. J. Comp. Phy.,182 (2002), 418–477. · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176 |
| [6] | M. Benzi and M. Tuma, A comparative study of sparse approximate inverse preconditioners. Appl. Numer. Math.,30 (1999), 305–340. · Zbl 0949.65043 · doi:10.1016/S0168-9274(98)00118-4 |
| [7] | A. Björck, Numerical Methods for Least Squares Problems. SIAM, Philadelphia, 1996. · Zbl 0847.65023 |
| [8] | P.N. Brown and H.F. Walker, GMRES on (nearly) singular system. SIAM J. Matrix Anal. Appl.,18 (1997), 37–51. · Zbl 0876.65019 · doi:10.1137/S0895479894262339 |
| [9] | E. Chow and Y. Saad, Approximate inverse preconditioners via sparse-sparse iterations. SIAM J. Sci. Comput,19 (1998), 995–1023. · Zbl 0922.65034 · doi:10.1137/S1064827594270415 |
| [10] | J.D.F. Cosgrove, J.C. Daz and A. Griewank, Approximate inverse preconditioning for sparse linear systems. Int. J. Comput. Math.,44 (1992), 91–110. · Zbl 0762.65025 · doi:10.1080/00207169208804097 |
| [11] | I.S. Duff, R.G. Grimes and J.G. Lewis, Sparse matrix test problems. ACM Trans. Math. Software,15 (1989), 1–14. · Zbl 0667.65040 · doi:10.1145/62038.62043 |
| [12] | N.I.M. Gould and J.A. Scott, Sparse approximate-inverse preconditioners using normminimization techniques. SIAM J. Sci. Comput.,19 (1998), 605–625. · Zbl 0911.65037 · doi:10.1137/S1064827595288425 |
| [13] | M. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput.,18 (1997), 838–853. · Zbl 0872.65031 · doi:10.1137/S1064827594276552 |
| [14] | K. Hayami, J.-F. Yin and T. Ito, GMRES methods for least squares problems. NII Technical Report, NII-2007-009E, July 2007, 1–28. |
| [15] | C.C. Paige and M.A. Saunders, Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal.,12 (1975), 617–629. · Zbl 0319.65025 · doi:10.1137/0712047 |
| [16] | Y. Saad, Iterative Methods for Sparse Linear Systems (2nd edition). SIAM, Philadelphia, 2003. · Zbl 1031.65046 |
| [17] | Y. Saad and M.H. Schultz, GMRES: a generalized minimal residual method for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput.,7 (1986), 856–869. · Zbl 0599.65018 · doi:10.1137/0907058 |
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.
