An assessment of linear versus nonlinear multigrid methods for unstructured mesh solvers. (English) Zbl 0995.65099
Summary: The relative performance of a nonlinear full approximation storage multigrid algorithm and an equivalent linear multigrid algorithms for solving two different nonlinear problems is investigated. The first case consists of a transient radiation diffusion problem for which an exact linearization is available, while the second problem involves the solution of the steady-state Navier-Stokes equations, where a first-order discrete Jacobian is employed as an approximation to the Jacobian of a second-order-accurate discretization.
When an exact linearization is employed, the linear and nonlinear multigrid methods asymptotically converge at identical rates and the linear method is found to be more efficient due to its lower cost per cycle. When an approximate linearization is employed, as in the Navier-Stokes cases, the relative efficiency of the linear approach versus the nonlinear approach depends both on the degree to which the linear system approximates the full Jacobian as well as on the relative cost of linear versus nonlinear multigrid cycles.
For cases where convergence is limited by a poor Jacobian approximation, substantial speedup can be obtained using either multigrid method as a preconditioners to a Newton-Krylov method.
When an exact linearization is employed, the linear and nonlinear multigrid methods asymptotically converge at identical rates and the linear method is found to be more efficient due to its lower cost per cycle. When an approximate linearization is employed, as in the Navier-Stokes cases, the relative efficiency of the linear approach versus the nonlinear approach depends both on the degree to which the linear system approximates the full Jacobian as well as on the relative cost of linear versus nonlinear multigrid cycles.
For cases where convergence is limited by a poor Jacobian approximation, substantial speedup can be obtained using either multigrid method as a preconditioners to a Newton-Krylov method.
MSC:
| 65M55 | Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs |
| 65M06 | Finite difference methods for initial value and initial-boundary value problems involving PDEs |
| 65M12 | Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65H10 | Numerical computation of solutions to systems of equations |
| 35K55 | Nonlinear parabolic equations |
| 35Q30 | Navier-Stokes equations |
Keywords:
unstructured mesh; linear multigrid; transient radiation diffusion problem; Navier-Stokes equations; linearization; nonlinear multigrid; convergence; preconditioners; Newton-Krylov methodReferences:
| [1] | Brandt, A., Multigrid techniques with applications to fluid dynamics: 1984 guide, VKI Lecture Series, 1 (1984) · Zbl 0581.76033 |
| [2] | Hackbush, W., Multigrid Methods and Applications (1985), Springer-Verlag: Springer-Verlag Berlin · Zbl 0595.65106 |
| [3] | Jameson, A., Solution of the Euler equations by a multigrid method, Appl. Math. Comput., 13, 327 (1983) · Zbl 0545.76065 |
| [4] | J. L. Thomas, D. L. Bonhaus, and, W. K. Anderson, An \((O) (nm^2\); J. L. Thomas, D. L. Bonhaus, and, W. K. Anderson, An \((O) (nm^2\) |
| [5] | Carre, G., An implicit multigrid method by agglomeration applied to turbulent flows, Comput. Fluids, 26, 299 (1997) · Zbl 0884.76049 |
| [6] | M. Raw, Robustness of Coupled Algebraic Multigrid for the Navier-Stokes Equations; M. Raw, Robustness of Coupled Algebraic Multigrid for the Navier-Stokes Equations |
| [7] | Mousseau, V. A.; Knoll, D. A.; Rider, W. J., Physics-based preconditioning and the Newton-Krylov method for non-equilibrium radiation diffusion, J. Comput. Phys., 160, 743 (2000) · Zbl 0949.65092 |
| [8] | P. N. Brown, and, C. S. Woodward, Preconditioning Strategies for Fully Implicit Radiation Diffusion With Material Energy Transfer; P. N. Brown, and, C. S. Woodward, Preconditioning Strategies for Fully Implicit Radiation Diffusion With Material Energy Transfer · Zbl 0992.65102 |
| [9] | E. J. Nielsen, W. K. Anderson, R. W. Walters, and, D. E. Keyes, Application of Newton-Krylov methodology to a three-dimensional unstructured Euler code, in, Proceedings of the 12th AIAA CFD Conference, San Diego, CA, June 1995, AIAA Paper 95-1733-CP.; E. J. Nielsen, W. K. Anderson, R. W. Walters, and, D. E. Keyes, Application of Newton-Krylov methodology to a three-dimensional unstructured Euler code, in, Proceedings of the 12th AIAA CFD Conference, San Diego, CA, June 1995, AIAA Paper 95-1733-CP. |
| [10] | Mavriplis, D. J.; Pirzadeh, S., Large-scale parallel unstructured mesh computations for 3D high-lift analysis, AIAA J. Aircraft, 36, 987 (1999) |
| [11] | D. J. Mavriplis, On Convergence Acceleration Techniques for Unstructured Meshes; D. J. Mavriplis, On Convergence Acceleration Techniques for Unstructured Meshes |
| [12] | Lallemand, M.; Steve, H.; Dervieux, A., Unstructured multigridding by volume agglomeration: Current status, Comput. Fluids, 21, 397 (1992) · Zbl 0753.76136 |
| [13] | W. A. Smith, Multigrid solution of transonic flow on unstructured grids, in, Recent Advances and Applications in Computational Fluid Dynamics. Proceedings of the ASME Winter Annual Meeting November 1990, edited by, O. Baysal, ASME, New York, 1990.; W. A. Smith, Multigrid solution of transonic flow on unstructured grids, in, Recent Advances and Applications in Computational Fluid Dynamics. Proceedings of the ASME Winter Annual Meeting November 1990, edited by, O. Baysal, ASME, New York, 1990. |
| [14] | Venkatakrishnan, V.; Mavriplis, D. J., Agglomeration multigrid for the three-dimensional Euler equations, AIAA J., 33, 633 (1995) · Zbl 0925.76477 |
| [15] | Mavriplis, D. J., Multigrid techniques for unstructured meshes, VKI Lecture Series VKI-LS 1995-02 (1995) · Zbl 0890.76069 |
| [16] | J. W. Ruge and K. Stüben, Algebraic multigrid, in Multigrid Methods, edited by S. F. McCormickSoc. for Industr. & Appl. Math. Philadelphia, 1987, pp. 73-131.; J. W. Ruge and K. Stüben, Algebraic multigrid, in Multigrid Methods, edited by S. F. McCormickSoc. for Industr. & Appl. Math. Philadelphia, 1987, pp. 73-131. |
| [17] | N. Pierce, M. Giles, A. Jameson, and, L. Martinelli, Accelerating three-dimensional Navier-Stokes calculations, in, Proceedings of the 13th AIAA CFD Conference, Snowmass Village, CO, June 1997, AIAA Paper 97-1953.; N. Pierce, M. Giles, A. Jameson, and, L. Martinelli, Accelerating three-dimensional Navier-Stokes calculations, in, Proceedings of the 13th AIAA CFD Conference, Snowmass Village, CO, June 1997, AIAA Paper 97-1953. |
| [18] | B. van Leer, W. T. Lee, and, P. Roe, Characteristic time-stepping or local preconditioning of the Euler equations, in, Proceedings of the 10th AIAA CFD Conference, Honolulu, HI, June 1991, AIAA Paper 91-1552-CP.; B. van Leer, W. T. Lee, and, P. Roe, Characteristic time-stepping or local preconditioning of the Euler equations, in, Proceedings of the 10th AIAA CFD Conference, Honolulu, HI, June 1991, AIAA Paper 91-1552-CP. |
| [19] | E. Turkel, Preconditioning-squared methods for multidimensional aerodynamics, in, Proceedings of the 13th AIAA CFD Conference, Snowmass, CO, June 1997, AIAA Paper 97-2025-CP.; E. Turkel, Preconditioning-squared methods for multidimensional aerodynamics, in, Proceedings of the 13th AIAA CFD Conference, Snowmass, CO, June 1997, AIAA Paper 97-2025-CP. |
| [20] | Mavriplis, D. J., Multigrid strategies for viscous flow solvers on anisotropic unstructured meshes, J. Comput. Phys., 145, 141 (1998) · Zbl 0926.76066 |
| [21] | Knoll, D. A.; Rider, W. J.; Olson, G. L., An efficient nonlinear solution method for nonequilibrium radiation diffusion, J. Quant. Spectrosc. Radiat. Transfer, 63, 15 (1999) |
| [22] | Roe, P. L., Approximate Riemann solvers, parameter vectors and difference schemes, J. Comput. Phys., 43, 357 (1981) · Zbl 0474.65066 |
| [23] | Spalart, P. R.; Allmaras, S. R., A. one-equation turbulence model for aerodynamic flows, Rech. Aerosp., 1, 5 (1994) |
| [24] | Mavriplis, D. J., Directional agglomeration multigrid techniques for high-Reynolds number viscous flows, AIAA J., 37, 1222 (1999) |
| [25] | B. van Leer, C. H. Tai, and, K. G. Powell, Design of Optimally-Smoothing Multi-stage Schemes for the Euler Equations; B. van Leer, C. H. Tai, and, K. G. Powell, Design of Optimally-Smoothing Multi-stage Schemes for the Euler Equations · Zbl 0758.76043 |
| [26] | L. Martinelli, and, A. Jameson, Validation of a Multigrid Method for the Reynolds-; L. Martinelli, and, A. Jameson, Validation of a Multigrid Method for the Reynolds- |
| [27] | Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing Co. Boston · Zbl 1002.65042 |
| [28] | Venkatakrishnan, V.; Mavriplis, D. J., Implicit solvers for unstructured meshes, J. Comput. Phys., 105, 83 (1993) · Zbl 0783.76065 |
| [29] | L. B. Wigton, N. J. Yu, and, D. P. Young, GMRES acceleration of computational fluid dynamic codes, in, Proceedings of the 7th AIAA CFD Conference, July 1985, AIAA Paper 85-1494-CP.; L. B. Wigton, N. J. Yu, and, D. P. Young, GMRES acceleration of computational fluid dynamic codes, in, Proceedings of the 7th AIAA CFD Conference, July 1985, AIAA Paper 85-1494-CP. |
| [30] | D. Jespersen, T. Pulliam, and, P. Buning, Recent Enhancements to OVERFLOW; D. Jespersen, T. Pulliam, and, P. Buning, Recent Enhancements to OVERFLOW |
| [31] | Stals, L., The parallel solution of radiation transport equations, Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, Portsmouth, VA, March 2001 (2001) |
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.
