×

A new domain decomposition method with overlapping patches for ultrascale simulations: application to biological flows. (English) Zbl 1193.92029

Summary: We address the failure in scalability of large-scale parallel simulations that are based on (semi-)implicit time-stepping and hence on the solution of linear systems on thousands of processors. We develop a general algorithmic framework based on domain decomposition that removes the scalability limitations and leads to optimal allocation of available computational resources. It is a non-intrusive approach as it does not require modification of existing codes. Specifically, we present here a two-stage domain decomposition method for the Navier-Stokes equations that combines features of discontinuous and continuous Galerkin formulations. At the first stage the domain is subdivided into overlapping patches and within each patch a \(C^{0}\) spectral element discretization (second stage) is employed. Solution within each patch is obtained separately by applying an efficient parallel solver. Proper inter-patch boundary conditions are developed to provide solution continuity, while a Multilevel Communicating Interface (MCI) is developed to provide efficient communication between the non-overlapping groups of processors of each patch. The overall strong scaling of the method depends on the number of patches and on the scalability of the standard solver within each patch.
This dual path to scalability provides great flexibility in balancing accuracy with parallel efficiency. The accuracy of the method has been evaluated in solutions of steady and unsteady 3D flow problems including blood flow in the human intracranial arterial tree. Benchmarks on BlueGene/P, CRAY XT5 and Sun Constellation Linux Cluster have demonstrated good performance on up to 96,000 cores, solving up to 8.21B degrees of freedom in unsteady flow problem. The proposed method is general and can be potentially used with other discretization methods or in other applications.

MSC:

92C35 Physiological flow
76D05 Navier-Stokes equations for incompressible viscous fluids
68U99 Computing methodologies and applications
68U20 Simulation (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] International assessment of research and development in simulation-based engineering and science, WTEC Panel Report, 2009. Available from: <www.wtec.org>; International assessment of research and development in simulation-based engineering and science, WTEC Panel Report, 2009. Available from: <www.wtec.org>
[2] (Keyes, D.; Colella, P.; Dunning, T. H.; Gropp, W. D., A Science-based Case for Large-scale Simulation, vols. 1&2 (2003), Office of Science, U.S. Department of Energy (DOE): Office of Science, U.S. Department of Energy (DOE) Washington, DC)
[3] Grinberg, L.; Karniadakis, G. E., A scalable domain decomposition method for ultra-parallel arterial flow simulations, Commun. Comput. Phys., 4, 5, 1151-1169 (2008) · Zbl 1364.76249
[4] Chen, H.; Lazarov, R. D., Domain splitting algorithm for mixed finite element approximations to parabolic problems, East-West J. Numer. Math., 4, 121-135 (1995) · Zbl 0878.65081
[5] Hebeker, F. K.; Kuznetsov, Yu. A., Unsteady convection and convection-diffusion problems via direct overlapping domain decomposition methods, Numer. Meth. Partial Differential Equations, 14, 3, 387-406 (1997) · Zbl 0919.65058
[6] Hebeker, F. K., A domain splitting method for heat conduction problems in composite materials, Math. Model. Numer. Anal., 34, 1, 47-62 (2000) · Zbl 0952.65070
[7] Wu, Z. N.; Zou, H., Grid overlapping for implicit parallel computations of compressible flows, J. Comput. Phys., 157, 243 (2000)
[8] Wu, Z. N.; Zou, H., Efficient parallel method for implicit upwind schemes approximating the Euler equations in gas dynamics, J. Comput. Phys., 187, 2, 683-715 (2003) · Zbl 1061.76052
[9] X. Tai, T. Johansen, H. Dahle, M.A. Espedal, Characteristic domain splitting method, in: Glowinski et al. (Eds.), Domain Decomposition Methods in Science and Engineering, Proceedings of 8th International Conference on Domain Decomposition Methods, Wiley, New York, 1997, pp. 317-323.; X. Tai, T. Johansen, H. Dahle, M.A. Espedal, Characteristic domain splitting method, in: Glowinski et al. (Eds.), Domain Decomposition Methods in Science and Engineering, Proceedings of 8th International Conference on Domain Decomposition Methods, Wiley, New York, 1997, pp. 317-323.
[10] Wang, H.; Liu, J.; Espedal, M. S.; Ewing, R. E., A characteristic nonoverlapping domain decomposition method for multidimensional convection-diffusion equations, Numer. Methods Partial Differential Equations, 21, 1, 89-103 (2004) · Zbl 1059.65087
[11] C. Bernardi, Y. Maday, A.A. Patera, New nonconforming approach to domain decomposition: the mortar element method, in: H. Brezis, J.L. Lions (Eds.), Nonlinear PDEs and their Applications, Collegede France Seminar 1994: vol XI, Pitman Research Notes in Math. Series 299, Longman, London.; C. Bernardi, Y. Maday, A.A. Patera, New nonconforming approach to domain decomposition: the mortar element method, in: H. Brezis, J.L. Lions (Eds.), Nonlinear PDEs and their Applications, Collegede France Seminar 1994: vol XI, Pitman Research Notes in Math. Series 299, Longman, London. · Zbl 0797.65094
[12] Cai, X.; Dryja, M.; Sarkis, M., Overlapping nonmatching grid mortar element methods for elliptic problems, SIAM J. Numer. Anal., 36, 581-606 (1999) · Zbl 0927.65131
[13] Bjørstad, P. E.; Widlund, O. B., To overlap or not to overlap: a note on a domain decomposition method for elliptic problems, SIAM J. Sci. Statist. Comput., 10, 5, 1053-1061 (1989) · Zbl 0678.65069
[14] Dryja, M.; Widlund, O. B., Domain decomposition algorithms with small overlap, SIAM J. Sci. Statist. Comput., 15, 3, 604-620 (1994) · Zbl 0802.65119
[15] Kim, H. H.; Widlund, O. B., Two-level Schwarz algoriths, using overlapping subdomains, for mortar finite element methods, SIAM J. Numer. Anal., 44, 4, 1514-1534 (2006) · Zbl 1124.65035
[16] Dohrmann, C. R.; Klawonn, A.; Widlund, Olof B., Domain decomposition for less regular subdomains: overlapping Schwarz in two dimensions, SIAM J. Numer. Anal., 46, 4, 2153-2168 (2008) · Zbl 1183.65160
[17] Pavarino, L. F.; Zampieri, E., Overlapping Schwarz and spectral element methods for linear elasticity and elastic waves, J. Sci. Comput., 27, 1-3, 51-73 (2006) · Zbl 1115.74027
[18] M. Paraschivoiu, X.C. Cai, M. Sarkis, D.P. Young, D.E. Keyes, Multi-domain multi-model formulation for compressible flows: conservative interface coupling and parallel implicit solvers for 3D unstructured meshes, AIAA Paper 99-0784, American Institute of Aeronautics and Astronautics, Reston, VA, 1999.; M. Paraschivoiu, X.C. Cai, M. Sarkis, D.P. Young, D.E. Keyes, Multi-domain multi-model formulation for compressible flows: conservative interface coupling and parallel implicit solvers for 3D unstructured meshes, AIAA Paper 99-0784, American Institute of Aeronautics and Astronautics, Reston, VA, 1999.
[19] Li, J.; Melenk, M.; Wohlmuth, B.; Zou, J., Optimal convergence of higher order finite element methods for elliptic interface problems, Appl. Numer. Math., 60, 19-37 (2010) · Zbl 1208.65168
[20] Karniadakis, G. E.; Sherwin, S. J., Spectral/hp Element Methods for CFD (2005), Oxford University Press: Oxford University Press Oxford, 650 pp · Zbl 0857.76044
[21] L. Grinberg, Topics in ultrascale scientific computing with application in biomedical modeling, Ph.D. Thesis, Brown University, 2009.; L. Grinberg, Topics in ultrascale scientific computing with application in biomedical modeling, Ph.D. Thesis, Brown University, 2009.
[22] Sherwin, S. J.; Casarin, M., Low-energy basis preconditioning for elliptic substructured solvers based on unstructured spectral/hp element discretization, J. Comput. Phys., 171, 1, 394-417 (2001) · Zbl 0985.65143
[23] Grinberg, L.; Pekurovsky, D.; Sherwin, S. J.; Karniadakis, G. E., Parallel performance of a low energy basis preconditioner for spectral/hp elements, Parallel Comput. (2009)
[24] Karniadakis, G. E.; Israeli, M.; Orszag, S. A., High-order splitting methods for the incompressible Navier-Stokes equations, J. Comput. Phys., 97, 414-443 (1991) · Zbl 0738.76050
[25] Cockburn, B.; Karniadakis, G. E.; Shu, C. W., Discontinuous Galerkin Methods: Theory, Computation and Applications (2000), Springer: Springer Berlin
[26] Hughes, T. J.R.; Scovazzi, G.; Bochev, P. B.; Buffa, A., A multiscale discontinuous Galerkin method with the computational structure of a continuous Galerkin method, Comput. Methods Appl. Mech. Eng., 195, 2761-2787 (2006) · Zbl 1124.76027
[27] M. Gander, C. Japhet, Y. Maday, F. Nataf, A new cement to glue nonconforming grids with robin interface conditions: the finite element case, in: Domain Decomposition Methods in Science and Engineering Series: Lecture Notes in Computational Science and Engineering 40 (4) (2006) 259-266.; M. Gander, C. Japhet, Y. Maday, F. Nataf, A new cement to glue nonconforming grids with robin interface conditions: the finite element case, in: Domain Decomposition Methods in Science and Engineering Series: Lecture Notes in Computational Science and Engineering 40 (4) (2006) 259-266. · Zbl 1067.65144
[28] Zhang, M.; Shu, C. W., An analysis of three different formulations of the discontinuous Galerkin method for diffusion equations, Math. Models Meth. Appl. Sci., 13, 3, 395-413 (2003) · Zbl 1050.65094
[29] Kirby, R. M.; Karniadakis, G. E., Selecting the numerical flux in discontinuous Galerkin methods for diffusion problems, J. Sci. Comput., 22-23, 3, 385-411 (2005) · Zbl 1104.76060
[30] National Institute for Computational Sciences (NICS). Available from: <http://www.nics.tennessee.edu>; National Institute for Computational Sciences (NICS). Available from: <http://www.nics.tennessee.edu>
[31] Available from: <http://www.alcf.anl.gov>; Available from: <http://www.alcf.anl.gov>
[32] Available from: <http://services.tacc.utexas.edu/index.php/ranger-user-guide>; Available from: <http://services.tacc.utexas.edu/index.php/ranger-user-guide>
[33] P. Volino, N. Magnenat-Thalmann, The SPHERIGON: A Simple Polygon Patch for Smoothing Quickly your Polygonal Meshes, Proceedings of the Computer Animation, 1998, pp. 72-78.; P. Volino, N. Magnenat-Thalmann, The SPHERIGON: A Simple Polygon Patch for Smoothing Quickly your Polygonal Meshes, Proceedings of the Computer Animation, 1998, pp. 72-78.
[34] Womersley, J. R., Oscillatory motion of a viscous liquid in a thin-walled elastic tube. I. The linear approximation for long waves, Philos. Mag., 46, 199-221 (1955) · Zbl 0064.43903
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.