×

Approximate generalized inverses with iterative refinement for \(\epsilon\)-accurate preconditioning of singular systems. (English) Zbl 1482.65044

Summary: We introduce a new class of preconditioners to enable flexible GMRES to find a least-squares solution, and potentially the pseudoinverse solution, of large-scale sparse, asymmetric, singular, and potentially inconsistent systems. We develop the preconditioners based on a new observation that generalized inverses (i.e., \(\boldsymbol{A}^g\in\{\boldsymbol{G}\mid\boldsymbol{AGA}=\boldsymbol{A}\})\) enable the preconditioned Krylov subspaces to converge in a single step. We then compute an approximate generalized inverse (AGI) efficiently using a hybrid incomplete factorization (HIF), which combines multilevel incomplete LU with rank-revealing QR on its final Schur complement. We define the criteria of \(\epsilon\)-accuracy and stability of AGI to guarantee the convergence of preconditioned GMRES for consistent systems. For inconsistent systems, we fortify HIF with iterative refinement to obtain HIFIR, which allows accurate computations of the null-space vectors. By combining the two techniques, we then obtain a new solver, called PIPIT, for obtaining the pseudoinverse solutions for systems with low-dimensional null spaces. We demonstrate the robustness of HIF and HIFIR and show that they improve both accuracy and efficiency of the prior state of the art by orders of magnitude for systems with up to a million unknowns.

MSC:

65F08 Preconditioners for iterative methods
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Alnaes, J. Blechta, J. Hake, A. Johansson, B. Kehlet, A. Logg, C. Richardson, J. Ring, M. E. Rognes, and G. N. Wells, The FEniCS project version 1.5, Arch. Numer. Sofware, 3 (2015).
[2] P. R. Amestoy, T. A. Davis, and I. S. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 886-905. · Zbl 0861.65021
[3] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, et al., LAPACK Users’ Guide, SIAM, Philadelphia, 1999. · Zbl 0934.65030
[4] M. Arioli and I. S. Duff, Using FGMRES to obtain backward stability in mixed precision, Electron. Trans. Numer. Anal., 33 (2009), pp. 31-44. · Zbl 1171.65018
[5] J. Baglama and L. Reichel, Augmented implicitly restarted Lanczos bidiagonalization methods, SIAM J. Sci. Comput., 27 (2005), pp. 19-42. · Zbl 1087.65039
[6] A. Ben-Israel and T. N. Greville, Generalized Inverses: Theory and Applications, 2nd ed., CMS Books Math. 15, Springer, New York, 2003. · Zbl 1026.15004
[7] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1-137. · Zbl 1115.65034
[8] M. Benzi and M. T\r uma, A robust incomplete factorization preconditioner for positive definite matrices, Numer. Linear Algebra Appl., 10 (2003), pp. 385-400. · Zbl 1071.65528
[9] M. Benzi and M. T\r uma, 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
[10] C. H. Bischof, Incremental condition estimation, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 312-322. · Zbl 0697.65042
[11] \AA. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996. · Zbl 0847.65023
[12] \AA. Björck and T. Elfving, Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations, BIT, 19 (1979), pp. 145-163. · Zbl 0409.65022
[13] P. Bochev and R. B. Lehoucq, On the finite element solution of the pure Neumann problem, SIAM Rev., 47 (2005), pp. 50-66. · Zbl 1084.65111
[14] M. Bollhöfer, J. I. Aliaga, A. F. Martín, and E. S. Quintana-Ortí, ILUPACK, in Encyclopedia of Parallel Computing, Springer, New York, 2011, pp. 917-926. · Zbl 1231.68001
[15] M. Bollhöfer and Y. Saad, Multilevel preconditioners constructed from inverse-based ILUs, SIAM J. Sci. Comput., 27 (2006), pp. 1627-1650. · Zbl 1104.65037
[16] W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed., other Titles Appl. Math. 72, SIAM, Philadelphia, 2000. · Zbl 0958.65128
[17] P. N. Brown and H. F. Walker, GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 37-51. · Zbl 0876.65019
[18] D. Calvetti, B. Lewis, and L. Reichel, GMRES-type methods for inconsistent systems, Linear Algebra Appl., 316 (2000), pp. 157-169. · Zbl 0963.65042
[19] E. Carson and N. J. Higham, A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems, SIAM J. Sci. Comput., 39 (2017), pp. A2834-A2856. · Zbl 1379.65019
[20] T. F. Chan, Rank revealing QR factorizations, Linear Algebra Appl., 88 (1987), pp. 67-82. · Zbl 0624.65025
[21] Q. Chen, A. Ghai, and X. Jiao, HILUCSI: Simple, robust, and fast multilevel ILU for large-scale saddle-point problems from PDEs, Numer. Linear Algebra Appl., (2021), e2400, https://doi.org/10.1002/nla.2400. · Zbl 07478626
[22] S.-C. T. Choi, Iterative Methods for Singular Linear Equations and Least-Squares Problems, Ph.D. thesis, Stanford University, 2006.
[23] S.-C. T. Choi, C. C. Paige, and M. A. Saunders, MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems, SIAM J. Sci. Comput., 33 (2011), pp. 1810-1836. · Zbl 1230.65050
[24] T. A. Davis, Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, ACM Trans. Math. Software, 38 (2011), pp. 1-22. · Zbl 1365.65122
[25] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Software, 38 (2011), pp. 1-25. · Zbl 1365.65123
[26] P. B. Denton, S. J. Parke, T. Tao, and X. Zhang, Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra, Bull. Amer. Math. Soc. (2021), https://doi.org/10.1090/bull/1722. · Zbl 1481.15008
[27] G. Dhondt, The Finite Element Method for Three-Dimensional Thermomechanical Applications, John Wiley & Sons, New York, 2004. · Zbl 1093.74001
[28] I. S. Duff and J. Koster, On algorithms for permuting large entries to the diagonal of a sparse matrix, SIAM J. Matrix Anal. Appl., 22 (2001), pp. 973-996. · Zbl 0979.05087
[29] I. S. Duff and S. Pralet, Strategies for scaling and pivoting for sparse symmetric indefinite problems, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 313-340. · Zbl 1092.65037
[30] T. Elfving, A stationary iterative pseudoinverse algorithm, BIT, 38 (1998), pp. 275-282. · Zbl 0907.65042
[31] H. C. Elman, D. J. Silvester, and A. J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2nd ed., Oxford University Press, New York, 2014. · Zbl 1304.76002
[32] A. Ern and J.-L. Guermond, Theory and Practice of Finite Elements, Appl. Math. Sci., 159, Springer, New York, 2013.
[33] D. C.-L. Fong and M. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM J. Sci. Comput., 33 (2011), pp. 2950-2971. · Zbl 1232.65052
[34] R. W. Freund and M. Hochbruck, On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling, Numer. Linear Algebra Appl., 1 (1994), pp. 403-420. · Zbl 0840.65021
[35] C. Geuzaine and J.-F. Remacle, Gmsh: A 3-D finite element mesh generator with built-in pre-and post-processing facilities, Internat. J. Numer. Meth. Engrg., 79 (2009), pp. 1309-1331. · Zbl 1176.74181
[36] A. Ghai, C. Lu, and X. Jiao, A comparison of preconditioned Krylov subspace methods for large-scale nonsymmetric linear systems, Numer. Linear Algebra Appl. (2017), e2215. · Zbl 1524.65131
[37] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037
[38] N. Gould and J. Scott, The state-of-the-art of preconditioners for sparse linear least-squares problems, ACM Trans. Math. Software, 43 (2017), pp. 1-35. · Zbl 1380.65064
[39] P. M. Gresho and R. L. Sani, On pressure boundary conditions for the incompressible Navier-Stokes equations, Int. J. Numer. Methods Fluids, 7 (1987), pp. 1111-1145. · Zbl 0644.76025
[40] K. Hayami, J.-F. Yin, and T. Ito, GMRES methods for least squares problems, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2400-2430. · Zbl 1215.65071
[41] M. R. Hestenes, E. Stiefel, et al., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49 (1952), pp. 409-436. · Zbl 0048.09901
[42] A. Jennings and M. Ajiz, Incomplete methods for solving \(A^TAx=b\), SIAM J. Sci. Stat. Comput., 5 (1984), pp. 978-987. · Zbl 0559.65013
[43] S. Karczmarz, Angenaherte auflosung von systemen linearer glei-chungen, Bull. Int. Acad. Pol. Sic. Let. Cl. Sci. Math. Nat., 35 (1937), pp. 355-357. · Zbl 0017.31703
[44] M. Kuchta, K.-A. Mardal, and M. Mortensen, On the singular Neumann problem in linear elasticity, Numer. Linear Algebra Appl., 26 (2019), e2212. · Zbl 1524.65831
[45] R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations: Steady State and Time Dependent Problems, SIAM, Philadelphia, 2007. · Zbl 1127.65080
[46] 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
[47] N. Li, Y. Saad, and E. Chow, Crout versions of ILU for general sparse matrices, SIAM J. Sci. Comput., 25 (2003), pp. 716-728. · Zbl 1042.65025
[48] J. Mayer, A multilevel Crout ILU preconditioner with pivoting and row permutation, Numer. Linear Algebra Appl., 14 (2007), pp. 771-789. · Zbl 1199.65091
[49] E. H. Moore, On the reciprocal of the general algebraic matrix, Bull. Amer. Math. Soc., 26 (1920), pp. 394-395.
[50] K. Morikuni and K. Hayami, Inner-iteration Krylov subspace methods for least squares problems, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1-22. · Zbl 1269.65039
[51] K. Morikuni and K. Hayami, Convergence of inner-iteration GMRES methods for rank-deficient least squares problems, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 225-250. · Zbl 1315.65041
[52] K. Morikuni and M. Rozložník, On GMRES for singular EP and GP systems, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1033-1048. · Zbl 1391.65070
[53] 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
[54] C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8 (1982), pp. 43-71. · Zbl 0478.65016
[55] R. Penrose, A generalized inverse for matrices, Math Proc. Cambridge, 51 (1955), pp. 406-413. · Zbl 0065.24603
[56] C. Popa, Least-squares solution of overdetermined inconsistent linear systems using Kaczmarz’s relaxation, Int. J. Comput. Math., 55 (1995), pp. 79-89. · Zbl 0830.65027
[57] C. R. Rao and S. K. Mitra, Generalized inverse of a matrix and its applications, in Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Theory of Statistics, Regents of the University of California, 1972. · Zbl 0232.15002
[58] J. N. Reddy and D. K. Gartling, The Finite Element Method in Heat Transfer and Fluid Dynamics, CRC Press, Boca Raton, FL, 2010. · Zbl 1257.80001
[59] L. Reichel and Q. Ye, Breakdown-free GMRES for singular systems, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 1001-1021. · Zbl 1086.65030
[60] Y. Saad, Preconditioning techniques for nonsymmetric and indefinite linear systems, J. Comput. Appl. Math, 24 (1988), pp. 89-105. · Zbl 0662.65028
[61] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993), pp. 461-469. · Zbl 0780.65022
[62] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Other Titles Appl. Math. 82, SIAM, Philadelphia, 2003. · Zbl 1031.65046
[63] J. A. Scott and M. T\r uma, Preconditioning of Linear Least Squares by RIF for Implicitly Held Normal Equations, Tech. Report RAL-TR-2016-P-001, Rutherford Appleton Laboratory, Oxfordshire, UK, 2016. · Zbl 1348.65066
[64] A. Sidi, DGMRES: A GMRES-type algorithm for Drazin-inverse solution of singular non-symmetric linear systems, Linear Algebra Appl., 335 (2001), pp. 189-204. · Zbl 0982.65043
[65] V. Simoncini and D. B. Szyld, Flexible inner-outer Krylov subspace methods, SIAM J. Numer. Anal., 40 (2002), pp. 2219-2239. · Zbl 1047.65021
[66] R. D. Skeel, Iterative refinement implies numerical stability for Gaussian elimination, Math. Comp., 35 (1980), pp. 817-832. · Zbl 0441.65027
[67] K. Sugihara, K. Hayami, and N. Zheng, Right preconditioned MINRES for singular systems, Numer. Linear Algebra Appl., 27 (2020), e2277. · Zbl 1463.65058
[68] K. Tanabe, Projection method for solving a singular system of linear equations and its applications, Numer. Math., 17 (1971), pp. 203-214. · Zbl 0228.65032
[69] MATLAB R2020a, The MathWorks, Natick, MA, 2020.
[70] L. N. Trefethen and D. Bau, III, Numerical Linear Algebra, Other Titles Appl. Math. 50, SIAM, Philadelphia, 1997. · Zbl 0874.65013
[71] U. Trottenberg, C. W. Oosterlee, and A. Schuller, Multigrid, Academic Press, New York, 2000.
[72] R. S. Tuminaro, H. F. Walker, and J. N. Shadid, On backtracking failure in Newton-Gmres methods with a demonstration for the Navier-Stokes equations, J. Comput. Phys., 180 (2002), pp. 549-558. · Zbl 1143.76489
[73] F. Uren͂a, J. J. Benito, and L. G. Corvinos, Application of the generalized finite difference method to solve the advection-diffusion equation, J. Comput. Appl. Math, 235 (2011), pp. 1849-1855. · Zbl 1209.65088
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.