A parallel adaptive pseudo transient Newton-Krylov-Schwarz ( NKS) method for the solution of compressible flows is presented. Multidimensional upwind residual distribution schemes are used for space discretisation, while an implicit time-marching scheme is employed for the discretisation of the (pseudo)time derivative. The linear system arising from the Newton method applied to the resulting nonlinear system is solved by the means of Krylov iterations with Schwarz-type preconditioners. A scalable and efficient data structure for the NKS procedure is presented. The main computational kernels are considered, and an extensive analysis is reported to compare the Krylov accelerators, the preconditioning techniques. Results, obtained on a distributed memory computer, are presented for 2D and 3D problems of aeronautical interest on unstructured grids. 1. Introduction The aim of this paper is to provide an overview of the methods required for an efficient parallel solution of the compressible Euler equations (CEE) on unstructured 2D and 3D grids. The ingredients include space and time discretisation schemes for the underlying partial differential equations (PDEs), a nonlinear solver based on the Newton’s method, and a parallel Krylov accelerator with domain decomposition preconditioners. Nowadays, unstructured grids are of particular interest for industrial applications. With respect to structured grids, it is often easier to produce unstructured grids of good quality in domains of complex shape, especially if the unstructured grid generator can be coupled to a CAD system. This can provide—at least in principle—a fast process to solve the problem at hand, with minimal intervention of the user, once the geometry of the domain and the boundary conditions have been specified. However, such techniques imply an almost perfect geometric representation (CAD level) and automatic grid generation remains a challenge in computational engineering, especially for moving boundaries. The framework presented here can be successfully applied to the solution of sets of PDEs problems discretised on unstructured grids. The focus in this paper is restricted to the solution of the CEE. In particular, the space discretisation technique considered is based on the so-called multidimensional upwind residual distribution (MURD) schemes; see for instance [1–5]. These schemes are supposed to render higher accuracy and less spurious numerical anomalies. This is due to the fact that they take into account the multidirectionality of the wave structure, rather than being based upon a summation
References
[1]
“Unstructured grid methods for advection dominated flows,” In AGARD, R-987, 1992.
[2]
H. Deconinck, K. Sermeus, and R. Abgrall, Status of Multidimensional Upwind Residual Distribution Schemes and Applications in Aeronautics, AIAA Paper, 2000.
[3]
P. L. Roe, “Multidimensional upwinding—motivation and concepts,” in 25th VKI Lecture Series on Computational Fluid Dynamics, pp. 94–95, VKI, 1994.
[4]
P. L. Roe and D. Sildikover, “Optimum positive linear schemes for advection in two and three dimension,” Tech. Rep., ICASE, 1989.
[5]
Brite/Euram (OFES N. 97.04271), “Industrial demonstration of accurate and efficient multidimensional upwinding algorithms for aerodynamic simulation IDeMAS,” Tech. Rep., Von Karman Institute, Rhode Saint Genèse, Belgium, 2001.
[6]
P. L. Roe, “Approximate Riemann solvers, parameter vectors, and difference schemes,” Journal of Computational Physics, vol. 43, no. 2, pp. 357–372, 1981.
[7]
P. L. Roe, “Fluctuation and signals—a framework for numerical evolution problems,” in Numerical Methods For Fluid Dynamics, K. W. Morton and M. J. Baines, Eds., pp. 219–257, Academic Press, 1982.
[8]
A. Quarteroni and A. Valli, Domain Decomposition Methods For Partial Differential Equations, Oxford University Press, Oxford, UK, 1999.
[9]
B. F. Smith, P. Bjorstad, and W. D. Gropp, Parallel Multilevel Methods For Elliptic Partial Differential Equations, Cambridge University Press, Cambridge, UK, 1996.
[10]
X. C. Cai, D. E. Keyes, and V. Venkatakrishnan, “Newton-Krylov-Schwarz: an implicit solver for CFD,” in Proceedings of the 8th International Conference on Domain Decom-position Methods, R. Glowinski, Ed., pp. 387–400, 1997.
[11]
W. D. Gropp, D. K. Kaushik, D. E. Keyes, and B. F. Smith, “High-performance parallel implicit CFD,” Parallel Computing, vol. 27, no. 4, pp. 337–362, 2001.
[12]
W. Gropp, D. Keyes, L. C. McInnes, and M. D. Tidriri, “Globalized Newton-Krylov-Schwarz algorithms and software for parallel implicit CFD,” International Journal of High Performance Computing Applications, vol. 14, no. 2, pp. 102–136, 2000.
[13]
E. Nielsen, W. Anderson, R. Walters, and D. E. Keyes, “Application of Newton-Krylov methodology to a three-dimensional unstructured Euler code,” AIAA Paper 95–1733, 1995.
[14]
D. A. Knoll and D. E. Keyes, “Jacobian-free Newton-Krylov methods: a survey of approaches and applications,” Journal of Computational Physics, vol. 193, no. 2, pp. 357–397, 2004.
[15]
C. Y. Huang and F. N. Hwang, “Parallel pseudo-transient Newton-Krylov-Schwarz continuation algorithms for bifurcation analysis of incompressible sudden expansion flows,” Applied Numerical Mathematics, vol. 60, no. 7, pp. 738–751, 2010.
[16]
G. May, F. Iacono, and A. Jameson, “Efficient algorithms for high-order discretizations of the euler and navier-stokes equations,” Tech. Rep., Stanford University, 2009.
[17]
C. Hirsch, Numerical Computation of Internal and External Flow, vol. 2 of Computational Methods for Inviscid and Viscous Flows, John Wiley & Sons, New York, NY, USA, 1990.
[18]
C. Hirsch, Numerical Computation of Internal and External Flow, vol. 1 of Fundamentals of Numerical Discretization, John Wiley & Sons, New York, NY, USA, 1989.
[19]
H. Paillère, Multidimensional upwind residual distribution schemes for the Euler and Navier-stokes equations on unstructured grids [Ph.D. thesis], Université Libre de Bruxelles, Brussels, Belgium, 1995.
[20]
R. Struijs, A multi-dimensional upwind discretization method for the Euler equations on unstructured grids [Ph.D. thesis], The University of Delft, Delft, The Netherlands, 1994.
[21]
R. Struijs, H. Deconinck, and P. Roe, “Fluctuation Splitting Schemes for multidimensional convection problems: an alternative to finite volume and finite element methods,” in Computational Fluid Dynamics, VKI LS, 1990.
[22]
R. Struijs, H. Deconinck, and P. Roe, “Fluctuation splitting schemes for the 2D Euler equations,” in Computational Fluid Dynamics, VKI LS, 1991.
[23]
E. van der Weide, Compressible flow simulations on unstructured grids using multi-dimensional upwind schemes [Ph.D. thesis], Université Libre de Bruxelles, Brussels, Belgium, 1998.
[24]
T. Quintino, M. Ricchiuto, A. Csik, H. Deconinck, and S. Poedts, “Conservative multidimensional upwind residual distribution schemes for arbitrary finite elements,” in Computational Fluid Dynamics 2002, S. Armfield, P. Morgan, and K. Srinivas, Eds., Springer, 2003.
[25]
P. L. Roe, “Discrete models for the numerical analysis of time-dependent multidimensional gas dynamics,” Journal of Computational Physics, vol. 63, no. 2, pp. 458–476, 1986.
[26]
H. Deconinck, C. Hirsch, and J. Peuteman, “Characteristics decomposition methods for the multidimensional Euler equations,” in Proceedings of the International Conference on Numerical Methods in Fluid Dynamics, vol. 264 of Lecture Notes in Physics, pp. 216–221, Springer, Berlin, Heidelberg, June 1986.
[27]
J. Bastin and G. Rogé, “A multidimensional fluctuation splitting scheme for the three dimensional Euler equations,” Mathematical Modelling and Numerical Analysis, vol. 33, no. 6, pp. 1241–1259, 1999.
[28]
M. Sala, Domain decomposition preconditioners: theoretical properties, application to the compressible Euler equations, parallel aspects [Ph.D. thesis], Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, 2003.
[29]
R. S. Dembo, S. C. Eisenstat, and T. Steihaug, “Inexact Newton methods,” SIAM Journal on Numerical Analysis, vol. 19, pp. 400–408, 1982.
[30]
D. Vanderstraeten, á. ？sík, and D. Roose, “An expert-system to control the CFL number of implicit upwind methods,” Tech. Rep., Katholieke Universiteit Leuven, Department of Computer Science, Leuven, Belgium, 2000.
[31]
C. T. Kelley and D. E. Keyes, “Convergence analysis of pseudo-transient continuation,” SIAM Journal on Numerical Analysis, vol. 35, no. 2, pp. 508–523, 1998.
[32]
M. Sala and L. Formaggia, “Algebraic coarse grid operators for domain decomposition based preconditioners,” in Parallel Computational Fluid Dynamics—Practice and Theory, P. Wilders, A. Ecer, J. Periaux, N. Satofuka, and P. Fox, Eds., pp. 119–126, Elsevier, Amsterdam, The Netherlands, 2002.
[33]
L. Jenkins, T. Kelley, C. T. Miller, and C. E. Kees, “An aggregation-based domain decomposition preconditioner for groundwater flow,” Tech. Rep. TR00-13, Department of Mathematics, North Carolina State University, 2000.
[34]
C. Lasser and A. Toselli, “An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems,” Mathematics of Computation, vol. 72, no. 243, pp. 1215–1238, 2003.
[35]
L. Paglieri, A. Scheinine, L. Formaggia, and A. Quarteroni, “Parallel conjugate gradient with Schwarz preconditioner applied to fluid dynamics problems,” in Proceedings of the Parallel Computational Fluid Dynamics, Algorithms and Results Using Advanced Computer (CFD ’97), P. Schiano, Ed., pp. 21–30, 1997.
[36]
C. Lasser and A. Toselli, “Convergence of some two-level overlapping domain decomposition preconditioners with smoothed aggregation coarse spaces,” Tech. Rep. TUM-M0109, Technische Universit？t München, 2001.
P. Leyland, A. Casagrande, and Y. Savoy, “Parallel mesh adaptive techniques illustrated with complex compressible flow simulations,” Modelling and Simulation in Engineering, vol. 2012, Article ID 317359, 14 pages, 2012.
[39]
G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 359–392, 1998.
[40]
P. Leyland and R. Richter, “Completely parallel compressible flow simulations using adaptive unstructured meshes,” Computer Methods in Applied Mechanics and Engineering, vol. 184, no. 2–4, pp. 467–483, 2000.
[41]
M. Sala and L. Formaggia, “Parallel Schur and Schwarz based preconditioners and agglomeration coarse corrections for CFD problems,” Tech. Rep. 15, DMA-EPFL, 2001.
[42]
G. Karypis and V. Kumar, “METIS: unstructured graph partitioning and sparse matrix ordering system,” Tech. Rep., Department of Computer Science, University of Minnesota, 1998.
[43]
G. Karypis and V. Kumar, “ParMETIS: parallel graph partitioning and sparse matrix ordering library,” Tech. Rep. 97-060, Department of Computer Science, University of Minnesota, 1997.
[44]
R. Tuminaro, M. Heroux, S. Hutchison, and J. Shadid, “Official Aztec user’s guide: version 2. 1.,” Tech. Rep. SAND99-8801J, Sandia National Laboratories, Albuquerque, Nm, USA, 1999.
[45]
E. Issman, Implicit solution strategies for compressible flow equations on unstructured grids [Ph.D. thesis], Université Libre de Bruxelles, Brussels, Belgium, 1997.
[46]
R. Abgrall, “Toward the ultimate conservative scheme: following the quest,” Journal of Computational Physics, vol. 167, no. 2, pp. 277–315, 2001.
[47]
G. Degrez, “Implicit time-dependent methods for inviscid and viscous compressible flows, with a discussion of the concept of numerical dissipation,” in Computational Fluid Dynamics, VKI Lecture Series, 2009.
