A spectral analysis of subspace enhanced preconditioners. (English) Zbl 1341.65012
Let \(A\in\mathbb R^{n\times n}\) be symmetric positive definite (SPD) with eigenvalue decomposition \(A[V~V_\perp]=[V~V_\perp]\mathrm{diag}(\Lambda,\Lambda_\perp)\), where \(\Lambda\) contains the \(r\) smallest eigenvalues and \(V\) the corresponding eigenvectors. Three projections are defined: \(P_D=I-AVE^{-1}V^T\), \(P_C=I+VE^{-1}V^T\), and \(P_A=I-AVE^{-1}V^T+VE^{-1}V^T\) where \(E=V^TAV\). Applying one of these \(P_X\) to \(A\) will give a matrix \(P_XA\) whose eigenvalues are respectively \(\mathrm{diag}(0,\Lambda_\perp)\), \(\mathrm{diag}(I+\Lambda,\Lambda_\perp)\), and \(\mathrm{diag}(I,\Lambda_\perp)\) so that these \(P_X\) can serve as preconditioners. Clearly, to compute the eigenvalues of \(A\), the exact eigenvectors \(V\) cannot be used, but some orthogonal set \(\tilde{V}\approx V\) is used instead. Also the inverse \(E^{-1}\) is often approximated as \(\tilde{E}^{-1}\). The result is an approximate projector \(\tilde{P}_X\). Several bounds for the eigenvalues of the preconditioned \(\tilde{P}_X A\) matrices are proved. Numerical tests illustrate the technique.
Reviewer: Adhemar Bultheel (Leuven)
MSC:
| 65F08 | Preconditioners for iterative methods |
| 15B48 | Positive matrices and their generalizations; cones of matrices |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 54F15 | Continua and generalizations |
| 15A42 | Inequalities involving eigenvalues and eigenvectors |
Keywords:
perturbation analysis; preconditioner; domain decomposition; spectrum; coarse space; numerical examples; eigenvalue; eigenvectorSoftware:
FreeFem++References:
| [1] | Brown, P.N., Walker, H.F.: GMRES on singular systems. SIAM J. Matrix Anal. Appl. 18, 37-51 (1997) · Zbl 0876.65019 · doi:10.1137/S0895479894262339 |
| [2] | Cai, X.C., Sarkis, M.: A restricted additive Schwarz preconditioner for general sparse linear systems. SIAM J. Sci. Comput. 21, 792-797 (1999) · Zbl 0944.65031 · doi:10.1137/S106482759732678X |
| [3] | Efstathiou, E., Gander, M.J.: Why restricted additive Schwarz converges faster than additive Schwarz. BIT 43, 945-959 (2003) · Zbl 1045.65027 · doi:10.1023/B:BITN.0000014563.33622.1d |
| [4] | Erlangga, Y.A., Nabben, R.: Deflation and balancing preconditioners for Krylov subspace methods applied to nonsymmetric matrices. SIAM J. Matrix Anal. Appl. 30, 684-699 (2008) · Zbl 1163.65014 · doi:10.1137/060678257 |
| [5] | Frank, J., Vuik, C.: On the construction of deflation-based preconditioners. SIAM J. Sci. Comput. 23, 442-462 (2001) · Zbl 0997.65072 · doi:10.1137/S1064827500373231 |
| [6] | Golub, G.H., van Loan, C.F.: Matrix Comput., 3rd edn. John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009 |
| [7] | Giraud, L., Gratton, S.: On the sensitivity of some spectral preconditioners. SIAM J. Matrix Anal. Appl. 27, 1089-1105 (2006) · Zbl 1104.65040 · doi:10.1137/040617546 |
| [8] | Gosselet, P., Rey, C.: On a selective reuse of Krylov subspaces in Newton-Krylov approaches for nonlinear elasticity. In: Domain Decomposition Methods in Science and Engineering, National Autonomous University of Mexico, México, pp. 419-426 (2003) · Zbl 1248.65129 |
| [9] | Havé, P., Masson, R., Nataf, F., Szydlarski, M., Xiang, H., Zhao, T.: Algebraic domain decomposition methods for highly heterogeneous problems. SIAM J. Sci. Comput. 35, C284-C302 (2013) · Zbl 1278.65189 · doi:10.1137/110842648 |
| [10] | Hecht, F.: FreeFem++. http://www.freefem.org/ff++/ (2014) · Zbl 1296.65178 |
| [11] | Kaasschieter, E.F.: Preconditioned conjugate gradients for solving singular systems. J. Comput. Appl. Math. 24, 265-275 (1988) · Zbl 0659.65031 · doi:10.1016/0377-0427(88)90358-5 |
| [12] | Karypis, G., Kumar, V.: A fast and highly qualty multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359-392 (1998) · Zbl 0915.68129 · doi:10.1137/S1064827595287997 |
| [13] | Klawonn, A., Rheinbach, O.: Deflation, projector preconditioning, and balancing in iterative substructuring methods: connections and new results. SIAM J. Sci. Comput. 34, A459-A484 (2012) · Zbl 1248.65129 · doi:10.1137/100811118 |
| [14] | Klawonn, A., Lanser, M., Rheinbach, O.: Nonlinear FETI-DP and BDDC methods. SIAM J. Sci. Comput. 36, A737-A765 (2014) · Zbl 1296.65178 · doi:10.1137/130920563 |
| [15] | Morgan, R.B.: GMRES with deflated restarting. SIAM J. Sci. Comput. 24, 20-37 (2002) · Zbl 1018.65042 · doi:10.1137/S1064827599364659 |
| [16] | Nabben, R., Vuik, C.: a comparison of abstract versions of deflation, balancing and additive coarse grid correction preconditioners. Numer. Linear Algeb. Appl. 15, 355-372 (2008) · Zbl 1212.65121 · doi:10.1002/nla.571 |
| [17] | Nataf, F., Xiang, H., Dolean, V., Spillane, N.: A coarse grid space construction based on local Dirichlet to Neumann maps. SIAM J. Sci. Comput. 33, 1623-1642 (2011) · Zbl 1230.65134 · doi:10.1137/100796376 |
| [18] | Nicolaides, R.A.: Deflation of conjugate gradient with application to boundary value problem. SIAM J. Numer. Anal. 24, 355-365 (1987) · Zbl 0624.65028 · doi:10.1137/0724027 |
| [19] | Notay, Y., Napov, A.: Further comparison of additive and multiplicative coarse grid correction. Appl. Numer. Math. 65, 53-62 (2013) · Zbl 1271.65052 · doi:10.1016/j.apnum.2012.12.001 |
| [20] | Padiy, A., Axelsson, O., Polman, B.: Generalized augmented matrix preconditioning approach and its application to iterative solution of ill-conditioned algebraic systems. SIAM J. Matrix Anal. Appl. 22, 793-818 (2000) · Zbl 0982.65053 · doi:10.1137/S0895479899356754 |
| [21] | Parks, M.L., de Sturler, E., Mackey, G., Johnson, D.D., Maiti, S.: Recycling Krylov subspaces for sequences of linear systems. SIAM J. Sci. Comput. 28, 1651-1674 (2006) · Zbl 1123.65022 · doi:10.1137/040607277 |
| [22] | Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [23] | St-Cyr, A., Gander, M.J., Thomas, S.J.: Optimized multiplicative, additive, and restricted additive Schwarz preconditioning. SIAM J. Sci. Comput. 29, 2402-2425 (2007) · Zbl 1154.65017 · doi:10.1137/060652610 |
| [24] | Stewart, G.W.: Matrix Algorithms Volume II: Eigensystems. SIAM, Philadelphia (2001) · Zbl 0984.65031 · doi:10.1137/1.9780898718058 |
| [25] | Tang, J.M., Maclachlan, S.P., Nabben, R., Vuik, C.: A comparison of two-level preconditioners based on multigrid and deflation. SIAM J. Matrix Anal. Appl. 31, 1715-1739 (2010) · Zbl 1205.65143 · doi:10.1137/08072084X |
| [26] | Tang, J.M., Nabben, R., Vuik, C., Erlangga, Y.A.: Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods. J. Sci. Comput. 39, 340-370 (2009) · Zbl 1203.65073 · doi:10.1007/s10915-009-9272-6 |
| [27] | Toselli, A., Widlund, O.: Domain Decomposition Methods: Algorithms and Theory. Springer, Berlin (2005) · Zbl 1069.65138 |
| [28] | van der Sluis, A., van der Vorst, H.A.: The rate of convergence of conjugate gradients. Numer. Math. 48, 543-560 (1986) · Zbl 0596.65015 · doi:10.1007/BF01389450 |
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.
