Optimizing a multigrid Runge-Kutta smoother for variable-coefficient convection-diffusion equations. (English) Zbl 1375.35359
Summary: The theory of Generally Locally Toeplitz (or GLT for short) sequences of matrices is proposed in the analysis of a multigrid solver for the linear systems generated by finite volume/finite difference approximations of variable-coefficients linear convection-diffusion equations in 1D, proposed by Birken in 2012, and extended here to 2D problems. The multigrid solver is used with a Runge-Kutta smoother. Optimal coefficients for the smoother are found by considering the unsteady linear advection equation and using optimization algorithms. In particular, in order to reduce the issues of having multiple local minima, the sequential quadratic programming (SQP) mixed with genetic and particle swarm optimization algorithms are proposed. Numerical results show that our proposals are competitive with respect to other multigrid implementations.
MSC:
| 35Q35 | PDEs in connection with fluid mechanics |
| 15B05 | Toeplitz, Cauchy, and related matrices |
| 65M55 | Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs |
| 76M12 | Finite volume methods applied to problems in fluid mechanics |
| 90C26 | Nonconvex programming, global optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 65L06 | Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
Keywords:
multigrid; unsteady flows; finite volume methods; explicit Runge-Kutta methods; linear advection equations; GLTReferences:
| [1] | Birken, P., Optimizing Runge-Kutta smoothers for unsteady flow problems, Electron. Trans. Numer. Anal., 39, 298-312 (2012) · Zbl 1291.76213 |
| [2] | Caughey, D.; Jameson, A., How many steps are required to solve the Euler equations of steady compressible flow: in search of a fast solution algorithm, AIAA J., 2001-2673 (2001) |
| [3] | Notay, Y., An aggregation-based algebraic multigrid method, Electron. Trans. Numer. Anal., 37, 123-146 (2010) · Zbl 1206.65133 |
| [4] | Notay, Y., Aggregation-based algebraic multigrid for convection-diffusion equations, SIAM J. Sci. Comput., 34, A2288-A2316 (2012) · Zbl 1250.76139 |
| [5] | Gupta, M. M.; Zhang, J., High accuracy multigrid solution of the 3d convection-diffusion equation, Appl. Math. Comput., 113, 249-274 (2000) · Zbl 1023.65127 |
| [6] | Zhang, J., Accelerated multigrid high accuracy solution of the convection-diffusion equation with high Reynolds number, Numer. Methods Partial Differential Equations, 13, 77-92 (1997) · Zbl 0868.76063 |
| [7] | Bey, J.; Wittum, G., Downwind numbering: robust multigrid for convection-diffusion problems, Appl. Numer. Math., 23, 177-192 (1997) · Zbl 0879.65088 |
| [8] | Van Leer, B.; Lee, W.-T.; Roe, P. L.; Powell, K. G.; Tai, C.-H., Design of optimally smoothing multistage schemes for the Euler equations, Commun. Appl. Numer. Methods, 8, 761-769 (1992) · Zbl 0758.76043 |
| [9] | Böttcher, A.; Grudsky, S. M., Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis (2000), Birkhäuser Verlag · Zbl 0969.47022 |
| [10] | Bertaccini, D.; Golub, G. H.; Serra-Capizzano, S., Spectral analysis of a preconditioned iterative method for the convection-diffusion equation, SIAM J. Matrix Anal. Appl., 29, 260-278 (2007) · Zbl 1140.65024 |
| [11] | Serra-Capizzano, S., Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations, Linear Algebra Appl., 366, 371-402 (2003), Special issue on Structured Matrices: Analysis, Algorithms and Applications · Zbl 1028.65109 |
| [12] | Serra-Capizzano, S., The GLT class as a generalized Fourier analysis and applications, Linear Algebra Appl., 419, 180-233 (2006) · Zbl 1109.65032 |
| [13] | Beckermann, B.; Serra-Capizzano, S., On the asymptotic spectrum of finite element matrix sequences, SIAM J. Numer. Anal., 45, 746-769 (2007) · Zbl 1140.65080 |
| [14] | Donatelli, M.; Molteni, M.; Pennati, V.; Serra-Capizzano, S., Multigrid methods for cubic spline solution of two point (and 2d) boundary value problems, Appl. Numer. Math., 104, 15-29 (2016) · Zbl 1336.65120 |
| [15] | Donatelli, M.; Garoni, C.; Manni, C.; Serra-Capizzano, S.; Speleers, H., Spectral analysis and spectral symbol of matrices in isogeometric collocation methods, Math. Comp., 85, 1639-1680 (2016) · Zbl 1335.65096 |
| [16] | Tilli, P., Locally Toeplitz sequences: spectral properties and applications, Linear Algebra Appl., 278, 91-120 (1998) · Zbl 0934.15009 |
| [17] | Haelterman, R.; Vierendeels, J.; Heule, D. V., A generalization of the Runge-Kutta iteration, J. Comput. Appl. Math., 224, 152-167 (2009) · Zbl 1189.65061 |
| [18] | Serra-Capizzano, S., Distribution results on the algebra generated by Toeplitz sequences: a finite-dimensional approach, Linear Algebra Appl., 328, 121-130 (2001) · Zbl 1003.15008 |
| [19] | Garoni, C.; Serra-Capizzano, S., The Theory of Generalized Locally Toeplitz Sequences: Theory and Applications - Vol. I, Springer Monographs (2017) · Zbl 1376.15002 |
| [20] | Rood, R. B., Numerical advection algorithms and their role in atmospheric transport and chemistry models, Rev. Geophys., 25, 71-100 (1987) |
| [21] | Laub, A. J., Matrix Analysis for Scientists and Engineers (2005), SIAM · Zbl 1077.15001 |
| [22] | Golinskii, L.; Serra-Capizzano, S., The asymptotic properties of the spectrum of nonsymmetrically perturbed Jacobi matrix sequences, J. Approx. Theory, 144, 84-102 (2007) · Zbl 1111.15013 |
| [23] | Garoni, C.; Serra-Capizzano, S.; Sesana, D., Tools for determining the asymptotic spectral distribution of non-Hermitian perturbations of Hermitian matrix-sequences and applications, Integral Equations Operator Theory, 81, 213-225 (2015) · Zbl 1337.47045 |
| [24] | Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [25] | Van der Vorst, H. A., Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 13, 631-644 (1992) · Zbl 0761.65023 |
| [26] | Tai, C.-H.; Sheu, J.-H.; Van Leer, B., Optimal multistage schemes for Euler equations with residual smoothing, AIAA J., 33, 1008-1016 (1995) · Zbl 0845.76062 |
| [27] | Bassi, F.; Ghidoni, A.; Rebay, S., Optimal Runge-Kutta smoothers for the p-multigrid discontinuous Galerkin solution of the 1d Euler equations, J. Comput. Phys., 4153-4175 (2010) · Zbl 1220.65130 |
| [28] | Brayton, R. K.; Director, S.; Hachtel, G. D.; Vidigal, L. M., A new algorithm for statistical circuit design based on quasi-Newton methods and function splitting, IEEE Trans. Circuits Syst. I. Regul. Pap., 26, 784-794 (1979) |
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.
