ChebStaBlkCG: a block variant of ChebFilterCG. (English) Zbl 1524.65145
Summary: The behavior of ChebFilterCG (an algorithm that combines the Chebyshev filter and Conjugate Gradient) applied to systems with unfavorable eigenvalue distribution is examined. To improve the convergence, a hybrid approach combining a stabilized version of the block conjugated gradient with Chebyshev polynomials as preconditioners (ChebStaBlkCG) is proposed. The performance of ChebStaBlkCG is illustrated and validated on a set of linear systems. It is shown how ChebStaBlkCG can be used to accelerate the block Cimmino method and to solve linear systems with multiple right-hand sides.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
block Cimmino; block conjugate gradient; Chebyshev filtering polynomials; ill-conditioning; polynomial accelerationReferences:
| [1] | KalantzisV, BekasC, CurioniA, GallopoulosE. Accelerating data uncertainty quantification by solving linear systems with multiple right‐hand sides. Numer Algorithms. 2013;62(4):637-653. · Zbl 1263.65009 |
| [2] | TouhamiA. Utilisation des filtres de Tchebycheff et construction de préconditionneurs spectraux pour l’accélération des méthodes de Krylov [PhD thesis]. Toulouse, France; 2005. |
| [3] | GolubGH, RuizD, TouhamiA. A hybrid approach combining Chebyshev filter and conjugate gradient for solving linear systems with multiple right‐hand sides. SIAM J Matrix Anal Appl. 2007;29(3):774-795. · Zbl 1151.65319 |
| [4] | SadkaneM, TouhamiA. Convergence analysis of the ChebFilterCG algorithm. Numer Linear Algebra Appl. 2017;e2087:17. · Zbl 1424.65035 |
| [5] | SaadY. On the Lánczos method for solving symmetric linear systems with several right‐hand sides. Math Comp. 1987;48(178):651-662. · Zbl 0615.65038 |
| [6] | ErhelJ, Guyomarc’hF. An augmented conjugate gradient method for solving consecutive symmetric positive definite linear systems. SIAM J Matrix Anal Appl. 2000;21(4):1279-1299. · Zbl 0966.65031 |
| [7] | SaadY, YeungM, ErhelJ, Guyomarc’hF. A deflated version of the conjugate gradient algorithm. SIAM J Sci Comput. 2000;21(5):1909-1926. · Zbl 0955.65021 |
| [8] | GutknechtMH. Spectral deflation in Krylov solvers: a theory of coordinate space based methods. Electron Trans Numer Anal. 2012;39:156-185. · Zbl 1285.65021 |
| [9] | NicolaidesRA. Deflation of conjugate gradients with applications to boundary value problems. SIAM J Numer Anal. 1987;24(2):355-365. · Zbl 0624.65028 |
| [10] | DostálZ. Conjugate gradient method with preconditioning by projector. Int J Comput Math. 1988;23:315-323. · Zbl 0668.65034 |
| [11] | FrankJ, VuikC. On the construction of deflation‐based preconditioners. SIAM J Sci Comput. 2001;23(2):442-462. · Zbl 0997.65072 |
| [12] | NabbenR, VuikC. A comparison of deflation and coarse grid correction applied to porous media flow. SIAM J Numer Anal. 2004;42(4):1631-1647. · Zbl 1146.76658 |
| [13] | CarpentieriB, DuffIS, GiraudL. A class of spectral two‐level preconditioners. SIAM J Sci Comput. 2003;25(2):749-765. · Zbl 1048.65043 |
| [14] | O’LearyDP. The block conjugate gradient algorithm and related methods. Linear Algebra Appl. 1980;29:293-322. · Zbl 0426.65011 |
| [15] | ArioliM, DuffIS, RuizD, SadkaneM. Block Lanczos techniques for accelerating the block Cimmino method. SIAM J Sci Comput. 1995;16(6):1478-1511. · Zbl 0839.65037 |
| [16] | CimminoG. Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. Ric Sci Progr techn econom naz. 1939;9:326-333. · JFM 64.1244.02 |
| [17] | AnsorgeR. Connections between the Cimmino‐method and the Kaczmarz‐method for the solution of singular and regular systems of equations. Computing. 1984;33(3-4):367-375. · Zbl 0537.65027 |
| [18] | SlobodaF. A projection method of the Cimmino type for linear algebraic systems. Parallel Comput. 1991;17(4-5):435-442. · Zbl 0741.65037 |
| [19] | FrommerA, LundK, SzyldDB. Block Krylov subspace methods for functions of matrices. Electron Trans Numer Anal. 2017;47:100-126. · Zbl 1372.65138 |
| [20] | RivlinTJ. The Chebyshev polynomials: From approximation theory to algebra and number theory. 2nd ed. New York, NY: John Wiley & Sons; 1990. · Zbl 0734.41029 |
| [21] | BjörckȦ. Solving linear least squares problems by Gram‐Schmidt orthogonalization. BIT Numer Math. 1967;7:1-21. · Zbl 0183.17802 |
| [22] | OettliW, PragerW. Compatibility of approximate solution of linear equations with given error bounds for coefficients and right‐hand sides. Numerische Mathematik. 1964;6:405-409. · Zbl 0133.08603 |
| [23] | ArioliM, DemmelJW, DuffIS. Solving sparse linear systems with sparse backward error. SIAM J Matrix Anal Appl. 1989;10(2):165-190. · Zbl 0684.65022 |
| [24] | van derSluisA, van derVorstHA. The rate of convergence of conjugate gradients. Numerische Mathematik. 1986;48(5):543-560. · Zbl 0596.65015 |
| [25] | van derSluisA, van derVorstHA. The convergence behavior of Ritz values in the presence of close eigenvalues. Linear Algebra Appl. 1987;88-89:651-694. · Zbl 0632.65035 |
| [26] | ParlettBN. Misconvergence in the Lanczos algorithm. In: Reliable numerical computation. New York, NY: Oxford University Press; 1990. p. 7-24. · Zbl 0726.65032 |
| [27] | MeurantG. The Lanczos and conjugate gradient algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics; 2006. Software, environments, and tools, No. 19. · Zbl 1110.65029 |
| [28] | LiesenJ, StrakošZ. Krylov subspace methods: Principles and analysis. Oxford, UK: Oxford University Press; 2013. · Zbl 1263.65034 |
| [29] | ChronopoulosAT, KucherovAB. Block s‐step Krylov iterative methods. Numer Linear Algebra Appl. 2010;17(1):3-15. · Zbl 1240.65107 |
| [30] | SoodhalterKM. Block Krylov subspace recycling for shifted systems with unrelated right‐hand sides. SIAM J Sci Comput. 2016;38(1):A302-A324. |
| [31] | BirkA. Deflated shifted block Krylov subspace methods for Hermitian positive definite matrices. [PhD thesis]. Wuppertal, Germany: Bergische Universität Wuppertal; 2015. |
| [32] | GiraudL, RuizD, TouhamiA. A comparative study of iterative solvers exploiting spectral information for SPD systems. SIAM J Sci Comput. 2006;27(5):1760-1786. · Zbl 1100.65026 |
| [33] | KaporinIE. Using Chebyshev polynomials and approximate inverse triangular factorization for the preconditioning of the conjugate gradient method. Zh Vychisl Mat Mat Fiz. 2012;52(2):179-204. · Zbl 1245.65035 |
| [34] | BramleyR, SamehA. Row projection methods for large nonsymmetric linear systems. SIAM J Sci Statist Comput. 1992;13(1):168-193. · Zbl 0752.65024 |
| [35] | ElfvingT. Block‐iterative methods for consistent and inconsistent linear equations. Numer Math. 1980;35(1):1-12. · Zbl 0416.65031 |
| [36] | KamathC, SamehA. A projection method for solving nonsymmetric linear systems on multiprocessors. Parallel Computing. 1989;9(3):291-312. · Zbl 0668.65028 |
| [37] | DuffIS, GuivarchR, RuizD, ZenadiM. The augmented block Cimmino distributed method. SIAM J Sci Comput. 2015;37(3):A1248-A1269. · Zbl 1318.65016 |
| [38] | ÇatalyürekÜV, AykanatC. Hypergraph‐partitioning‐based decomposition for parallel sparse‐matrix vector multiplication. IEEE Trans Parallel Distrib Syst. 1999;10(7):673-693. |
| [39] | UçarB, ÇatalyürekÜV, AykanatC. A matrix partitioning interface to PaToH in MATLAB. Parallel Comput. 2010;36(5‐6):254-272. · Zbl 1204.68277 |
| [40] | DuffIS, GrimesRG, LewisJG. Sparse matrix test problems. ACM Trans Softw. 1989;15(1):1-14. · Zbl 0667.65040 |
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.
