Conditioning of the finite volume element method for diffusion problems with general simplicial meshes

Wang, Xiang; Huang, Weizhang; Li, Yonghai

doi:10.1090/mcom/3423

Conditioning of the finite volume element method for diffusion problems with general simplicial meshes
HTML articles powered by AMS MathViewer

by Xiang Wang, Weizhang Huang and Yonghai Li HTML | PDF

Math. Comp. 88 (2019), 2665-2696 Request permission

Abstract:

The conditioning of the linear finite volume element discretization for general diffusion equations is studied on arbitrary simplicial meshes. The condition number is defined as the ratio of the maximal singular value of the stiffness matrix to the minimal eigenvalue of its symmetric part. This definition is motivated by the fact that the convergence rate of the generalized minimal residual method for the corresponding linear systems is determined by the ratio. An upper bound for the ratio is established by developing an upper bound for the maximal singular value and a lower bound for the minimal eigenvalue of the symmetric part. It is shown that the bound depends on three factors: the number of the elements in the mesh, the mesh nonuniformity measured in the Euclidean metric, and the mesh nonuniformity measured in the metric specified by the inverse diffusion matrix. It is also shown that the diagonal scaling can effectively eliminate the effects from the mesh nonuniformity measured in the Euclidean metric. Numerical results for a selection of examples in one, two, and three dimensions are presented.

References

Mark Ainsworth, William McLean, and Thanh Tran, The conditioning of boundary element equations on locally refined meshes and preconditioning by diagonal scaling, SIAM J. Numer. Anal. 36 (1999), no. 6, 1901–1932. MR 1712149, DOI 10.1137/S0036142997330809
Mark Ainsworth, Bill McLean, and Thanh Tran, Diagonal scaling of stiffness matrices in the Galerkin boundary element method, ANZIAM J. 42 (2000), no. 1, 141–150. Papers in honour of David Elliott on the occasion of his sixty-fifth birthday. MR 1783377, DOI 10.1017/S1446181100011676
Randolph E. Bank and Donald J. Rose, Some error estimates for the box method, SIAM J. Numer. Anal. 24 (1987), no. 4, 777–787. MR 899703, DOI 10.1137/0724050
Randolph E. Bank and L. Ridgway Scott, On the conditioning of finite element equations with highly refined meshes, SIAM J. Numer. Anal. 26 (1989), no. 6, 1383–1394. MR 1025094, DOI 10.1137/0726080
T. Barth and M. Ohlberger, Finite Volume Methods: Foundation and Analysis, Vol. 1, Chap. 15, John Wiley & Sons, 2004, 1–57.
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, Texts in Applied Mathematics, vol. 15, Springer-Verlag, New York, 1994. MR 1278258, DOI 10.1007/978-1-4757-4338-8
Chunjia Bi and Victor Ginting, Two-grid finite volume element method for linear and nonlinear elliptic problems, Numer. Math. 108 (2007), no. 2, 177–198. MR 2358002, DOI 10.1007/s00211-007-0115-9
Zhi Qiang Cai, Jan Mandel, and Steve McCormick, The finite volume element method for diffusion equations on general triangulations, SIAM J. Numer. Anal. 28 (1991), no. 2, 392–402. MR 1087511, DOI 10.1137/0728022
Zhi Qiang Cai, On the finite volume element method, Numer. Math. 58 (1991), no. 7, 713–735. MR 1090257, DOI 10.1007/BF01385651
Waixiang Cao, Zhimin Zhang, and Qingsong Zou, Is $2k$-conjecture valid for finite volume methods?, SIAM J. Numer. Anal. 53 (2015), no. 2, 942–962. MR 3328149, DOI 10.1137/130936178
Long Chen, A new class of high order finite volume methods for second order elliptic equations, SIAM J. Numer. Anal. 47 (2010), no. 6, 4021–4043. MR 2585177, DOI 10.1137/080720164
Zhongying Chen, Yuesheng Xu, and Yuanyuan Zhang, A construction of higher-order finite volume methods, Math. Comp. 84 (2015), no. 292, 599–628. MR 3290957, DOI 10.1090/S0025-5718-2014-02881-0
Zhongying Chen, Junfeng Wu, and Yuesheng Xu, Higher-order finite volume methods for elliptic boundary value problems, Adv. Comput. Math. 37 (2012), no. 2, 191–253. MR 2944051, DOI 10.1007/s10444-011-9201-8
So-Hsiang Chou and Xiu Ye, Unified analysis of finite volume methods for second order elliptic problems, SIAM J. Numer. Anal. 45 (2007), no. 4, 1639–1653. MR 2338403, DOI 10.1137/050643994
Qiang Du, Desheng Wang, and Liyong Zhu, On mesh geometry and stiffness matrix conditioning for general finite element spaces, SIAM J. Numer. Anal. 47 (2009), no. 2, 1421–1444. MR 2497335, DOI 10.1137/080718486
Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20 (1983), no. 2, 345–357. MR 694523, DOI 10.1137/0720023
Alexandre Ern and Jean-Luc Guermond, Theory and practice of finite elements, Applied Mathematical Sciences, vol. 159, Springer-Verlag, New York, 2004. MR 2050138, DOI 10.1007/978-1-4757-4355-5
Richard E. Ewing, Tao Lin, and Yanping Lin, On the accuracy of the finite volume element method based on piecewise linear polynomials, SIAM J. Numer. Anal. 39 (2002), no. 6, 1865–1888. MR 1897941, DOI 10.1137/S0036142900368873
Isaac Fried, Bounds on the spectral and maximum norms of the finite element stiffness, flexibility and mass matrices, Internat. J. Solids Structures 9 (1973), 1013–1034 (English, with Russian summary). MR 345400, DOI 10.1016/0020-7683(73)90013-9
David Gilbarg and Neil S. Trudinger, Elliptic partial differential equations of second order, Classics in Mathematics, Springer-Verlag, Berlin, 2001. Reprint of the 1998 edition. MR 1814364
Ivan G. Graham and William McLean, Anisotropic mesh refinement: the conditioning of Galerkin boundary element matrices and simple preconditioners, SIAM J. Numer. Anal. 44 (2006), no. 4, 1487–1513. MR 2257114, DOI 10.1137/040621247
W. Hackbusch, On first and second order box schemes, Computing 41 (1989), no. 4, 277–296 (English, with German summary). MR 993825, DOI 10.1007/BF02241218
Weizhang Huang, Sign-preserving of principal eigenfunctions in P1 finite element approximation of eigenvalue problems of second-order elliptic operators, J. Comput. Phys. 274 (2014), 230–244. MR 3231765, DOI 10.1016/j.jcp.2014.06.012
W. Huang, L. Kamenski, and J. Lang, Stability of explicit Runge-Kutta methods for high order finite element approximation of linear parabolic equations, in Numerical Mathematics and Advanced Applications (Proceedings of the 2013 European Numerical Mathematics and Advanced Applications Conference ENUMATH-2013, Lausanne, Switzerland, August 26–30, 2013), Lecture Notes in Computational Science and Engineering, vol. 103, Springer, Cham, 2015, pp. 165–173.
Weizhang Huang, Lennard Kamenski, and Jens Lang, Stability of explicit one-step methods for P1-finite element approximation of linear diffusion equations on anisotropic meshes, SIAM J. Numer. Anal. 54 (2016), no. 3, 1612–1634. MR 3505307, DOI 10.1137/130949531
Weizhang Huang and Robert D. Russell, Adaptive moving mesh methods, Applied Mathematical Sciences, vol. 174, Springer, New York, 2011. MR 2722625, DOI 10.1007/978-1-4419-7916-2
Lennard Kamenski and Weizhang Huang, A study on the conditioning of finite element equations with arbitrary anisotropic meshes via a density function approach, J. Math. Study 47 (2014), no. 2, 151–172. MR 3260337, DOI 10.4208/jms.v47n2.14.02
L. Kamenski, W. Huang, and J. Lang, Conditioning of implicit Runge-Kutta integration of finite element approximation of linear diffusion equations on anisotropic meshes, (submitted), 2017.
Lennard Kamenski, Weizhang Huang, and Hongguo Xu, Conditioning of finite element equations with arbitrary anisotropic meshes, Math. Comp. 83 (2014), no. 289, 2187–2211. MR 3223329, DOI 10.1090/S0025-5718-2014-02822-6
Ronghua Li, Zhongying Chen, and Wei Wu, Generalized difference methods for differential equations, Monographs and Textbooks in Pure and Applied Mathematics, vol. 226, Marcel Dekker, Inc., New York, 2000. Numerical analysis of finite volume methods. MR 1731376
Yonghai Li, Shi Shu, Yuesheng Xu, and Qingsong Zou, Multilevel preconditioning for the finite volume method, Math. Comp. 81 (2012), no. 279, 1399–1428. MR 2904584, DOI 10.1090/S0025-5718-2012-02582-8
F. Liebau, The finite volume element method with quadratic basis functions, Computing 57 (1996), no. 4, 281–299 (English, with English and German summaries). MR 1422087, DOI 10.1007/BF02252250
Yanping Lin, Min Yang, and Qingsong Zou, $L^2$ error estimates for a class of any order finite volume schemes over quadrilateral meshes, SIAM J. Numer. Anal. 53 (2015), no. 4, 2009–2029. MR 3384836, DOI 10.1137/140963121
Junliang Lv and Yonghai Li, Optimal biquadratic finite volume element methods on quadrilateral meshes, SIAM J. Numer. Anal. 50 (2012), no. 5, 2379–2399. MR 3022223, DOI 10.1137/100805881
T. Schmidt, Box schemes on quadrilateral meshes, Computing 51 (1993), no. 3-4, 271–292 (English, with English and German summaries). MR 1253406, DOI 10.1007/BF02238536
J. R. Shewchuk, What is a good linear element?—Interpolation, conditioning, and quality measures, in Proceedings of the 11th International Meshing Roundtable, Sandia National Laboratories, Albuquerque, NM, 2002, 115–126.
Xiang Wang and Yonghai Li, $L^2$ error estimates for high order finite volume methods on triangular meshes, SIAM J. Numer. Anal. 54 (2016), no. 5, 2729–2749. MR 3544655, DOI 10.1137/140988486
Xiang Wang and Yonghai Li, Superconvergence of quadratic finite volume method on triangular meshes, J. Comput. Appl. Math. 348 (2019), 181–199. MR 3886669, DOI 10.1016/j.cam.2018.08.025
A. J. Wathen, Realistic eigenvalue bounds for the Galerkin mass matrix, IMA J. Numer. Anal. 7 (1987), no. 4, 449–457. MR 968517, DOI 10.1093/imanum/7.4.449
Jinchao Xu and Qingsong Zou, Analysis of linear and quadratic simplicial finite volume methods for elliptic equations, Numer. Math. 111 (2009), no. 3, 469–492. MR 2470148, DOI 10.1007/s00211-008-0189-z
Min Yang, Chunjia Bi, and Jiangguo Liu, Postprocessing of a finite volume element method for semilinear parabolic problems, M2AN Math. Model. Numer. Anal. 43 (2009), no. 5, 957–971. MR 2559740, DOI 10.1051/m2an/2009017
Zhimin Zhang and Qingsong Zou, Vertex-centered finite volume schemes of any order over quadrilateral meshes for elliptic boundary value problems, Numer. Math. 130 (2015), no. 2, 363–393. MR 3343929, DOI 10.1007/s00211-014-0664-7
Liyong Zhu and Qiang Du, Mesh-dependent stability for finite element approximations of parabolic equations with mass lumping, J. Comput. Appl. Math. 236 (2011), no. 5, 801–811. MR 2853505, DOI 10.1016/j.cam.2011.05.030
Liyong Zhu and Qiang Du, Mesh dependent stability and condition number estimates for finite element approximations of parabolic problems, Math. Comp. 83 (2014), no. 285, 37–64. MR 3120581, DOI 10.1090/S0025-5718-2013-02703-2