Multilevel preconditioning for the finite volume method
HTML articles powered by AMS MathViewer
- by Yonghai Li, Shi Shu, Yuesheng Xu and Qingsong Zou PDF
- Math. Comp. 81 (2012), 1399-1428 Request permission
Abstract:
We consider the precondition of linear systems which resulted from the finite volume method (FVM) for elliptic boundary value problems. With the help of the interpolation operator from the trial space to the test space of the FVM and the operator induced by the FVM bilinear form, we show that both wavelet preconditioners and multilevel preconditioners designed originally for the finite element method (FEM) of a boundary value problem can be used to precondition the FVM of the same boundary value problem. We prove that such preconditioners ensure that the resulting coefficient matrix of the FVM has a uniformly bounded condition number. We present seven numerical examples to confirm our theoretical findings.References
- 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
- James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
- 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
- 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
- Zhong Ying Chen, The error estimate of generalized difference method of $3$rd-order Hermite type for elliptic partial differential equations, Northeast. Math. J. 8 (1992), no. 2, 127–135. MR 1182874
- Zhongying Chen, Ronghua Li, and Aihui Zhou, A note on the optimal $L^2$-estimate of the finite volume element method, Adv. Comput. Math. 16 (2002), no. 4, 291–303. MR 1894926, DOI 10.1023/A:1014577215948
- Zhongying Chen, Bin Wu, and Yuesheng Xu, Multilevel augmentation methods for differential equations, Adv. Comput. Math. 24 (2006), no. 1-4, 213–238. MR 2222269, DOI 10.1007/s10444-004-4092-6
- Z. Chen, J. Wu and Y. Xu, Higher-order finite volume methods for elliptic boundary value problems, Adv. Comput. Math., to appear.
- Zhongying Chen and Yuesheng Xu, The Petrov-Galerkin and iterated Petrov-Galerkin methods for second-kind integral equations, SIAM J. Numer. Anal. 35 (1998), no. 1, 406–434. MR 1618413, DOI 10.1137/S0036142996297217
- S. H. Chou and D. Y. Kwak, A covolume method based on rotated bilinears for the generalized Stokes problem, SIAM J. Numer. Anal. 35 (1998), no. 2, 494–507. MR 1618834, DOI 10.1137/S0036142996299964
- So-Hsiang Chou and Do Y. Kwak, Multigrid algorithms for a vertex-centered covolume method for elliptic problems, Numer. Math. 90 (2002), no. 3, 441–458. MR 1884225, DOI 10.1007/s002110100288
- 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
- Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 55–228. MR 1489256, DOI 10.1017/S0962492900002713
- Wolfgang Dahmen and Angela Kunoth, Multilevel preconditioning, Numer. Math. 63 (1992), no. 3, 315–344. MR 1186345, DOI 10.1007/BF01385864
- W. Dahmen, S. Prössdorf, and R. Schneider, Wavelet approximation methods for pseudodifferential equations. I. Stability and convergence, Math. Z. 215 (1994), no. 4, 583–620. MR 1269492, DOI 10.1007/BF02571732
- Wolfgang Dahmen, Reinhold Schneider, and Yuesheng Xu, Nonlinear functionals of wavelet expansions—adaptive reconstruction and fast evaluation, Numer. Math. 86 (2000), no. 1, 49–101. MR 1774010, DOI 10.1007/PL00005403
- Wolfgang Dahmen and Rob Stevenson, Element-by-element construction of wavelets satisfying stability and moment conditions, SIAM J. Numer. Anal. 37 (1999), no. 1, 319–352. MR 1742747, DOI 10.1137/S0036142997330949
- Ronald A. DeVore and George G. Lorentz, Constructive approximation, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 303, Springer-Verlag, Berlin, 1993. MR 1261635
- Robert Eymard, Thierry Gallouët, and Raphaèle Herbin, Finite volume methods, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, North-Holland, Amsterdam, 2000, pp. 713–1020. MR 1804748, DOI 10.1086/phos.67.4.188705
- 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
- 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
- M. Griebel and P. Oswald, Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems, Adv. Comput. Math. 4 (1995), no. 1-2, 171–206. MR 1338900, DOI 10.1007/BF02123478
- Rong-Qing Jia and Song-Tao Liu, Wavelet bases of Hermite cubic splines on the interval, Adv. Comput. Math. 25 (2006), no. 1-3, 23–39. MR 2231693, DOI 10.1007/s10444-003-7609-5
- Uwe Kotyczka and Peter Oswald, Piecewise linear prewavelets of small support, Approximation theory VIII, Vol. 2 (College Station, TX, 1995) Ser. Approx. Decompos., vol. 6, World Sci. Publ., River Edge, NJ, 1995, pp. 235–242. MR 1471789
- R. Li, Generalized difference methods for two points boundary problem, Acta Scietiarum Naturalium Universitatis Jilineness, 1 (1982), 26-40 (in Chinese).
- R. Li and P. Zhu, Generalized difference methods for second order elliptic partial differential equations (I), Numer. Math., A Journal of Chinese Univ., 2 (1982), 140-152 (in Chinese).
- Rong Hua Li, Generalized difference methods for a nonlinear Dirichlet problem, SIAM J. Numer. Anal. 24 (1987), no. 1, 77–88. MR 874736, DOI 10.1137/0724007
- Yong-hai Li and Rong-hua Li, Generalized difference methods on arbitrary quadrilateral networks, J. Comput. Math. 17 (1999), no. 6, 653–672. MR 1723103
- 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
- Junliang Lv and Yonghai Li, $L^2$ error estimate of the finite volume element methods on quadrilateral meshes, Adv. Comput. Math. 33 (2010), no. 2, 129–148. MR 2659583, DOI 10.1007/s10444-009-9121-z
- P. Oswald, On function spaces related to finite element approximation theory, Z. Anal. Anwendungen 9 (1990), no. 1, 43–64 (English, with German and Russian summaries). MR 1063242, DOI 10.4171/ZAA/380
- P. Oswald, On discrete norm estimates related to multilevel preconditioners in the finite element method, Constructive Theory of Functions, Varna’ 91, Sofia, 1992, 203-214.
- Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
- Rob Stevenson, Locally supported, piecewise polynomial biorthogonal wavelets on nonuniform meshes, Constr. Approx. 19 (2003), no. 4, 477–508. MR 1998901, DOI 10.1007/s00365-003-0545-2
- Endre Süli, The accuracy of cell vertex finite volume methods on quadrilateral meshes, Math. Comp. 59 (1992), no. 200, 359–382. MR 1134740, DOI 10.1090/S0025-5718-1992-1134740-X
- Yuzhi Sun, Z. J. Wang, and Yen Liu, Spectral (finite) volume method for conservation laws on unstructured grids. VI. Extension to viscous flow, J. Comput. Phys. 215 (2006), no. 1, 41–58. MR 2215651, DOI 10.1016/j.jcp.2005.10.019
- Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
- Jinchao Xu, An introduction to multigrid convergence theory, Iterative methods in scientific computing (Hong Kong, 1995) Springer, Singapore, 1997, pp. 169–241. MR 1661962
- Jinchao Xu, An introduction to multilevel methods, Wavelets, multilevel methods and elliptic PDEs (Leicester, 1996) Numer. Math. Sci. Comput., Oxford Univ. Press, New York, 1997, pp. 213–302. MR 1600688
- Jinchao Xu and Xiao-Chuan Cai, A preconditioned GMRES method for nonsymmetric or indefinite problems, Math. Comp. 59 (1992), no. 200, 311–319. MR 1134741, DOI 10.1090/S0025-5718-1992-1134741-1
- Jinchao Xu and Yunrong Zhu, Uniform convergent multigrid methods for elliptic problems with strongly discontinuous coefficients, Math. Models Methods Appl. Sci. 18 (2008), no. 1, 77–105. MR 2378084, DOI 10.1142/S0218202508002619
- 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
- Yuesheng Xu and Qingsong Zou, Adaptive wavelet methods for elliptic operator equations with nonlinear terms, Adv. Comput. Math. 19 (2003), no. 1-3, 99–146. Challenges in computational mathematics (Pohang, 2001). MR 1973461, DOI 10.1023/A:1022816511874
- Yuesheng Xu and Qingsong Zou, Tree wavelet approximations with applications, Sci. China Ser. A 48 (2005), no. 5, 680–702. MR 2158483, DOI 10.1360/04ys0173
- Harry Yserentant, On the multilevel splitting of finite element spaces, Numer. Math. 49 (1986), no. 4, 379–412. MR 853662, DOI 10.1007/BF01389538
- Harry Yserentant, Two preconditioners based on the multi-level splitting of finite element spaces, Numer. Math. 58 (1990), no. 2, 163–184. MR 1069277, DOI 10.1007/BF01385617
- Pi Qi Zhu and Rong Hua Li, Generalized difference methods for second-order elliptic partial differential equations. II. Quadrilateral subdivision, Numer. Math. J. Chinese Univ. 4 (1982), no. 4, 360–375 (Chinese, with English summary). MR 696348
- Qingsong Zou, Hierarchical error estimates for finite volume approximation solution of elliptic equations, Appl. Numer. Math. 60 (2010), no. 1-2, 142–153. MR 2566084, DOI 10.1016/j.apnum.2009.10.006
Additional Information
- Yonghai Li
- Affiliation: Department of Mathematics, Jilin University, Changchun, 130012, People’s Republic of China
- MR Author ID: 363086
- Email: yonghai@jlu.edu.cn
- Shi Shu
- Affiliation: School of Mathematical and Computational Sciences, Xiangtan University, Hunan 411105, China
- Email: shushi@xtu.edu.cn
- Yuesheng Xu
- Affiliation: Department of Mathematics, Syracuse University, Syracuse, New York 13244, and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Guangzhou, 510275, People’s Republic of China
- MR Author ID: 214352
- Email: yxu06@syr.edu
- Qingsong Zou
- Affiliation: Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Guangzhou, 510275, People’s Republic of China.
- Email: mcszqs@mail.sysu.edu.cn
- Received by editor(s): July 14, 2010
- Received by editor(s) in revised form: April 18, 2011
- Published electronically: February 29, 2012
- Additional Notes: The first author was supported by the ‘985’ programme of Jilin University, the National Natural Science Foundation of China (No.10971082) and the NSAF of China (Grant No.11076014)
The second author was partially supported by the NSFC Key Project (Grant No.11031006) and the Provincial Natural Science Foundation of China (Grant No.10JJ7001), and the Aid Program for Science and Technology Innovative Research Team in Higher Educational Institutions of Hunan Province of China.
The third and corresponding author is partially supported by the US Air Force Office of Scientific Research under grant FA9550-09-1-0511, by Guangdong Provincial Government of China through the “Computational Science Innovative Research Team” program, and by the Natural Science Foundation of China under grant 11071286
The fourth author is supported in part by the Fundamental Research Funds for the Central Universities and National Natural Science Foundation of China under grant 11171359 - © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 81 (2012), 1399-1428
- MSC (2010): Primary 65N08, 65F08, 65N55
- DOI: https://doi.org/10.1090/S0025-5718-2012-02582-8
- MathSciNet review: 2904584