Deflation for the off-diagonal block in symmetric saddle point systems. (English) Zbl 1531.65049
Advanced simulation tasks often require the numerical solution of partial differential equations with fine resolution such that the discretization leads to large, sparse linear systems. As a first choice, it seems natural to use direct methods for the analysis but often these come with high computation complexity.
In this interesting paper, the authors study iterative solvers for matrices in saddle point form, as they appear as systems for example in the discretization of PDEs in incompressible fluid flow. They develop a deflation strategy for symmetric saddle point matrices by taking advantage of their intrinsic block structure. The vectors used for the deflation arise naturally from an elliptic singular value decomposition which a priori relies on a generalized Golub-Kahan bidiagonalization process. The block which is targeted by deflation is the off-diagonal one since it features a problematic singular value distribution for certain applications which the authors present in the paper with numerical experiments.
The paper is well written with a good list of references.
In this interesting paper, the authors study iterative solvers for matrices in saddle point form, as they appear as systems for example in the discretization of PDEs in incompressible fluid flow. They develop a deflation strategy for symmetric saddle point matrices by taking advantage of their intrinsic block structure. The vectors used for the deflation arise naturally from an elliptic singular value decomposition which a priori relies on a generalized Golub-Kahan bidiagonalization process. The block which is targeted by deflation is the off-diagonal one since it features a problematic singular value distribution for certain applications which the authors present in the paper with numerical experiments.
The paper is well written with a good list of references.
Reviewer: Steven B. Damelin (Ann Arbor)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 35P15 | Estimates of eigenvalues in context of PDEs |
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
Keywords:
Golub-Kahan bidiagonalization; eigenvalue deflation; singular value decomposition; saddle point problems; Stokes equationReferences:
| [1] | Aishima, K., Global convergence of the restarted Lanczos and Jacobi-Davidson methods for symmetric eigenvalue problems, Numer. Math., 131 (2015), pp. 405-423. · Zbl 1325.65050 |
| [2] | Arioli, M., Generalized Golub-Kahan bidiagonalization and stopping criteria, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 571-592, doi:10.1137/120866543. · Zbl 1273.65041 |
| [3] | Axelsson, O. and Karátson, J., Reaching the superlinear convergence phase of the CG method, J. Comput. Appl. Math., 260 (2014), pp. 244-257. · Zbl 1293.65045 |
| [4] | Baglama, J. and Reichel, L., Augmented implicitly restarted Lanczos bidiagonalization methods, SIAM J. Sci. Comput., 27 (2005), pp. 19-42, doi:10.1137/04060593X. · Zbl 1087.65039 |
| [5] | Baglama, J., Reichel, L., and Richmond, D., An augmented LSQR method, Numer. Algorithms, 64 (2013), pp. 263-293. · Zbl 1273.65059 |
| [6] | Barlow, J. L., Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction, Numer. Math., 124 (2013), pp. 237-278. · Zbl 1272.65034 |
| [7] | Barrett, R., Berry, M., Chan, T. F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, 1994, doi:10.1137/1.9781611971538. · Zbl 0814.65030 |
| [8] | Benzi, M., Golub, G. H., and Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1-137. · Zbl 1115.65034 |
| [9] | Chizhonkov, E. V. and Olshanskii, M. A., On the domain geometry dependence of the LBB condition, ESAIM Math. Model. Numer. Anal., 34 (2000), pp. 935-951. · Zbl 1006.76052 |
| [10] | Coulaud, O., Giraud, L., Ramet, P., and Vasseur, X., Deflation and Augmentation Techniques in Krylov Subspace Methods for the Solution of Linear Systems, arXiv preprint, arXiv:1303.5692, 2013. |
| [11] | Daas, H. A., Grigori, L., Hénon, P., and Ricoux, P., Recycling Krylov subspaces and truncating deflation subspaces for solving sequence of linear systems, ACM Trans. Math. Software, 47 (2021), pp. 1-30. · Zbl 07467973 |
| [12] | Darrigrand, V., Dumitrasc, A., Kruse, C., and Rüde, U., Inexact inner-outer Golub-Kahan bidiagonalization method: A relaxation strategy, Numer. Linear Algebra Appl., (2022), e2484. · Zbl 07790610 |
| [13] | Elman, H. C., Silvester, D. J., and Wathen, A. J., Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2nd ed., , Oxford Academic, 2014. · Zbl 1304.76002 |
| [14] | Fischer, B., Polynomial Based Iteration Methods for Symmetric Linear Systems, , SIAM, 2011, doi:10.1137/1.9781611971927. · Zbl 1223.65023 |
| [15] | Fischer, B., Ramage, A., Silvester, D. J., and Wathen, A. J., Minimum residual methods for augmented systems, BIT, 38 (1998), pp. 527-543. · Zbl 0914.65026 |
| [16] | Gaul, A., Gutknecht, M. H., Liesen, J., and Nabben, R., Deflated and Augmented Krylov Subspace Methods: Basic Facts and a Breakdown-Free Deflated MINRES, , Technical University Berlin, 2011. · Zbl 1273.65049 |
| [17] | Gaul, A., Gutknecht, M. H., Liesen, J., and Nabben, R., A framework for deflated and augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 495-518, doi:10.1137/110820713. · Zbl 1273.65049 |
| [18] | Giraud, L. and Gratton, S., On the sensitivity of some spectral preconditioners, SIAM J. Matrix Anal. Appl., 27 (2006), pp. 1089-1105, doi:10.1137/040617546. · Zbl 1104.65040 |
| [19] | Giraud, L., Langou, J., and Rozložník, M., The loss of orthogonality in the Gram-Schmidt orthogonalization process, Comput. Math. Appl., 50 (2005), pp. 1069-1075. · Zbl 1085.65037 |
| [20] | Golub, G. H. and Underwood, R., The block Lanczos method for computing eigenvalues, in Mathematical Software, Elsevier, 1977, pp. 361-377. · Zbl 0407.68040 |
| [21] | Golub, G. H. and Van Loan, C. F., Matrix Computations, , Johns Hopkins University Press, 1996. · Zbl 0865.65009 |
| [22] | Golub, G. H., Zhang, Z., and Zha, H., Large sparse symmetric eigenvalue problems with homogeneous linear constraints: The Lanczos process with inner-outer iterations, Linear Algebra Appl., 309 (2000), pp. 289-306. · Zbl 0948.65033 |
| [23] | Griebel, M., Dornseifer, T., and Neunhoeffer, T., Numerical Simulation in Fluid Dynamics: A Practical Introduction, , SIAM, 1998, doi:10.1137/1.9780898719703. · Zbl 0945.76001 |
| [24] | Gutknecht, M. H., Spectral deflation in Krylov solvers: A theory of coordinate space based methods, Electron. Trans. Numer. Anal., 39 (2012), pp. 156-185. · Zbl 1285.65021 |
| [25] | Harlow, F. H. and Welch, J. E., Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface, Phys. Fluids, 8 (1965), pp. 2182-2189. · Zbl 1180.76043 |
| [26] | Kohl, N. and Rüde, U., Textbook Efficiency: Massively Parallel Matrix-Free Multigrid for the Stokes System, arXiv preprint, arXiv:2010.13513, 2020. · Zbl 1492.65080 |
| [27] | Kruse, C., Darrigrand, V., Tardieu, N., Arioli, M., and Rüde, U., Application of an iterative Golub-Kahan algorithm to structural mechanics problems with multi-point constraints, Adv. Model. Simul. Eng. Sci., 7 (2020), 45. |
| [28] | Kruse, C., Sosonkina, M., Arioli, M., Tardieu, N., and Rüde, U., Parallel performance of an iterative solver based on the Golub-Kahan bidiagonalization, in Parallel Processing and Applied Mathematics (PPAM 2019), , Wyrzykowski, R., Deelman, E., Dongarra, J., and Karczewski, K., eds., Springer, 2020, pp. 104-116. |
| [29] | Kruse, C., Sosonkina, M., Arioli, M., Tardieu, N., and Rüde, U., Parallel solution of saddle point systems with nested iterative solvers based on the Golub-Kahan bidiagonalization, Concurr. Comput., 33 (2021), e5914. |
| [30] | Liesen, J. and Tichỳ, P., Convergence analysis of Krylov subspace methods, GAMM-Mitt., 27 (2004), pp. 153-173. · Zbl 1071.65041 |
| [31] | Mello, L. A. M., De Sturler, E., Paulino, G. H., and Silva, E. C. N., Recycling Krylov subspaces for efficient large-scale electrical impedance tomography, Comput. Methods Appl. Mech. Engrg., 199 (2010), pp. 3101-3110. · Zbl 1225.92026 |
| [32] | Mercier, S., Gratton, S., Tardieu, N., and Vasseur, X., A new preconditioner update strategy for the solution of sequences of linear systems in structural mechanics: Application to saddle point problems in elasticity, Comput. Mech., 60 (2017), pp. 969-982. · Zbl 1398.65047 |
| [33] | Nabben, R. and Vuik, C., A comparison of deflation and coarse grid correction applied to porous media flow, SIAM J. Numer. Anal., 42 (2004), pp. 1631-1647, doi:10.1137/S0036142903430451. · Zbl 1146.76658 |
| [34] | Olshanskii, M. A. and Simoncini, V., Acquired clustering properties and solution of certain saddle point systems, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2754-2768, doi:10.1137/100792652. · Zbl 1213.65060 |
| [35] | Orban, D. and Arioli, M., Iterative Solution of Symmetric Quasi-definite Linear Systems, , SIAM, 2017, doi:10.1137/1.9781611974737. · Zbl 1409.65004 |
| [36] | Paige, C. C., Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl., 34 (1980), pp. 235-258. · Zbl 0471.65017 |
| [37] | Ramage, A., Ruiz, D., Sartenaer, A., and Tannier, C., Using partial spectral information for block diagonal preconditioning of saddle-point systems, Comput. Optim. Appl., 78 (2021), pp. 353-375. · Zbl 1469.90143 |
| [38] | Rozložník, M., Tůma, M., Smoktunowicz, A., and Kopal, J., Numerical stability of orthogonalization methods with a non-standard inner product, BIT, 52 (2012), pp. 1035-1058. · Zbl 1259.65069 |
| [39] | Saad, Y., Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, doi:10.1137/1.9780898718003. · Zbl 1031.65046 |
| [40] | Saunders, M. A., Solution of sparse rectangular systems using LSQR and CRAIG, BIT, 35 (1995), pp. 588-604. · Zbl 0844.65029 |
| [41] | Sifuentes, J. A., Embree, M., and Morgan, R. B., GMRES convergence for perturbed coefficient matrices, with application to approximate deflation preconditioning, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1066-1088, doi:10.1137/120884328. · Zbl 1314.65051 |
| [42] | Soodhalter, K. M., de Sturler, E., and Kilmer, M. E., A survey of subspace recycling iterative methods, GAMM-Mitt., 43 (2020), e202000016. · Zbl 1541.65019 |
| [43] | Stathopoulos, A. and Orginos, K., Computing and deflating eigenvalues while solving multiple right-hand side linear systems with an application to quantum chromodynamics, SIAM J. Sci. Comput., 32 (2010), pp. 439-462, doi:10.1137/080725532. · Zbl 1209.65046 |
| [44] | Van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems, , Cambridge University Press, 2003. · Zbl 1023.65027 |
| [45] | van’t Wout, E., van Gijzen, M. B., Ditzel, A., van der Ploeg, A., and Vuik, C., The deflated relaxed incomplete Cholesky CG method for use in a real-time ship simulator, Proc. Comput. Sci., 1 (2010), pp. 249-257. |
| [46] | Venkovic, N., Mycek, P., Giraud, L., and Le Maitre, O., Comparative Study of Harmonic and Rayleigh-Ritz Procedures with Applications to Deflated Conjugate Gradients, Technical report TR/PA/20-3, CERFACS, 2020. |
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.
