zbMATH — the first resource for mathematics

A scalable geometric multigrid solver for nonsymmetric elliptic systems with application to variable-density flows. (English) Zbl 1382.65301
Summary: A geometric multigrid algorithm is introduced for solving nonsymmetric linear systems resulting from the discretization of the variable density Navier-Stokes equations on nonuniform structured rectilinear grids and high-Reynolds number flows. The restriction operation is defined such that the resulting system on the coarser grids is symmetric, thereby allowing for the use of efficient smoother algorithms. To achieve an optimal rate of convergence, the sequence of interpolation and restriction operations are determined through a dynamic procedure. A parallel partitioning strategy is introduced to minimize communication while maintaining the load balance between all processors. To test the proposed algorithm, we consider two cases: 1) homogeneous isotropic turbulence discretized on uniform grids and 2) turbulent duct flow discretized on stretched grids. Testing the algorithm on systems with up to a billion unknowns shows that the cost varies linearly with the number of unknowns. This \(\mathcal{O}(N)\) behavior confirms the robustness of the proposed multigrid method regarding ill-conditioning of large systems characteristic of multiscale high-Reynolds number turbulent flows. The robustness of our method to density variations is established by considering cases where density varies sharply in space by a factor of up to \(10^{4}\), showing its applicability to two-phase flow problems. Strong and weak scalability studies are carried out, employing up to \(30,000\) processors, to examine the parallel performance of our implementation. Excellent scalability of our solver is shown for a granularity as low as \(10^{4}\) to \(10^{5}\) unknowns per processor. At its tested peak throughput, it solves approximately 4 billion unknowns per second employing over \(16,000\) processors with a parallel efficiency higher than 50%.

65M55 Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
76D05 Navier-Stokes equations for incompressible viscous fluids
Full Text: DOI
[1] Saad, Y., Iterative methods for sparse linear systems, (2003), SIAM · Zbl 1002.65042
[2] Saad, Y.; Sosonkina, M.; Zhang, J., Domain decomposition and multi-level type techniques for general sparse linear systems, Contemp. Math., 218, 174-190, (1998) · Zbl 0909.65020
[3] Esmaily, M.; Bazilevs, Y.; Marsden, A., A bi-partitioned iterative algorithm for solving linear systems arising from incompressible flow problems, Comput. Methods Appl. Mech. Eng., 286, 40-62, (2015)
[4] Shakib, F.; Hughes, T.; Johan, Z., A multi-element group preconditioned GMRES algorithm for nonsymmetric systems arising in finite element analysis, Comput. Methods Appl. Mech. Eng., 75, 415-456, (1989) · Zbl 0687.76065
[5] Fischer, P., Projection techniques for iterative solution of ax=b with successive right-hand sides, Comput. Methods Appl. Mech. Eng., 163, 193-204, (1998) · Zbl 0960.76063
[6] Carey, G.; Jiang, B.-N., Nonlinear preconditioned conjugate gradient and least-squares finite elements, Comput. Methods Appl. Mech. Eng., 62, 145-154, (1987) · Zbl 0633.65112
[7] Esmaily, M.; Bazilevs, Y.; Marsden, A. L., A new preconditioning technique for implicitly coupled multidomain simulations with applications to hemodynamics, Comput. Mech., 52, 1141-1152, (2013) · Zbl 1388.76130
[8] Bakhvalov, N. S., On the convergence of a relaxation method with natural constraints on the elliptic operator, USSR Comput. Math. Math. Phys., 6, 101-135, (1966)
[9] Hackbusch, W., Multi-grid methods and applications, vol. 4, (2013), Springer Science & Business Media
[10] Brandt, A., Multi-level adaptive solutions to boundary-value problems, Math. Comput., 31, 333-390, (1977) · Zbl 0373.65054
[11] Wesseling, P., Introduction to multigrid methods, (1995), Technical Report ICASE-95-11, DTIC Document · Zbl 0872.76068
[12] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 179-196, (1996) · Zbl 0851.65087
[13] Ghia, U.; Ghia, K. N.; Shin, C., High-re solutions for incompressible flow using the Navier-Stokes equations and a multigrid method, J. Comput. Phys., 48, 387-411, (1982) · Zbl 0511.76031
[14] Brandt, A., Algebraic multigrid theory: the symmetric case, Appl. Math. Comput., 19, 23-56, (1986) · Zbl 0616.65037
[15] Antonietti, P. F.; Sarti, M.; Verani, M., Multigrid algorithms for hp-discontinuous Galerkin discretizations of elliptic problems, SIAM J. Numer. Anal., 53, 598-618, (2015) · Zbl 1312.65181
[16] Jofre, L.; Lehmkuhl, O.; Ventosa, J.; Trias, F. X.; Oliva, A., Conservation properties of unstructured finite-volume mesh schemes for the Navier-Stokes equations, Numer. Heat Transf., Part B, Fundam., 65, 53-79, (2014)
[17] Chan, T. F.; Wan, W., Robust multigrid methods for nonsmooth coefficient elliptic linear systems, J. Comput. Appl. Math., 123, 323-352, (2000) · Zbl 0966.65099
[18] De Zeeuw, P. M., Matrix-dependent prolongations and restrictions in a blackbox multigrid solver, J. Comput. Appl. Math., 33, 1-27, (1990) · Zbl 0717.65099
[19] Chan, T. F.; Xu, J.; Zikatanov, L., An agglomeration multigrid method for unstructured grids, Contemp. Math., 218, 67-81, (1998) · Zbl 0909.65102
[20] Lallemand, M.-H.; Steve, H.; Dervieux, A., Unstructured multigridding by volume agglomeration: current status, Comput. Fluids, 21, 397-433, (1992) · Zbl 0753.76136
[21] Chan, T. F.; Go, S.; Zou, J., Multilevel domain decomposition and multigrid methods for unstructured meshes: algorithms and theory, (May 1995), Department of Mathematics, UCLA, Technical Report CAM 95-24
[22] Wan, W. L.; Chan, T. F.; Smith, B., An energy-minimizing interpolation for robust multigrid methods, SIAM J. Sci. Comput., 21, 1632-1649, (1999) · Zbl 0966.65098
[23] Reusken, A., A multigrid method based on incomplete Gaussian elimination, Numer. Linear Algebra Appl., 3, 369-390, (1996) · Zbl 0906.65118
[24] Richter, C.; Schoeps, S.; Clemens, M., GPU acceleration of algebraic multigrid preconditioners for discrete elliptic field problems, IEEE Trans. Magn., 50, 461-464, (2014)
[25] Smith, B.; Bjorstad, P.; Gropp, W., Domain decomposition: parallel multilevel methods for elliptic partial differential equations, (2004), Cambridge University Press
[26] Yang, U. M., Boomeramg: a parallel algebraic multigrid solver and preconditioner, Appl. Numer. Math., 41, 155-177, (2002) · Zbl 0995.65128
[27] Esmaily, M.; Bazilevs, Y.; Marsden, A., Impact of data distribution on the parallel performance of iterative linear solvers with emphasis on CFD of incompressible flows, Comput. Mech., 55, 93-103, (2015) · Zbl 1311.76057
[28] Polizzi, E.; Sameh, A. H., A parallel hybrid banded system solver: the SPIKE algorithm, Parallel Comput., 32, 177-194, (2006)
[29] Kuck, D. J.; Davidson, E. S.; Lawrie, D. H.; Sameh, A. H., Parallel supercomputing today and the cedar approach, Science, 231, 967-974, (1986)
[30] Esmaily, M.; Mani, A., Analysis of the clustering of inertial particles in turbulent flows, Phys. Rev. Fluids, 1, (2016)
[31] Pouransari, H.; Mani, A., Effects of preferential concentration on heat transfer in particle-based solar receivers, J. Sol. Energy Eng., 139, (2017)
[32] Farbar, E.; Boyd, I. D.; Esmaily, M., Monte Carlo modeling of radiative heat transfer in particle-laden flow, J. Quant. Spectrosc. Radiat. Transf., 184, 146-160, (2016)
[33] Heroux, M. A.; Bartlett, R. A.; Howle, V. E.; Hoekstra, R. J.; Hu, J. J.; Kolda, T. G.; Lehoucq, R. B.; Long, K. R.; Pawlowski, R. P.; Phipps, E. T.; Salinger, A. G.; Thornquist, H. K.; Tuminaro, R. S.; Willenbring, J. M.; Williams, A.; Stanley, K. S., An overview of the trilinos project, ACM Trans. Math. Softw., 31, 397-423, (2005) · Zbl 1136.65354
[34] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-436, (1952) · Zbl 0048.09901
[35] Pouransari, H.; Mortazavi, M.; Mani, A., Parallel variable-density particle-laden turbulence simulation, (2016), arXiv preprint
[36] Yang, X.; Mittal, R., Efficient relaxed-Jacobi smoothers for multigrid on parallel computers, J. Comput. Phys., 332, 135-142, (2017) · Zbl 1380.65243
[37] Prokopenko, A.; Hu, J. J.; Wiesner, T. A.; Siefert, C. M.; Tuminaro, R. S., Muelu User’s guide 1.0, (2014), Sandia National Labs, Technical Report SAND2014-18874
[38] Bavier, E.; Hoemmen, M.; Rajamanickam, S.; Thornquist, H., Amesos2 and belos: direct and iterative solvers for large sparse linear systems, (2012), Technical Report 3
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.