×

Reliability investigation of BiCGStab and IDR solvers for the advection-diffusion-reaction equation. (English) Zbl 1492.65081

Summary: The reliability of BiCGStab and IDR solvers for the exponential scheme discretization of the advection-diffusion-reaction equation is investigated. The resulting discretization matrices have real eigenvalues. We consider BiCGStab, IDR\((S),\) BiCGStab\((L)\) and various modifications of BiCGStab, where \(S\) denotes the dimension of the shadow space and \(L\) the degree of the polynomial used in the polynomial part. Several implementations of BiCGStab exist which are equivalent in exact arithmetic, however, not in finite precision arithmetic. The modifications of BiCGStab we consider are; choosing a random shadow vector, a reliable updating scheme, and storing the best intermediate solution. It is shown that the Local Minimal Residual algorithm, a method similar to the “minimize residual” step of BiCGStab, can be interpreted in terms of a time-dependent advection-diffusion-reaction equation with homogeneous Dirichlet boundary conditions for the residual, which plays a key role in the convergence analysis. Due to the real eigenvalues, the benefit of BiCGStab\((L)\) compared to BiCGStab is shown to be modest in numerical experiments. Non-sparse (e.g. uniform random) shadow residual turns out to be essential for the reliability of BiCGStab. The reliable updating scheme ensures the required tolerance is truly achieved. Keeping the best intermediate solution has no significant effect. Recommendation is to modify BiCGStab with a random shadow residual and the reliable updating scheme, especially in the regime of large Péclet and small Damköhler numbers. An alternative option is IDR\((S)\), which outperforms BiCGStab for problems with strong advection in terms of the number of matrix-vector products. The MATLAB code used in the numerical experiments is available on GitLab: https://gitlab.com/ChrisSchoutrop/krylov-adr, a C++ implementation of IDR\((S)\) is available in the Eigen linear algebra library: http://eigen.tuxfamily.org.

MSC:

65F10 Iterative numerical methods for linear systems
15A06 Linear equations (linear algebraic aspects)
15A18 Eigenvalues, singular values, and eigenvectors
15B05 Toeplitz, Cauchy, and related matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Martinez, A. Dhruv, L. Lin, E. Balaras, M. Keidar, Interaction between a helium atmo-spheric plasma jet and targets and dynamics of the interface, Plasma Sources Science and Technology, 28 (2019):115002.
[2] D.A. Knoll, P.R. McHugh, Newton-Krylov methods applied to a system of convection-diffusion-reaction equations, Computer Physics Communications, 88 (1995):141-160. · Zbl 0923.76199
[3] J. Lin, S. Reutskiy, C. Chen, J. Lu, A novel method for solving time-dependent 2D advection-diffusion-reaction equations to model transfer in nonlinear anisotropic media, Communica-tions in Computational Physics, 26 (2019):233-264. · Zbl 1473.65330
[4] B. Fischer, A. Ramage, D.J. Silvester, A.J. Wathen, On parameter choice and iterative conver-gence for stabilised discretisations of advection-diffusion problems, Computer Methods in Applied Mechanics and Engineering, 179 (1999):179-195. · Zbl 0977.76043
[5] A. Singh, S. Das, S.H. Ong, H. Jafari, Numerical solution of nonlinear reaction-advection-diffusion equation, Journal of Computational and Nonlinear Dynamics, 14 (2019).
[6] S. Patankar, Numerical Heat Transfer and Fluid Flow, Taylor & Francis, 2018.
[7] D.L. Scharfetter, H.K. Gummel, Large-signal analysis of a silicon read diode oscillator, IEEE Transactions on Electron Devices, 16 (1969):64-77.
[8] Y. Saad, Iterative Methods for Sparse Linear Systems: Second Edition, SIAM, 2003. · Zbl 1031.65046
[9] H.A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, volume 13, Cam-bridge University Press, 2003. · Zbl 1023.65027
[10] J.R. Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, Technical report, Carnegie Mellon University, 1994.
[11] V. Faber, T. Manteuffel, Necessary and sufficient conditions for the existence of a conjugate gradient method, SIAM Journal on Numerical Analysis, 21 (1984):352-362. · Zbl 0546.65010
[12] J. Liesen, Z. Strakoˇs, On optimal short recurrences for generating orthogonal Krylov sub-space bases, SIAM Review, 50 (2008):485-503. · Zbl 1148.65023
[13] C. Lanczos, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards, 49 (1952):33-53.
[14] H.A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Com-puting, 13 (1992):631-644. · Zbl 0761.65023
[15] MATLAB, R2019a, The MathWorks Inc., 2019.
[16] G. Guennebaud, B. Jacob, et al., Eigen, URl: http://eigen.tuxfamily.org, (2010).
[17] J. Van Dijk, K. Peerenboom, M. Jimenez, D. Mihailova, J. Van der Mullen, The plasma mod-elling toolkit PLASIMO, Journal of Physics D: Applied Physics, 42 (2009):194012.
[18] COMSOL Multiphysics v. 5.6. www.comsol.com. COMSOL AB, Stockholm, Sweden.
[19] G.L.G. Sleijpen, H.A. Van der Vorst, Optimal iteration methods for large linear systems of equations, Notes on Numerical Fluid Mechanics, 45 (1993):291-291. · Zbl 0807.76066
[20] Y. Saad, M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, 7 (1986):856-869. · Zbl 0599.65018
[21] G.L.G. Sleijpen, H.A. van der Vorst, D.R. Fokkema, BiCGstab (ell) for linear equations in-volving unsymmetric matrices with complex spectrum, Electronic Transactions on Numeri-cal Analysis, 1 (1993):11-32. · Zbl 0820.65016
[22] P. Sonneveld, M.B. van Gijzen, IDR(s): A family of simple and fast algorithms for solving large nonsymmetric systems of linear equations, SIAM Journal on Scientific Computing, 31 (2008):1035-1062. · Zbl 1190.65053
[23] G.L.G. Sleijpen, M.B. van Gijzen, Exploiting BiCGstab (l) strategies to induce dimension reduction, SIAM Journal on Scientific Computing, 32 (2010):2687-2709. · Zbl 1220.65042
[24] G.L.G. Sleijpen, H.A. van der Vorst, D.R. Fokkema, BiCGstab (l) and other hybrid Bi-CG methods, Numerical Algorithms, 7 (1994):75-109. · Zbl 0810.65027
[25] K. Aihara, K. Abe, E. Ishiwata, A variant of IDRstab with reliable update strategies for solving sparse linear systems, Journal of Computational and Applied Mathematics, 259 (2014):244-258. · Zbl 1291.65093
[26] L.T. Yang, R.P. Brent, The improved BiCGStab method for large and sparse unsymmetric linear systems on parallel distributed memory architectures, in Fifth International Confer-ence on Algorithms and Architectures for Parallel Processing, 2002. Proceedings, IEEE, 2002 324-328.
[27] S. Cools, W. Vanroose, The communication-hiding pipelined BiCGStab method for the par-allel solution of large unsymmetric linear systems, Parallel Computing, 65 (2017):1-20.
[28] A. El Guennouni, K. Jbilou, H. Sadok, A block version of BiCGSTAB for linear systems with multiple right-hand sides, Electronic Transactions on Numerical Analysis, 16 (2003):2. · Zbl 1065.65052
[29] K. Ahuja, P. Benner, E. de Sturler, L. Feng, Recycling BiCGSTAB with an application to para-metric model order reduction, SIAM Journal on Scientific Computing, 37 (2015):429-446. · Zbl 1325.65044
[30] D.R. Fokkema, Enhanced Implementation of BiCGstab (l) for Solving Linear Systems of Equations, 1996.
[31] G.L.G. Sleijpen and H.A. van der Vorst, Reliable updated residuals in hybrid Bi-CG methods, Computing, 56 (1996):141-163. · Zbl 0842.65018
[32] J. Liesen, P. Tichỳ, Convergence analysis of Krylov subspace methods, GAMM-Mitteilungen, 27 (2004):153-173. · Zbl 1071.65041
[33] W. Joubert, Lanczos methods for the solution of nonsymmetric systems of linear equations, SIAM Journal on Matrix Analysis and Applications, 13 (1992):926-943. · Zbl 0758.65026
[34] Y. Yasuda. S. Sakamoto, Y. Kosaka, T. Sakuma, N. Okamoto, T. Oshima, Numerical analysis of large-scale sound fields using iterative methods part I: Application of Krylov subspace methods to boundary element analysis, Journal of Computational Acoustics, 15 (2007):449-471.
[35] N. Okamoto, R. Tomiku, T. Otsuru, Y. Yasuda, Numerical analysis of large-scale sound fields using iterative methods part II: Application of Krylov subspace methods to finite element analysis, Journal of Computational Acoustics, 15 (2007):473-493.
[36] J. Spanier, K.B. Oldham, An Atlas of Functions, Hemisphere Publishing Corporation New York, 1987. · Zbl 0618.65007
[37] M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, volume 55, US Government printing office, 1964. · Zbl 0171.38503
[38] S. Noschese, L. Pasquini, L. Reichel, Tridiagonal Toeplitz matrices: Properties and novel applications, Numerical Linear Algebra with Applications, 20 (2013):302-326. · Zbl 1289.65082
[39] R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, 1991, Cambridge University Presss, Cambridge, 37 (1991):39. · Zbl 0729.15001
[40] V. Khoromskaia, B.N. Khoromskij, F. Otto, Numerical study in stochastic homogenization for elliptic partial differential equations: Convergence rate in the size of representative vol-ume elements, Numerical Linear Algebra with Applications, 27 (2020):2296. · Zbl 07217205
[41] O.G. Ernst, Residual-minimizing Krylov subspace methods for stabilized discretizations of convection-diffusion equations, SIAM Journal on Matrix Analysis and Applications, 21 (2000):1079-1101. · Zbl 0961.65098
[42] H.C. Elman, D.J. Silvester and A.J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, Oxford University Press, USA, 2014. · Zbl 1304.76002
[43] C.F. van Loan, G.H. Golub, Matrix Computations, Johns Hopkins University Press, 1983. · Zbl 0559.65011
[44] F. Hiai, D. Petz, Introduction to Matrix Analysis and Applications, Springer Science & Busi-ness Media, 2014. · Zbl 1303.15001
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.