Preconditioners for multilevel Toeplitz linear systems from steady-state and evolutionary advection-diffusion equations. (English) Zbl 1460.65134
Summary: In this paper, we study preconditioners for multilevel Toeplitz linear systems arising from discretization of steady-state and evolutionary advection-diffusion equations, in which upwind scheme and central difference scheme are employed to discretize first-order and second-order terms, respectively. For the steady-state case, the preconditioner is constructed by replacing each of the discrete advection terms with a square root of the negative of discrete Laplacian matrix and the so constructed preconditioner is diagonalizable by a sine transform. Due to its diagonalizability, the preconditioner can be applied in a two-sided way. We prove that the GMRES solver for the preconditioned linear system has a linear convergence rate independent of discretization step-sizes. The sum of the time discretization and the steady-state preconditioner constitutes the evolutionary preconditioner. A fast implementation is proposed for the evolutionary preconditioner. Moreover, for the evolutionary case, we prove that the modulus of the eigenvalues of the preconditioned matrix is lower and upper bounded by positive constants independent of discretization step-sizes. We test the proposed preconditioners with several Krylov subspace solvers on some advection-dominated advection-diffusion problems and compare their performance with other preconditioners to show its efficiency.
MSC:
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 15B05 | Toeplitz, Cauchy, and related matrices |
| 35P15 | Estimates of eigenvalues in context of PDEs |
Keywords:
steady-state and evolutionary advection-diffusion equation; convergence of GMRES; advection-dominated; fast sine transform; multilevel Toeplitz matrixReferences:
| [1] | Ali, N.; Rahman, R.; Sulaiman, J.; Ghazali, K., SOR iterative method with wave variable transformation for solving advection-diffusion equations, AIP Conf. Proc., 2013, 020036, 607-626 (2018) |
| [2] | Bhatia, R., Matrix Analysis, vol. 169 (2013), Springer Science & Business Media |
| [3] | Brandt, A.; Yavneh, I., Accelerated multigrid convergence and high-Reynolds recirculating flows, SIAM J. Sci. Comput., 14, 3, 607-626 (1993) · Zbl 0770.76039 |
| [4] | Chan, R. H.; Ng, M. K., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 3, 427-482 (1996) · Zbl 0863.65013 |
| [5] | Cockburn, B.; Shu, C.-W., The local discontinuous Galerkin method for time-dependent convection-diffusion systems, SIAM J. Numer. Anal., 35, 6, 2440-2463 (1998) · Zbl 0927.65118 |
| [6] | Codina, R., A discontinuity-capturing crosswind-dissipation for the finite element solution of the convection-diffusion equation, Comput. Methods Appl. Mech. Eng., 110, 3-4, 325-342 (1993) · Zbl 0844.76048 |
| [7] | Commenges, D.; Monsion, M., Fast inversion of triangular Toeplitz matrices, IEEE Trans. Autom. Control, 29, 3, 250-251 (1984) · Zbl 0531.65014 |
| [8] | Dehghan, Mehdi, Quasi-implicit and two-level explicit finite-difference procedures for solving the one-dimensional advection equation, Appl. Math. Comput., 167, 1, 46-67 (2005) · Zbl 1082.65566 |
| [9] | Dehghan, Mehdi, Time-splitting procedures for the solution of the two-dimensional transport equation, Kybernetes (2007) · Zbl 1193.93013 |
| [10] | Dehghan, Mehdi; Shirzadi, Mohammad, Meshless simulation of stochastic advection-diffusion equations based on radial basis functions, Eng. Anal. Bound. Elem., 53, 18-26 (2015) · Zbl 1403.65086 |
| [11] | Dehghan, Mehdi; Dehghani-Madiseh, Marzieh; Hajarian, Masoud, A generalized preconditioned mhss method for a class of complex symmetric linear systems, Math. Model. Anal., 18, 4, 561-576 (2013) · Zbl 1281.65058 |
| [12] | Eckhaus, W., Asymptotic Analysis of Singular Perturbations, vol. 9 (2011), Elsevier |
| [13] | Elman, H. C.; Silvester, D. J.; Wathen, A. J., Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics, Numer. Math. Sci. (2014) · Zbl 1304.76002 |
| [14] | Fattah, Q. N.; Hoopes, J. A., Dispersion in anisotropic, homogeneous, porous media, J. Hydraul. Eng., 111, 5, 810-827 (1985) |
| [15] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), The Johns Hopkins University Press · Zbl 1268.65037 |
| [16] | Grenander, Ulf; Szegö, Gabor, Toeplitz Forms and Their Applications (1958), Univ. of California Press · Zbl 0080.09501 |
| [17] | Gupta, M. M.; Manohar, R. P.; Stephenson, J. W., A single cell high order scheme for the convection-diffusion equation with variable coefficients, Int. J. Numer. Methods Fluids, 4, 7, 641-651 (1984) · Zbl 0545.76096 |
| [18] | Gutknecht, M. H., Variants of bicgstab for matrices with complex spectrum, SIAM J. Sci. Comput., 14, 5, 1020-1033 (1993) · Zbl 0837.65031 |
| [19] | Harten, Amiram; Lax, Peter D.; van Leer, Bram, On upstream differencing and Godunov-type schemes for hyperbolic conservation laws, SIAM Rev., 25, 1, 35-61 (1983) · Zbl 0565.65051 |
| [20] | Hemmingsson, L., A semi-circulant preconditioner for the convection-diffusion equation, Numer. Math., 81, 2, 211-248 (1998) · Zbl 0918.65032 |
| [21] | Isenberg, J.; Gutfinger, C., Heat transfer to a draining film, Int. J. Heat Mass Transf., 16, 2, 505-512 (1973) · Zbl 0257.76082 |
| [22] | Karaa, S.; Zhang, J., Convergence and performance of iterative methods for solving variable coefficient convection-diffusion equation with a fourth-order compact difference scheme, Comput. Math. Appl., 44, 3-4, 457-479 (2002) · Zbl 1055.65117 |
| [23] | Kumar, N., Unsteady flow against dispersion in finite porous media, J. Hydrol., 63, 3-4, 345-358 (1983) |
| [24] | Kurganov, A.; Tadmor, E., New high-resolution central schemes for nonlinear conservation laws and convection-diffusion equations, J. Comput. Phys., 160, 1, 241-282 (2000) · Zbl 0987.65085 |
| [25] | Linß, T., Analysis of an upwind finite-difference scheme for a system of coupled singularly perturbed convection-diffusion equations, Computing, 79, 1, 23-32 (2007) · Zbl 1115.65084 |
| [26] | Lott, P. A.; Elman, H., Fast iterative solver for convection-diffusion systems with spectral elements, Numer. Methods Partial Differ. Equ., 27, 2, 231-254 (2011) · Zbl 1209.65130 |
| [27] | Mohebbi, Akbar; Dehghan, Mehdi, High-order compact solution of the one-dimensional heat and advection-diffusion equations, Appl. Math. Model., 34, 10, 3071-3084 (2010) · Zbl 1201.65183 |
| [28] | Ng, M. K., Iterative methods for Toeplitz systems, Numer. Math. Sci. (2004) · Zbl 1059.65031 |
| [29] | Parlange, J., Water transport in soils, Annu. Rev. Fluid Mech., 12, 1, 77-102 (1980) · Zbl 0465.76092 |
| [30] | Reusken, A., Fourier analysis of a robust multigrid method for convection-diffusion equations, Numer. Math., 71, 3, 365-397 (1995) · Zbl 0833.65130 |
| [31] | Roos, H.-G.; Stynes, M.; Tobiska, L., Robust Numerical Methods for Singularly Perturbed Differential Equations: Convection-Diffusion-Reaction and Flow Problems, vol. 24 (2008), Springer Science & Business Media · Zbl 1155.65087 |
| [32] | Saad, Y., A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018 |
| [33] | Saad, Y., Ilut: a dual threshold incomplete Lu factorization, Numer. Linear Algebra Appl., 1, 4, 387-402 (1994) · Zbl 0838.65026 |
| [34] | Saad, Y., Iterative Methods for Sparse Linear Systems, vol. 82 (2003), SIAM · Zbl 1031.65046 |
| [35] | Saeed, A. M., Fast iterative solver for the 2-d convection-diffusion equations, J. Adv. Math., 9, 6, 2773-2782 (2014) |
| [36] | Salmon, J. R.; Liggett, J. A.; Gallagher, R. H., Dispersion analysis in homogeneous lakes, Int. J. Numer. Methods Eng., 15, 11, 1627-1642 (1980) · Zbl 0457.76016 |
| [37] | Segal, A., Aspects of numerical methods for elliptic singular perturbation problems, SIAM J. Sci. Stat. Comput., 3, 3, 327-649 (1982) · Zbl 0483.65059 |
| [38] | Sleijpen, G. L.; Fokkema, D. R., Bicgstab (l) for linear equations involving unsymmetric matrices with complex spectrum, Electron. Trans. Numer. Anal., 1, 11, 2000 (1993) · Zbl 0820.65016 |
| [39] | Sleijpen, G. L.; Van der Vorst, H. A.; Fokkema, D. R., Bicgstab (l) and other hybrid bi-cg methods, Numer. Algorithms, 7, 1, 75-109 (1994) · Zbl 0810.65027 |
| [40] | Stone, H., A simple derivation of the time-dependent convective-diffusion equation for surfactant transport along a deforming interface, Phys. Fluids A, Fluid Dyn., 2, 1, 111-112 (1990) |
| [41] | Van Loan, C. F., The ubiquitous Kronecker product, J. Comput. Appl. Math., 123, 1-2, 85-100 (2000) · Zbl 0966.65039 |
| [42] | Verfürth, R., A posteriori error estimators for convection-diffusion equations, Numer. Math., 80, 4, 641-663 (1998) · Zbl 0913.65095 |
| [43] | Zhang, J., Accelerated multigrid high accuracy solution of the convection-diffusion equation with high Reynolds number, Numer. Math., 80, 4, 641-663 (1998) · Zbl 0913.65095 |
| [44] | Zhang, J., Preconditioned iterative methods and finite difference schemes for convection-diffusion, Appl. Math. Comput., 109, 1, 11-30 (2000) · Zbl 1023.65110 |
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.
