An augmented Lagrangian preconditioner for the 3D stationary incompressible Navier-Stokes equations at High Reynolds number. (English) Zbl 1448.65261

The paper deals with the numerical solution of algebraic systems arising from the discretization of the 3D incompressible Navier-Stokes equations by finite element methods. In [M. Benzi and M. A. Olshanskii, SIAM J. Sci. Comput. 28, No. 6, 2095–2113 (2006; Zbl 1126.76028)], the efficientl technique of the preconditioner of augmented Lagrangian type was presented for the two-dimensional problems. The algorithm relies on a specialized multigrid method involving a custom prolongation operator and for robustness requires the use of piecewise constant finite elements for the pressure. However, this technique can not be directly extended to 3D problems due to the violation of the inf-sup condition for the used finite element pair. In this paper, the authors generalize the preconditioner to 3D by proposing alternative finite elements for the velocity and prolongation operators for which the preconditioner works robustly. The solver is effective at high Reynolds number: on a three-dimensional lid-driven cavity problem with approximately one billion degrees of freedom, the average number of Krylov iterations per Newton step varies from 4.5 at \(\operatorname{Re} = 10\) to 3 at \(\operatorname{Re} = 1000\) and 5 at \(\operatorname{Re} = 5000\).


65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65H10 Numerical computation of solutions to systems of equations
76D05 Navier-Stokes equations for incompressible viscous fluids


Zbl 1126.76028
Full Text: DOI arXiv


[1] M. S. Aln\aes, A. Logg, K. B. Ølgaard, M. E. Rognes, and G. N. Wells, Unified Form Language: A domain-specific language for weak formulations of partial differential equations, ACM Trans. Math. Softw., 40 (2014), 9, https://doi.org/10.1145/2566630. · Zbl 1308.65175
[2] D. N. Arnold, R. Falk, and R. Winther, Preconditioning in \textbfH (div) and applications, Math. Comp., 66 (1997), pp. 957–984, https://doi.org/10.1090/S0025-5718-97-00826-0. · Zbl 0870.65112
[3] D. N. Arnold, R. S. Falk, and R. Winther, Multigrid in H (div) and H (curl), Numer. Math., 85 (2000), pp. 197–217, https://doi.org/10.1007/pl00005386. · Zbl 0974.65113
[4] C. Bacuta, A unified approach for Uzawa algorithms, SIAM J. Numer. Anal., 44 (2006), pp. 2633–2649, https://doi.org/10.1137/050630714.
[5] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, S. Zampini, H. Zhang, and H. Zhang, PETSc Users Manual, Tech. Report ANL-95/11 - Revision 3.8, Argonne National Laboratory, Lemont, IL, 2017, http://www.mcs.anl.gov/petsc.
[6] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1–137, https://doi.org/10.1017/S0962492904000212. · Zbl 1115.65034
[7] M. Benzi and M. A. Olshanskii, An augmented Lagrangian-based approach to the Oseen problem, SIAM J. Sci. Comput., 28 (2006), pp. 2095–2113, https://doi.org/10.1137/050646421. · Zbl 1126.76028
[8] M. Benzi and M. A. Olshanskii, Field-of-values convergence analysis of augmented Lagrangian preconditioners for the linearized Navier–Stokes problem, SIAM J. Numer. Anal., 49 (2011), pp. 770–788, https://doi.org/10.1137/100806485. · Zbl 1245.76044
[9] M. Benzi, M. A. Olshanskii, and Z. Wang, Modified augmented Lagrangian preconditioners for the incompressible Navier-Stokes equations, Int. J. Numer. Methods Fluids, 66 (2011), pp. 486–508, https://doi.org/10.1002/fld.2267. · Zbl 1421.76152
[10] C. Bernardi and G. Raugel, Analysis of some finite elements for the Stokes problem, Math. Comp., 44 (1985), pp. 71–79, https://doi.org/10.2307/2007793. · Zbl 0563.65075
[11] C. Bernardi and G. Raugel, A conforming finite element method for the time-dependent Navier–Stokes equations, SIAM J. Numer. Anal., 22 (1985), pp. 455–473, https://doi.org/10.1137/0722027. · Zbl 0578.65122
[12] D. Boffi, F. Brezzi, and M. Fortin, Finite elements for the Stokes problem, in Mixed Finite Elements, Compatibility Conditions, and Applications, D. Boffi and L. Gastaldi, eds., Lecture Notes in Math. 1939, Springer, Berlin, Heidelberg, 2008, pp. 45–100. · Zbl 1182.76895
[13] D. Boffi and C. Lovadina, Analysis of new augmented Lagrangian formulations for mixed finite element schemes, Numer. Math., 75 (1997), pp. 405–419, https://doi.org/10.1007/s002110050246. · Zbl 0874.65085
[14] S. Börm and S. L. Borne, \(\mathcal{H}\)-LU factorization in preconditioners for augmented Lagrangian and grad-div stabilized saddle point systems, Int. J. Numer. Methods Fluids, 68 (2010), pp. 83–98, https://doi.org/10.1002/fld.2495.
[15] D. Braess and R. Sarazin, An efficient smoother for the Stokes problem, Appl. Numer. Math., 23 (1997), pp. 3–19, https://doi.org/10.1016/s0168-9274(96)00059-1. · Zbl 0874.65095
[16] A. Brandt and O. E. Livne, Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics, 2nd ed., Classics Appl. Math. 67, SIAM, Philadelphia, 2011, https://doi.org/10.1137/1.9781611970753.
[17] S. C. Brenner and L. R. Scott, The Mathematical Theory of Finite Element Methods, 3rd ed., Texts Appl. Math. 15, Springer-Verlag, New York, 2008.
[18] F. Brezzi and M. Fortin, Mixed and Hybrid Finite Element Methods, Springer Ser. Comput. Math. 15, Springer-Verlag, New York, 1991, https://doi.org/10.1007/978-1-4612-3172-1.
[19] A. N. Brooks and T. J. R. Hughes, Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations, Comput. Methods Appl. Mech. Engrg., 32 (1982), pp. 199–259, https://doi.org/10.1016/0045-7825(82)90071-8.
[20] J. Brown, M. Knepley, D. May, L. McInnes, and B. Smith, Composable linear solvers for multiphysics, in Proceedings of the 11th International Symposium on Parallel and Distributed Computing (ISPDC), 2012, pp. 55–62, https://doi.org/10.1109/ISPDC.2012.16.
[21] P. R. Brune, M. G. Knepley, B. F. Smith, and X. Tu, Composing scalable nonlinear algebraic solvers, SIAM Rev., 57 (2015), pp. 535–565, https://doi.org/10.1137/130936725. · Zbl 1336.65030
[22] A. J. Chorin, A numerical method for solving incompressible viscous flow problems, J. Comput. Phys., 2 (1967), pp. 12–26, https://doi.org/10.1016/0021-9991(67)90037-x.
[23] B. Cockburn, G. Kanschat, and D. Schötzau, A note on discontinuous Galerkin divergence-free solutions of the Navier–Stokes equations, J. Sci. Comput., 31 (2006), pp. 61–73, https://doi.org/10.1007/s10915-006-9107-7.
[24] A. C. de Niet and F. W. Wubs, Two preconditioners for saddle point problems in fluid flows, Int. J. Numer. Methods Fluids, 54 (2007), pp. 355–377, https://doi.org/10.1002/fld.1401. · Zbl 1111.76033
[25] M. Eiermann and O. G. Ernst, Geometric aspects of the theory of Krylov subspace methods, Acta Numer., 10 (2001), pp. 251–312, https://doi.org/10.1017/S0962492901000046. · Zbl 1105.65328
[26] H. Elman, V. E. Howle, J. Shadid, R. Shuttleworth, and R. Tuminaro, Block preconditioners based on approximate commutators, SIAM J. Sci. Comput., 27 (2006), pp. 1651–1668, https://doi.org/10.1137/040608817. · Zbl 1100.65042
[27] H. Elman and D. Silvester, Fast nonsymmetric iterations and preconditioning for Navier–Stokes equations, SIAM J. Sci. Comput., 17 (1996), pp. 33–46, https://doi.org/10.1137/0917004. · Zbl 0843.65080
[28] H. C. Elman, D. Loghin, and A. J. Wathen, Preconditioning techniques for Newton’s method for the incompressible Navier–Stokes equations, BIT, 43 (2003), pp. 961–974, https://doi.org/10.1023/b:bitn.0000014565.86918.df. · Zbl 1244.76023
[29] H. C. Elman, A. Ramage, and D. J. Silvester, IFISS: A computational laboratory for investigating incompressible flow problems, SIAM Rev., 56 (2014), pp. 261–273, https://doi.org/10.1137/120891393. · Zbl 1426.76645
[30] H. C. Elman, D. J. Silvester, and A. J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2nd ed., Oxford University Press, Oxford, 2014. · Zbl 1304.76002
[31] M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Stud. Math. Appl. 15, North-Holland, Amsterdam, 1983. · Zbl 0525.65045
[32] M. Gee, C. Siefert, J. Hu, R. Tuminaro, and M. Sala, ML \(5.0\) Smoothed Aggregation User’s Guide, Tech. Report SAND2006-2649, Sandia National Laboratories, Albuquerque, NM, 2006.
[33] C. Geuzaine and J.-F. Remacle, Gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing facilities, Internat. J. Numer. Methods Engrg., 79 (2009), pp. 1309–1331, https://doi.org/10.1002/nme.2579. · Zbl 1176.74181
[34] V. Girault and P.-A. Raviart, Finite Element Methods for Navier-Stokes Equations: Theory and Algorithms, Springer Ser. Comput. Math. 5, Springer, Berlin, 1986.
[35] A. Greenbaum, V. Pták, and Z. Strakoš, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 465–469, https://doi.org/10.1137/S0895479894275030.
[36] J. Guzmán and M. Neilan, Inf-Sup Stable Finite Elements on Barycentric Refinements Producing Divergence–Free Approximations in Arbitrary Dimensions, 2017, https://arxiv.org/abs/1710.08044.
[37] S. Hamilton, M. Benzi, and E. Haber, New multigrid smoothers for the Oseen problem, Numer. Linear Algebra Appl., 17 (2010), pp. 557–576, https://doi.org/10.1002/nla.707. · Zbl 1240.76003
[38] X. He, M. Neytcheva, and S. S. Capizzano, On an augmented Lagrangian-based preconditioning of Oseen type problems, BIT, 51 (2011), pp. 865–888, https://doi.org/10.1007/s10543-011-0334-4. · Zbl 1269.65030
[39] X. He, C. Vuik, and C. M. Klaij, Combining the augmented Lagrangian preconditioner with the simple Schur complement approximation, SIAM J. Sci. Comput., 40 (2018), pp. A1362–A1385, https://doi.org/10.1137/17M1144775. · Zbl 1392.65053
[40] T. Heister and G. Rapin, Efficient augmented Lagrangian-type preconditioning for the Oseen problem using grad-div stabilization, Int. J. Numer. Methods Fluids, 71 (2012), pp. 118–134, https://doi.org/10.1002/fld.3654.
[41] R. Hiptmair, Multigrid method for \({H}({div})\) in three dimensions, Electron. Trans. Numer. Anal., 6 (1997), pp. 133–152. · Zbl 0897.65046
[42] M. Homolya, L. Mitchell, F. Luporini, and D. A. Ham, TSFC: A structure-preserving form compiler, SIAM J. Sci. Comput., 40 (2018), pp. C401–C428, https://doi.org/10.1137/17M1130642. · Zbl 1388.68020
[43] I. C. F. Ipsen, A note on preconditioning nonsymmetric matrices, SIAM J. Sci. Comput., 23 (2001), pp. 1050–1051, https://doi.org/10.1137/S1064827500377435. · Zbl 0998.65049
[44] V. John, A. Linke, C. Merdon, M. Neilan, and L. G. Rebholz, On the divergence constraint in mixed finite element methods for incompressible flows, SIAM Rev., 59 (2017), pp. 492–544, https://doi.org/10.1137/15m1047696. · Zbl 1426.76275
[45] V. John and G. Matthies, Higher-order finite element discretizations in a benchmark problem for incompressible flows, Int. J. Numer. Methods Fluids, 37 (2001), pp. 885–903, https://doi.org/10.1002/fld.195. · Zbl 1007.76040
[46] D. Kay, D. Loghin, and A. Wathen, A preconditioner for the steady-state Navier–Stokes equations, SIAM J. Sci. Comput., 24 (2002), pp. 237–256, https://doi.org/10.1137/S106482759935808X. · Zbl 1013.65039
[47] R. C. Kirby, Algorithm 839: FIAT, a new paradigm for computing finite element basis functions, ACM Trans. Math. Softw., 30 (2004), pp. 502–516, https://doi.org/10.1145/1039813.1039820. · Zbl 1070.65571
[48] R. C. Kirby and L. Mitchell, Solver composition across the PDE/linear algebra barrier, SIAM J. Sci. Comput., 40 (2018), pp. C76–C98, https://doi.org/10.1137/17M1133208.
[49] M. G. Knepley and D. A. Karpeev, Flexible Representation of Computational Meshes, Tech. Report ANL/MCS-P1295-1005, Argonne National Laboratory, Lemont, IL, 2005.
[50] M. G. Knepley and D. A. Karpeev, Mesh algorithms for PDE with Sieve I: Mesh distribution, Sci. Program., 17 (2009), pp. 215–230, https://doi.org/10.1155/2009/948613.
[51] G. M. Kobel’kov, On solving the Navier-Stokes equations at large Reynolds numbers, Russian J. Numer. Anal. Math. Modelling, 10 (1995), pp. 33–40, https://doi.org/10.1515/rnam.1995.10.1.33.
[52] Y.-J. Lee, J. Wu, J. Xu, and L. Zikatanov, Robust subspace correction methods for nearly singular systems, Math. Models Methods Appl. Sci., 17 (2007), pp. 1937–1963, https://doi.org/10.1142/s0218202507002522. · Zbl 1151.65096
[53] X. S. Li and J. W. Demmel, SuperLU_DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Trans. Math. Softw., 29 (2003), pp. 110–140. · Zbl 1068.90591
[54] X. S. Li, J. W. Demmel, J. R. Gilbert, L. Grigori, M. Shao, and I. Yamazaki, SuperLU Users’ Guide, Tech. Report LBNL-44289, Lawrence Berkeley National Laboratory, Berkeley, CA, 1999.
[55] D. Loghin and A. J. Wathen, Analysis of preconditioners for saddle-point problems, SIAM J. Sci. Comput., 25 (2004), pp. 2029–2049, https://doi.org/10.1137/S1064827502418203. · Zbl 1067.65048
[56] K.-A. Mardal and R. Winther, Preconditioning discretizations of systems of partial differential equations, Numer. Linear Algebra Appl., 18 (2011), pp. 1–40, https://doi.org/10.1002/nla.716.
[57] D. A. May, P. Sanan, K. Rupp, M. G. Knepley, and B. F. Smith, Extreme-scale multigrid components within PETSc, in Proceedings of the Platform for Advanced Scientific Computing Conference, 2016, 5, https://doi.org/10.1145/2929908.2929913.
[58] M. F. Murphy, G. H. Golub, and A. J. Wathen, A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21 (2000), pp. 1969–1972, https://doi.org/10.1137/S1064827599355153. · Zbl 0959.65063
[59] M. A. Olshanskii and M. Benzi, An augmented Lagrangian approach to linearized problems in hydrodynamic stability, SIAM J. Sci. Comput., 30 (2008), pp. 1459–1473, https://doi.org/10.1137/070691851. · Zbl 1162.76031
[60] M. A. Olshanskii and A. Reusken, Grad-div stabilization for Stokes equations, Math. Comp., 73 (2004), pp. 1699–1718, https://doi.org/10.1090/s0025-5718-03-01629-6. · Zbl 1051.65103
[61] M. A. Olshanskii and A. Reusken, Convergence analysis of a multigrid method for a convection-dominated model problem, SIAM J. Numer. Anal., 42 (2004), pp. 1261–1291, https://doi.org/10.1137/s0036142902418679. · Zbl 1080.65105
[62] M. A. Olshanskii and E. E. Tyrtyshnikov, Iterative Methods for Linear Systems: Theory and Applications, SIAM, Philadelphia, 2014, https://doi.org/10.1137/1.9781611973464. · Zbl 1320.65050
[63] S. Patankar, Numerical Heat Transfer and Fluid Flow, 1st ed., Hemisphere Series on Computational Methods in Mechanics and Thermal Science, Taylor & Francis, London, 1980.
[64] A. Quarteroni and A. Valli, Numerical Approximation of Partial Differential Equations, Springer Ser. Comput. Math. 23, Springer-Verlag, Berlin, 1994. · Zbl 0803.65088
[65] A. Ramage, A multigrid preconditioner for stabilised discretisations of advection\textendashdiffusion problems, J. Comput. Appl. Math., 110 (1999), pp. 187–203, https://doi.org/10.1016/s0377-0427(99)00234-4. · Zbl 0939.65135
[66] F. Rathgeber, D. A. Ham, L. Mitchell, M. Lange, F. Luporini, A. T. T. Mcrae, G.-T. Bercea, G. R. Markall, and P. H. J. Kelly, Firedrake: Automating the finite element method by composing abstractions, ACM Trans. Math. Softw., 43 (2017), 24, https://doi.org/10.1145/2998441. · Zbl 1396.65144
[67] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993), pp. 461–469, https://doi.org/10.1137/0914028. · Zbl 0780.65022
[68] J. Schöberl, Multigrid methods for a parameter dependent problem in primal variables, Numer. Math., 84 (1999), pp. 97–119, https://doi.org/10.1007/s002110050465. · Zbl 0957.74059
[69] J. Schöberl, Robust Multigrid Methods for Parameter Dependent Problems, Ph.D. thesis, Johannes Kepler Universität Linz, Linz, Austria, 1999.
[70] L. R. Scott and M. Vogelius, Norm estimates for a maximal right inverse of the divergence operator in spaces of piecewise polynomials, RAIRO Modél. Math. Anal. Numér., 19 (1985), pp. 111–143. · Zbl 0608.65013
[71] L. R. Scott and S. Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp., 54 (1990), pp. 483–493, http://www.jstor.org/stable/2008497. · Zbl 0696.65007
[72] F. Shakib, T. J. R. Hughes, and Z. Johan, A new finite element formulation for computational fluid dynamics: X. The compressible Euler and Navier-Stokes equations, Comput. Methods Appl. Mech. Engrg., 89 (1991), pp. 141–219, https://doi.org/10.1016/0045-7825(91)90041-4.
[73] T. Shih, C. Tan, and B. Hwang, Effects of grid staggering on numerical schemes, Int. J. Numer. Methods Fluids, 9 (1989), pp. 193–212. · Zbl 0661.76024
[74] D. Silvester and A. Wathen, Fast iterative solution of stabilised Stokes systems Part II: Using general block preconditioners, SIAM J. Numer. Anal., 31 (1994), pp. 1352–1367, https://doi.org/10.1137/0731070. · Zbl 0810.76044
[75] G. Starke, Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems, Numer. Math., 78 (1997), pp. 103–117, https://doi.org/10.1007/s002110050306. · Zbl 0888.65037
[76] R. Temam, Une méthode d’approximation de la solution des équations de Navier-Stokes, Bull. Soc. Math. France, 98 (1968), pp. 115–152. · Zbl 0181.18903
[77] S. Turek, Efficient Solvers for Incompressible Flow Problems: An Algorithmic and Computational Approach, Lect. Notes Comput. Sci. Eng. 6, Springer-Verlag, Berlin, Heidelberg, 1999. · Zbl 0930.76002
[78] M. ur Rehman, C. Vuik, and G. Segal, A comparison of preconditioners for incompressible Navier-Stokes solvers, Int. J. Numer. Methods Fluids, 57 (2008), pp. 1731–1751, https://doi.org/10.1002/fld.1684. · Zbl 1262.76083
[79] S. P. Vanka, Block-implicit multigrid solution of Navier-Stokes equations in primitive variables, J. Comput. Phys., 65 (1986), pp. 138–158, https://doi.org/10.1016/0021-9991(86)90008-2.
[80] A. J. Wathen, Preconditioning, Acta Numer., 24 (2015), pp. 329–376, https://doi.org/10.1017/S0962492915000021.
[81] C.-T. Wu and H. C. Elman, Analysis and comparison of geometric and algebraic multigrid for convection-diffusion equations, SIAM J. Sci. Comput., 28 (2006), pp. 2208–2228, https://doi.org/10.1137/060662940. · Zbl 1133.65102
[82] Software used in “An augmented Lagrangian preconditioner for the \(3\) D stationary incompressible Navier–Stokes equations at high Reynolds number,” 2019, https://doi.org/10.5281/zenodo.3247427.
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.