Fast auxiliary space preconditioners for linear elasticity in mixed form

Chen, Long; Hu, Jun; Huang, Xuehai

doi:10.1090/mcom/3285

Fast auxiliary space preconditioners for linear elasticity in mixed form
HTML articles powered by AMS MathViewer

by Long Chen, Jun Hu and Xuehai Huang PDF

Math. Comp. 87 (2018), 1601-1633 Request permission

Abstract:

A block-diagonal preconditioner with the minimal residual method and an approximate block-factorization preconditioner with the generalized minimal residual method are developed for Hu-Zhang mixed finite element methods for linear elasticity. They are based on a new stability result for the saddle point system in mesh-dependent norms. The mesh-dependent norm for the stress corresponds to the mass matrix which is easy to invert while for the displacement it is spectral equivalent to the Schur complement. A fast auxiliary space preconditioner based on the $H^1$-conforming linear element of the linear elasticity problem is then designed for solving the Schur complement. For both diagonal and triangular preconditioners, it is proved that the conditioning numbers of the preconditioned systems are bounded above by a constant independent of both the crucial Lamé constant and the mesh size. Numerical examples are presented to support theoretical results. As byproducts, a new stabilized low order mixed finite element method is proposed and analyzed and superconvergence results for the Hu-Zhang element are obtained.

References

Scot Adams and Bernardo Cockburn, A mixed finite element method for elasticity in three dimensions, J. Sci. Comput. 25 (2005), no. 3, 515–521. MR 2221175, DOI 10.1007/s10915-004-4807-3
Paola F. Antonietti and Blanca Ayuso, Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case, M2AN Math. Model. Numer. Anal. 41 (2007), no. 1, 21–54. MR 2323689, DOI 10.1051/m2an:2007006
Paola F. Antonietti and Blanca Ayuso, Multiplicative Schwarz methods for discontinuous Galerkin approximations of elliptic problems, M2AN Math. Model. Numer. Anal. 42 (2008), no. 3, 443–469. MR 2423794, DOI 10.1051/m2an:2008012
Douglas N. Arnold, An interior penalty finite element method with discontinuous elements, SIAM J. Numer. Anal. 19 (1982), no. 4, 742–760. MR 664882, DOI 10.1137/0719052
Douglas N. Arnold and Gerard Awanou, Rectangular mixed finite elements for elasticity, Math. Models Methods Appl. Sci. 15 (2005), no. 9, 1417–1429. MR 2166210, DOI 10.1142/S0218202505000741
Douglas N. Arnold, Gerard Awanou, and Ragnar Winther, Finite elements for symmetric tensors in three dimensions, Math. Comp. 77 (2008), no. 263, 1229–1251. MR 2398766, DOI 10.1090/S0025-5718-08-02071-1
Douglas N. Arnold, Franco Brezzi, and L. Donatella Marini, A family of discontinuous Galerkin finite elements for the Reissner-Mindlin plate, J. Sci. Comput. 22/23 (2005), 25–45. MR 2142189, DOI 10.1007/s10915-004-4134-8
Douglas N. Arnold and Ragnar Winther, Mixed finite elements for elasticity, Numer. Math. 92 (2002), no. 3, 401–419. MR 1930384, DOI 10.1007/s002110100348
Owe Axelsson and Maya Neytcheva, Preconditioning methods for linear systems arising in constrained optimization problems, Numer. Linear Algebra Appl. 10 (2003), no. 1-2, 3–31. Dedicated to the 60th birthday of Raytcho Lazarov. MR 1964284, DOI 10.1002/nla.310
Owe Axelsson and Alexander Padiy, On a robust and scalable linear elasticity solver based on a saddle point formulation, Internat. J. Numer. Methods Engrg. 44 (1999), no. 6, 801–818. MR 1672010, DOI 10.1002/(SICI)1097-0207(19990228)44:6<801::AID-NME525>3.0.CO;2-Y
Blanca Ayuso de Dios, Michael Holst, Yunrong Zhu, and Ludmil Zikatanov, Multilevel preconditioners for discontinuous, Galerkin approximations of elliptic problems, with jump coefficients, Math. Comp. 83 (2014), no. 287, 1083–1120. MR 3167451, DOI 10.1090/S0025-5718-2013-02760-3
Blanca Ayuso de Dios and Ludmil Zikatanov, Uniformly convergent iterative methods for discontinuous Galerkin discretizations, J. Sci. Comput. 40 (2009), no. 1-3, 4–36. MR 2511726, DOI 10.1007/s10915-009-9293-1
Randolph E. Bank, Bruno D. Welfert, and Harry Yserentant, A class of iterative methods for solving saddle point problems, Numer. Math. 56 (1990), no. 7, 645–666. MR 1031439, DOI 10.1007/BF01405194
A. T. Barker, S. C. Brenner, and L.-Y. Sung, Overlapping Schwarz domain decomposition preconditioners for the local discontinuous Galerkin method for elliptic problems, J. Numer. Math. 19 (2011), no. 3, 165–187. MR 2854135, DOI 10.1515/JNUM.2011.008
Michele Benzi, Gene H. Golub, and Jörg Liesen, Numerical solution of saddle point problems, Acta Numer. 14 (2005), 1–137. MR 2168342, DOI 10.1017/S0962492904000212
Daniele Boffi, Franco Brezzi, and Michel Fortin, Mixed finite element methods and applications, Springer Series in Computational Mathematics, vol. 44, Springer, Heidelberg, 2013. MR 3097958, DOI 10.1007/978-3-642-36519-5
D. Braess and R. Verfürth, A posteriori error estimators for the Raviart-Thomas element, SIAM J. Numer. Anal. 33 (1996), no. 6, 2431–2444. MR 1427472, DOI 10.1137/S0036142994264079
James H. Bramble and Joseph E. Pasciak, The analysis of smoothers for multigrid algorithms, Math. Comp. 58 (1992), no. 198, 467–488. MR 1122058, DOI 10.1090/S0025-5718-1992-1122058-0
Susanne C. Brenner, A nonconforming mixed multigrid method for the pure displacement problem in planar linear elasticity, SIAM J. Numer. Anal. 30 (1993), no. 1, 116–135. MR 1202659, DOI 10.1137/0730006
Susanne C. Brenner, A nonconforming mixed multigrid method for the pure traction problem in planar linear elasticity, Math. Comp. 63 (1994), no. 208, 435–460, S1–S5. MR 1257574, DOI 10.1090/S0025-5718-1994-1257574-6
Susanne C. Brenner, Two-level additive Schwarz preconditioners for nonconforming finite elements, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 9–14. MR 1312372, DOI 10.1090/conm/180/01951
Susanne C. Brenner, Korn’s inequalities for piecewise $H^1$ vector fields, Math. Comp. 73 (2004), no. 247, 1067–1087. MR 2047078, DOI 10.1090/S0025-5718-03-01579-5
S. C. Brenner, J. Cui, T. Gudi, and L.-Y. Sung, Multigrid algorithms for symmetric discontinuous Galerkin methods on graded meshes, Numer. Math. 119 (2011), no. 1, 21–47. MR 2824854, DOI 10.1007/s00211-011-0379-y
S. C. Brenner, J. Cui, and L.-Y. Sung, Multigrid methods for the symmetric interior penalty method on graded meshes, Numer. Linear Algebra Appl. 16 (2009), no. 6, 481–501. MR 2522959, DOI 10.1002/nla.630
Susanne C. Brenner, Hengguang Li, and Li-Yeng Sung, Multigrid methods for saddle point problems: Stokes and Lamé systems, Numer. Math. 128 (2014), no. 2, 193–216. MR 3259489, DOI 10.1007/s00211-014-0607-3
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
Susanne C. Brenner, Kening Wang, and Jie Zhao, Poincaré-Friedrichs inequalities for piecewise $H^2$ functions, Numer. Funct. Anal. Optim. 25 (2004), no. 5-6, 463–478. MR 2106270, DOI 10.1081/NFA-200042165
Susanne C. Brenner and Jie Zhao, Convergence of multigrid algorithms for interior penalty methods, Appl. Numer. Anal. Comput. Math. 2 (2005), no. 1, 3–18. MR 2157481, DOI 10.1002/anac.200410019
Kolja Brix, Martin Campos Pinto, and Wolfgang Dahmen, A multilevel preconditioner for the interior penalty discontinuous Galerkin method, SIAM J. Numer. Anal. 46 (2008), no. 5, 2742–2768. MR 2421055, DOI 10.1137/07069691X
Long Chen, Jun Hu, and Xuehai Huang, Stabilized mixed finite element methods for linear elasticity on simplicial grids in $\Bbb {R}^n$, Comput. Methods Appl. Math. 17 (2017), no. 1, 17–31. MR 3589339, DOI 10.1515/cmam-2016-0035
L. Chen, J. Hu, X. Huang, and H. Man, Residual-based a posteriori error estimates for symmetric conforming mixed finite elements for linear elasticity problems, arXiv:1705.04106, 2016. To appear in Sci. China Math.
Long Chen, Junping Wang, Yanqiu Wang, and Xiu Ye, An auxiliary space multigrid preconditioner for the weak Galerkin method, Comput. Math. Appl. 70 (2015), no. 4, 330–344. MR 3372035, DOI 10.1016/j.camwa.2015.04.016
L. Chen, Y. Wu, L. Zhong, and J. Zhou, Multigrid preconditioners for mixed finite element methods of vector Laplacian, arXiv:1601.04095, 2016.
Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 0520174
B. Cockburn, O. Dubois, J. Gopalakrishnan, and S. Tan, Multigrid for an HDG method, IMA J. Numer. Anal. 34 (2014), no. 4, 1386–1425. MR 3269430, DOI 10.1093/imanum/drt024
Veselin A. Dobrev, Raytcho D. Lazarov, Panayot S. Vassilevski, and Ludmil T. Zikatanov, Two-level preconditioning of discontinuous Galerkin approximations of second-order elliptic equations, Numer. Linear Algebra Appl. 13 (2006), no. 9, 753–770. MR 2269798, DOI 10.1002/nla.504
H. S. Dollar, Constraint-style preconditioners for regularized saddle point problems, SIAM J. Matrix Anal. Appl. 29 (2007), no. 2, 672–684. MR 2318371, DOI 10.1137/050626168
Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124. MR 1393904, DOI 10.1137/0733054
Jim Douglas Jr. and Jean E. Roberts, Global estimates for mixed methods for second order elliptic equations, Math. Comp. 44 (1985), no. 169, 39–52. MR 771029, DOI 10.1090/S0025-5718-1985-0771029-9
H. C. Elman. Iterative Methods for Large, Sparse, Nonsymmetric Systems of Linear Equations. PhD thesis, Yale University, New Haven, CT, 1982.
Xiaobing Feng and Ohannes A. Karakashian, Two-level additive Schwarz methods for a discontinuous Galerkin approximation of second order elliptic problems, SIAM J. Numer. Anal. 39 (2001), no. 4, 1343–1365. MR 1870847, DOI 10.1137/S0036142900378480
J. Gopalakrishnan and G. Kanschat, A multilevel discontinuous Galerkin method, Numer. Math. 95 (2003), no. 3, 527–550. MR 2012931, DOI 10.1007/s002110200392
Antti Hannukainen, Continuous preconditioners for the mixed Poisson problem, BIT 52 (2012), no. 1, 65–83. MR 2891654, DOI 10.1007/s10543-011-0346-0
Ralf Hiptmair and Jinchao Xu, Nodal auxiliary space preconditioning in $\textbf {H}(\textbf {curl})$ and $\textbf {H}(\textrm {div})$ spaces, SIAM J. Numer. Anal. 45 (2007), no. 6, 2483–2509. MR 2361899, DOI 10.1137/060660588
Qingguo Hong, Johannes Kraus, Jinchao Xu, and Ludmil Zikatanov, A robust multigrid method for discontinuous Galerkin discretizations of Stokes and linear elasticity equations, Numer. Math. 132 (2016), no. 1, 23–49 (English, with Romanian summary). MR 3439214, DOI 10.1007/s00211-015-0712-y
Jun Hu, Finite element approximations of symmetric tensors on simplicial grids in $\Bbb R^n$: the higher order case, J. Comput. Math. 33 (2015), no. 3, 283–296. MR 3352360, DOI 10.4208/jcm.1412-m2014-0071
J. Hu and G. Yu, A unified analysis of quasi-optimal convergence for adaptive mixed finite element methods, arXiv:1601.00132, 2016. To appear in SIAM J. Numer. Anal.
Jun Hu and ShangYou Zhang, A family of conforming mixed finite elements for linear elasticity on triangular grids, arXiv:1406.7457, 2015..
Jun Hu and ShangYou Zhang, A family of symmetric mixed finite elements for linear elasticity on tetrahedral grids, Sci. China Math. 58 (2015), no. 2, 297–307. MR 3301063, DOI 10.1007/s11425-014-4953-5
Jianguo Huang and Xuehai Huang, Local and parallel algorithms for fourth order problems discretized by the Morley-Wang-Xu element method, Numer. Math. 119 (2011), no. 4, 667–697. MR 2854124, DOI 10.1007/s00211-011-0396-x
Carsten Keller, Nicholas I. M. Gould, and Andrew J. Wathen, Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl. 21 (2000), no. 4, 1300–1317. MR 1780274, DOI 10.1137/S0895479899351805
Axel Klawonn and Gerhard Starke, A preconditioner for the equations of linear elasticity discretized by the PEERS element, Numer. Linear Algebra Appl. 11 (2004), no. 5-6, 493–510. MR 2067817, DOI 10.1002/nla.357
Tzanio V. Kolev and Panayot S. Vassilevski, Auxiliary space AMG for $H$(curl) problems, Domain decomposition methods in science and engineering XVII, Lect. Notes Comput. Sci. Eng., vol. 60, Springer, Berlin, 2008, pp. 147–154. MR 2436078, DOI 10.1007/978-3-540-75199-1_{1}3
Tzanio V. Kolev and Panayot S. Vassilevski, Parallel auxiliary space AMG for $H(\textrm {curl})$ problems, J. Comput. Math. 27 (2009), no. 5, 604–623. MR 2536904, DOI 10.4208/jcm.2009.27.5.013
Johannes Kraus, Raytcho Lazarov, Maria Lymbery, Svetozar Margenov, and Ludmil Zikatanov, Preconditioning heterogeneous $H(\textrm {div})$ problems by additive Schur complement approximation and applications, SIAM J. Sci. Comput. 38 (2016), no. 2, A875–A898. MR 3474851, DOI 10.1137/140974092
J. Kraus, M. Lymbery, and S. Margenov, Auxiliary space multigrid method based on additive Schur complement approximation, Numer. Linear Algebra Appl. 22 (2015), no. 6, 965–986. MR 3426324, DOI 10.1002/nla.1959
J. K. Kraus and S. K. Tomar, A multilevel method for discontinuous Galerkin approximation of three-dimensional anisotropic elliptic problems, Numer. Linear Algebra Appl. 15 (2008), no. 5, 417–438. MR 2423513, DOI 10.1002/nla.544
Johannes K. Kraus and Satyendra K. Tomar, Multilevel preconditioning of two-dimensional elliptic problems discretized by a class of discontinuous Galerkin methods, SIAM J. Sci. Comput. 30 (2008), no. 2, 684–706. MR 2385881, DOI 10.1137/060667372
Chang-Ock Lee, Multigrid methods for the pure traction problem of linear elasticity: mixed formulation, SIAM J. Numer. Anal. 35 (1998), no. 1, 121–145. MR 1618440, DOI 10.1137/S0036142995282832
Young-Ju Lee, Jinbiao Wu, and Jinru Chen, Robust multigrid method for the planar linear elasticity problems, Numer. Math. 113 (2009), no. 3, 473–496. MR 2534133, DOI 10.1007/s00211-009-0232-8
Binjie Li and Xiaoping Xie, A two-level algorithm for the weak Galerkin discretization of diffusion problems, J. Comput. Appl. Math. 287 (2015), 179–195. MR 3342024, DOI 10.1016/j.cam.2015.03.043
D. Loghin and A. J. Wathen, Analysis of preconditioners for saddle-point problems, SIAM J. Sci. Comput. 25 (2004), no. 6, 2029–2049. MR 2086829, DOI 10.1137/S1064827502418203
Carlo Lovadina and Rolf Stenberg, Energy norm a posteriori error estimates for mixed finite element methods, Math. Comp. 75 (2006), no. 256, 1659–1674. MR 2240629, DOI 10.1090/S0025-5718-06-01872-2
Kent-Andre Mardal and Ragnar Winther, Preconditioning discretizations of systems of partial differential equations, Numer. Linear Algebra Appl. 18 (2011), no. 1, 1–40. MR 2769031, DOI 10.1002/nla.716
William F. Mitchell, A comparison of adaptive refinement techniques for elliptic problems, ACM Trans. Math. Software 15 (1989), no. 4, 326–347 (1990). MR 1062496, DOI 10.1145/76909.76912
Joseph E. Pasciak and Yanqiu Wang, A multigrid preconditioner for the mixed formulation of linear plane elasticity, SIAM J. Numer. Anal. 44 (2006), no. 2, 478–493. MR 2218956, DOI 10.1137/040617820
I. Perugia and V. Simoncini, Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations, Numer. Linear Algebra Appl. 7 (2000), no. 7-8, 585–616. Preconditioning techniques for large sparse matrix problems in industrial applications (Minneapolis, MN, 1999). MR 1802361, DOI 10.1002/1099-1506(200010/12)7:7/8<585::AID-NLA214>3.3.CO;2-6
J. W. Ruge and K. Stüben, Algebraic multigrid, Multigrid methods, Frontiers Appl. Math., vol. 3, SIAM, Philadelphia, PA, 1987, pp. 73–130. MR 972756
Torgeir Rusten, Panayot S. Vassilevski, and Ragnar Winther, Interior penalty preconditioners for mixed finite element approximations of elliptic problems, Math. Comp. 65 (1996), no. 214, 447–466. MR 1333325, DOI 10.1090/S0025-5718-96-00720-X
Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
Joachim Schöberl, Multigrid methods for a parameter dependent problem in primal variables, Numer. Math. 84 (1999), no. 1, 97–119. MR 1724348, DOI 10.1007/s002110050465
Rolf Stenberg, On the construction of optimal mixed finite element methods for the linear elasticity problem, Numer. Math. 48 (1986), no. 4, 447–462. MR 834332, DOI 10.1007/BF01389651
Rolf Stenberg, Postprocessing schemes for some mixed finite elements, RAIRO Modél. Math. Anal. Numér. 25 (1991), no. 1, 151–167 (English, with French summary). MR 1086845, DOI 10.1051/m2an/1991250101511
Ray S. Tuminaro, Jinchao Xu, and Yunrong Zhu, Auxiliary space preconditioners for mixed finite element methods, Domain decomposition methods in science and engineering XVIII, Lect. Notes Comput. Sci. Eng., vol. 70, Springer, Berlin, 2009, pp. 99–109. MR 2743962, DOI 10.1007/978-3-642-02677-5_{9}
Ming Wang, On the necessity and sufficiency of the patch test for convergence of nonconforming finite elements, SIAM J. Numer. Anal. 39 (2001), no. 2, 363–384. MR 1860273, DOI 10.1137/S003614299936473X
Yanqiu Wang, Overlapping Schwarz preconditioner for the mixed formulation of plane elasticity, Appl. Numer. Math. 54 (2005), no. 2, 292–309. MR 2148047, DOI 10.1016/j.apnum.2004.09.032
C. Wieners, Robust multigrid methods for nearly incompressible elasticity, Computing 64 (2000), no. 4, 289–306. International GAMM-Workshop on Multigrid Methods (Bonn, 1998). MR 1782022, DOI 10.1007/s006070070026
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
J. Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing 56 (1996), no. 3, 215–235 (English, with English and German summaries). International GAMM-Workshop on Multi-level Methods (Meisdorf, 1994). MR 1393008, DOI 10.1007/BF02238513
Jinchao Xu, Fast Poisson-based solvers for linear and nonlinear PDEs, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2886–2912. MR 2827997
Shuo Zhang and Jinchao Xu, Optimal solvers for fourth-order PDEs discretized on unstructured grids, SIAM J. Numer. Anal. 52 (2014), no. 1, 282–307. MR 3162408, DOI 10.1137/120878148
Liuqiang Zhong, Eric T. Chung, and Chunmei Liu, Fast solvers for the symmetric IPDG discretization of second order elliptic problems, Int. J. Numer. Anal. Model. 12 (2015), no. 3, 455–475. MR 3352442
Y. Zhu and Y.-J. Lee, Auxiliary space preconditioner for linear elasticity equation with weakly imposed symmetry problems. In: Conference on the Mathematics of Finite Elements and Applications, 2016.
Y. Zhu, E. Sifakis, J. Teran, and A. Brandt, An efficient multigrid method for the simulation of high-resolution elastic solids, ACM Trans. Graph. (TOG), 29(2), MAR 2010.
Jun Hu, A new family of efficient conforming mixed finite elements on both rectangular and cuboid meshes for linear elasticity in the symmetric formulation, SIAM J. Numer. Anal. 53 (2015), no. 3, 1438–1463. MR 3357634, DOI 10.1137/130945272
Jun Hu and Shangyou Zhang, Finite element approximations of symmetric tensors on simplicial grids in $\Bbb {R}^n$: the lower order case, Math. Models Methods Appl. Sci. 26 (2016), no. 9, 1649–1669. MR 3529252, DOI 10.1142/S0218202516500408