×

A deflated conjugate gradient method for multiple right hand sides and multiple shifts. (English) Zbl 1305.65116

Summary: We consider the task of computing solutions of linear systems that only differ by a shift with the identity matrix as well as linear systems with several different right-hand sides. In the past, Krylov subspace methods have been developed which exploit either the need for solutions to multiple right-hand sides (e.g. deflation type methods and block methods) or multiple shifts (e.g. shifted conjugate gradient methods) with some success. In this paper we present a block Krylov subspace method which, based on a block Lanczos process, exploits both features – shifts and multiple right-hand sides – at once. Such situations arise, for example, in lattice quantum chromodynamics simulations within the rational hybrid Monte Carlo algorithm. We present numerical evidence that our method is superior compared to applying other iterative methods to each of the systems individually as well as, in typical situations, to shifted or block Krylov subspace methods.

MSC:

65F10 Iterative numerical methods for linear systems
81V05 Strong interaction, including quantum chromodynamics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abdel-Rehim, A., Morgan, R.B., Wilcox, W.: Seed methods for linear equations in lattice QCD problems with multiple right-hand sides. PoS LAT2008, 38 (2008)
[2] Aliaga, J.I., Boley, D.L., Freund, R., Hernández, V.: A Lanczos-type method for multiple starting vectors. Math. Comp. 69(232), 1577-1601 (2000) · Zbl 0953.65018 · doi:10.1090/S0025-5718-99-01163-1
[3] Barbella, G., Perotti, F., Simoncini, V.: Block Krylov subspace methods for the computation of structural response to turbulent wind. Comput. Methods Appl. Mech. Eng. 200(23-24), 2067-2082 (2011) · Zbl 1228.74033 · doi:10.1016/j.cma.2011.02.017
[4] Darnell, D., Morgan, R.B., Wilcox, W.: Deflated GMRES for systems with multiple shifts and multiple right-hand sides. Linear Algebra Appl. 429(10), 2415-2434 (2008). Special issue in honor of Richard S. Varga · Zbl 1153.65032 · doi:10.1016/j.laa.2008.04.019
[5] Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1:1-1:25 (2011) · Zbl 1365.65123
[6] Debbio, L.D., Giusti, L., Lüscher, M., Petronzio, R., Tantalo, N.: QCD with light Wilson quarks on fine lattices (i): First experiences and physics results. JHEP 702, 56,2007 (2007)
[7] Debbio, L.D., Giusti, L., Lüscher, M., Petronzio, R., Tantalo, N.: QCD with light Wilson quarks on fine lattices (ii): DD-HMC simulations and data analysis. JHEP 702, 82,2007 (2007)
[8] Dubrulle, A.A.: Retooling the method of block conjugate gradients. Electron. Trans. Numer. Anal. 12, 216-233 (electronic) (2001) · Zbl 0985.65021
[9] Erhel, J., Guyomarc’H, F.: An augmented conjugate gradient method for solving consecutive symmetric positive definite linear systems. SIAM J. Matrix Anal. Appl. 21(4), 1279-1299 (2000) · Zbl 0966.65031 · doi:10.1137/S0895479897330194
[10] Fiebach, P., Frommer, A., Freund, R.: Variants of the Block-QMR method and applications in quantum chromodynamics. In: 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics, vol. 3, pp. 491-496 (1997) · Zbl 1365.65123
[11] Freund, R., Malhotra, M.: A block QMR algorithm for non-hermitian linear systems with multiple right-hand sides. Linear Algebra Appl. 254, 119-157 (1997) · Zbl 0873.65021 · doi:10.1016/S0024-3795(96)00529-0
[12] Frommer A., Maass, P.: Fast CG-based methods for Tikhonov-Phillips regularization. SIAM J. Sci. Comput. 20(5), 1831-1850 (1999) (electronic) · Zbl 0943.65068 · doi:10.1137/S1064827596313310
[13] Guennebaud, G., Jacob, B., et al.: Eigen v3. http://eigen.tuxfamily.org (2010) · Zbl 1074.65043
[14] Gutknecht, M.H.: Block Krylov space methods for linear systems with multiple right-hand sides: an introduction. In: Siddiqi, A., Duff, I., Christensen, O. (eds.) Modern Mathematical Models, Methods and Algorithms for Real World Systems, pp. 420-447. Anamaya Publishers, New Delhi (2007) · Zbl 0837.65029
[15] Higham, N.J.: Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia (2008) · Zbl 1167.15001 · doi:10.1137/1.9780898717778
[16] Kennedy, A.D.: Algorithms for dynamical fermions. Technical report, School of Physics, University of Edinburgh, arXiv:hep-lat/0607038v1 (2006)
[17] Morgan, R.B.: Restarted block-GMRES with deflation of eigenvalues. Appl. Numer. Math. 54(2), 222-236 (2005) · Zbl 1074.65043 · doi:10.1016/j.apnum.2004.09.028
[18] Nikishin, A.A., Yeremin, A.Y.: Variable block CG algorithms for solving large sparse symmetric positive definite linear systems on parallel computers, i: General iterative scheme. SIAM J. Matrix Anal. Appl. 16(4), 1135-1153 (1995) · Zbl 0837.65029 · doi:10.1137/S0895479893247679
[19] Nikishin, A.A., Yeremin, A.Y.: An automatic procedure for updating the block size in the block conjugate gradient method for solving linear systems. J. Math. Sci. 114, 1844-1853 (2003). doi:10.1023/A:1022462.721147 · Zbl 1029.65046 · doi:10.1023/A:1022462.721147
[20] O’Leary, D.P.: The block conjugate gradient algorithm and related methods. Linear Algebra Appl. 29, 293-322 (1980) · Zbl 0426.65011 · doi:10.1016/0024-3795(80)90247-5
[21] Paige, C.C., Parlett, B.N., van der Vorst, H.A.: Approximate solutions and eigenvalue bounds from Krylov subspaces. Numer. Linear Algebra Appl. 2(2), 115-133 (1995) · Zbl 0831.65036 · doi:10.1002/nla.1680020205
[22] Saad, Y.: On the Lanczos method for solving symmetric linear systems with several right-hand sides. Math. Comput. 48(178), 651-662 (1987) · Zbl 0615.65038
[23] Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[24] Soodhalter, K.: Mathematics and implementation details of a block MINRES algorithm. In: Review by Journal (2013) · Zbl 1278.65032
[25] Stathopoulos, A., 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(1), 439-462 (2010) · Zbl 1209.65046 · doi:10.1137/080725532
[26] Tadano, H., Sakurai, T., Kuramashi, Y.: Block BiCGGR: A new block Krylov subspace method for computing high accuracy solutions. JSIAM Lett. 1, 44 (2009) · Zbl 1278.65032 · doi:10.14495/jsiaml.1.44
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.