×

Multiplicative and additive parallel multigrid algorithms for the acceleration of compressible flow computations on unstructured meshes. (English) Zbl 1037.76033

Summary: We examine how parallel multigrid acceleration can be used to improve the efficiency of two-dimensional compressible steady flow calculations on unstructured meshes. We study two parallel multigrid formulations. The first one is based on the standard approach that relies on domain partitioning for the parallel treatment of pre- and post-smoothing steps, whereas the coarse grid levels are visited sequentially according to predefined cycles (V-cycle, F-cycle or W-cycle). When adopting the standard parallelization technique (i.e., intra-level parallelism based on domain partitioning), the usual drawback is that, as the calculation in a given cycling strategy proceeds from the finest level to the coarsest ones, the ratio between communication and calculation becomes worse resulting in a notable degradation of the parallel efficiency. In order to improve this situation, the second formulation considered in this study makes use of residual and correction filtering techniques allowing a parallel treatment of various grid levels. This leads to the notion of inter-level parallelism. We propose distributed memory parallel versions of these two multigrid formulations, and evaluate them through numerical experiments that are performed on a cluster of Pentium Pro computers interconnected via a 100 Mbit/s FastEthernet switch.

MSC:

76M10 Finite element methods applied to problems in fluid mechanics
76M12 Finite volume methods applied to problems in fluid mechanics
76N15 Gas dynamics (general theory)
65Y05 Parallel numerical computation

Software:

Wesseling; Madpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Bastian, W. Hackbusch, G. Wittum, Additive and multiplicative multi-grid: a comparison, Technical Report 95-08, ICA, 1995; P. Bastian, W. Hackbusch, G. Wittum, Additive and multiplicative multi-grid: a comparison, Technical Report 95-08, ICA, 1995 · Zbl 0908.65107
[2] Brandt, A.; Diskin, B., Multigrid solvers on decomposed domains, (Contemporary Mathematics, 157 (1994), Amer. Math. Soc: Amer. Math. Soc Providence, RI), 135-155 · Zbl 0796.65137
[3] Briggs, W.-L., A Multigrid Tutorial (1987), SIAM: SIAM Philadelphia, PA
[4] Carré, G., An implicit multigrid method by agglomeration applied to turbulent flows, Comput. Fluids, 26, 3, 299-320 (1997) · Zbl 0884.76049
[5] T.-F. Chan, R.-S. Tuminaro, Analysis of a parallel multigrid algorithm, Technical Report 89.41, Research Institute for Advanced Computer Science, October 1989; T.-F. Chan, R.-S. Tuminaro, Analysis of a parallel multigrid algorithm, Technical Report 89.41, Research Institute for Advanced Computer Science, October 1989
[6] T.F. Chan, R.S. Tuminaro, Design and implementation of parallel multigrid algorithms, Technical Report 87.21, Research Institute for Advanced Computer Science, August 1987; T.F. Chan, R.S. Tuminaro, Design and implementation of parallel multigrid algorithms, Technical Report 87.21, Research Institute for Advanced Computer Science, August 1987 · Zbl 0652.65076
[7] A. Dervieux, J. Francescatto, Parallel linear multigrid algorithms applied to the acceleration of compressible flows, Technical Report 3462, INRIA, July 1998; A. Dervieux, J. Francescatto, Parallel linear multigrid algorithms applied to the acceleration of compressible flows, Technical Report 3462, INRIA, July 1998 · Zbl 0928.76063
[8] Douglas, C.-C., A Review of Numerous Parallel Multigrid Methods (1996), SIAM: SIAM Philadelphia, PA · Zbl 0900.65344
[9] Fezoui, L.; Dervieux, A., Finite element non-oscillatory schemes for compressible flows, (Proceedings of the 8th France-U.S.S.R.-Italy Joint Symposium on Computational Mathematics and Applications, Pavie, Italy. Proceedings of the 8th France-U.S.S.R.-Italy Joint Symposium on Computational Mathematics and Applications, Pavie, Italy, IAN, 370 (1989)) · Zbl 0702.76074
[10] Fezoui, L.; Stoufflet, B., A class of implicit upwind schemes for Euler simulations with unstructured meshes, J. Comput. Phys., 84, 174-206 (1989) · Zbl 0677.76062
[11] Francescatto, J.; Dervieux, A., A semi-coarsening strategy for unstructured multigrid based on agglomeration, Internat. J. Numer. Methods Fluids, 26, 927-957 (1998) · Zbl 0928.76063
[12] Fredrickson, O.; McBryan, O., Parallel Superconvergent Multigrid. Parallel Superconvergent Multigrid, Lecture Notes in Pure and Applied Mathematics, 110 (1988) · Zbl 0651.65028
[13] Gannon, D.; Van Rosendale, J., On the structure of parallelism in a highly concurrent pde solver, J. Parallel Distrib. Comput., 3, 106-135 (1986)
[14] Hackbusch, W., Multigrid Methods and Applications. Multigrid Methods and Applications, Springer Series in Computational Mathematics, 4 (1985), Springer · Zbl 0577.65118
[15] Jones, J.; McCormick, S., Parallel multigrid algorithms, (Proceedings of the NASA/LaRC Interdisciplinary Series in Science and Engineering. Parallel Numerical Algorithms, Hampton, VA (1997), Kluwer: Kluwer Dordrecht)
[16] Lallemand, M.-H.; Steve, H.; Dervieux, A., Unstructured multigridding by volume agglomeration: current status, Comput. Fluids, 21, 397-433 (1992) · Zbl 0753.76136
[17] Lanteri, S., Parallel solutions of compressible flows using overlapping and non-overlapping mesh partitioning strategies, Parallel Comput., 22, 7, 943-968 (1996) · Zbl 0875.76541
[18] L.R. Matheson, Multigrid algorithms on massively parallel computers, Philosophy, Princeton University (1994); L.R. Matheson, Multigrid algorithms on massively parallel computers, Philosophy, Princeton University (1994) · Zbl 0830.65110
[19] D.J. Mavriplis, Directional agglomeration multigrid techniques for high-Reynolds number viscous flows, Technical Report 98-7, Institute for Computer Applications in Science and Engineering, January 1998; D.J. Mavriplis, Directional agglomeration multigrid techniques for high-Reynolds number viscous flows, Technical Report 98-7, Institute for Computer Applications in Science and Engineering, January 1998
[20] Mavriplis, D. J.; Pirzadeh, S., Large-scale parallel unstructured mesh computations for 3d high-lift analysis, (Proceedings of the 37th AIAA Aerospace Sciences Meeting (1999), AIAA: AIAA Reno, Nevada, USA)
[21] Mavriplis, D. J.; Venkatakrishnan, V., Agglomeration multigrid for two-dimensional viscous flows, J. Comput. Phys., 24, 553-570 (1995) · Zbl 0846.76047
[22] Mavriplis, D. J.; Venkatakrishnan, V., A 3d agglomeration multigrid solver for the Reynolds-averaged Navier-Stokes equations on unstructure meshes, Internat. J. Numer. Methods Fluids, 23, 527-544 (1996) · Zbl 0884.76043
[23] Roe, P. L., Approximate Riemann solvers, parameter vectors and difference schemes, J. Comput. Phys., 43, 357-371 (1981) · Zbl 0474.65066
[24] Steger, J.; Warming, R. F., Flux vector splitting for the inviscid gas dynamic equations with applications to finite difference methods, J. Comput. Phys., 40, 263-293 (1981) · Zbl 0468.76066
[25] Tuminaro, R.-S., A highly parallel multigrid-like method for the solution of the Euler equations, SIAM J. Sci. Statist. Comput., 13, 1, 88-100 (1992) · Zbl 0742.76068
[26] Van Leer, B., Towards the ultimate conservative difference scheme V: a second-order sequel to Godunov’s method, J. Comput. Phys., 32, 361-370 (1979) · Zbl 1364.65223
[27] Wesseling, P., An Introduction to Multigrid Methods (1991), Wiley: Wiley New York
[28] Wienands, R., Fourier analysis of GMRES \((m)\) preconditioned by multigrid, (Proceedings of the 9th Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO (1999)) · Zbl 0967.65101
[29] D. Xie, R. Scott, The parallel U-cycle multigrid method, Technical Report UH/MD 240, Department of Mathematics, University of Houston, 1997; D. Xie, R. Scott, The parallel U-cycle multigrid method, Technical Report UH/MD 240, Department of Mathematics, University of Houston, 1997
[30] Xu, J., Iterative methods by space decomposition and subspace correction, SIAM Rev., 34, 4, 581-613 (1992) · Zbl 0788.65037
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.