Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Multilevel preconditioning for the finite volume method


Authors: Yonghai Li, Shi Shu, Yuesheng Xu and Qingsong Zou
Journal: Math. Comp. 81 (2012), 1399-1428
MSC (2010): Primary 65N08, 65F08, 65N55
DOI: https://doi.org/10.1090/S0025-5718-2012-02582-8
Published electronically: February 29, 2012
Previous version: Originally posted February 16, 2012
MathSciNet review: 2904584
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. R. E. Bank and D. J. Rose, Some error estimates for the box method, SIAM J. Numer. Anal., 24 (1987), 777-787. MR 899703 (88j:65235)
  • 2. J. H. Bramble, J. E. Pasciak and J. Xu, Parallel multilevel preconditioners, Math. Comp., 55 (1990), 1-22. MR 1023042 (90k:65170)
  • 3. Z. Cai, J. Mandel and S. McCormick, The finite volume element for diffusion equations on general triangulations, SIAM J. Numer. Anal., 28 (1991), 392-402. MR 1087511 (92j:65165)
  • 4. Z. Cai, On the finite volume element method, Numer. Math., 58 (1991), 713-735. MR 1090257 (92d:65188)
  • 5. L. Chen, A new class of high order finite volume methods for second order elliptic equations, SIAM J. Numer. Anal., 47(2010), 4021-4043. MR 2585177
  • 6. Z. Chen, The error estimate of generalized difference method 3rd-order Hermite type for elliptic partial differential equations, Northeast. Math. J., 8 (1992), 127-135. MR 1182874 (93e:65125)
  • 7. Z. Chen, R. Li and A. Zhou, A note on the optimal estimate of the finite volume element method, Adv. Comput. Math., 16 (2002), 291-302. MR 1894926 (2002m:65113)
  • 8. Z. Chen, B. Wu and Y. Xu, Multilevel augmentation methods for differential equations, Adv. Comput. Math., 24(2006), 213-238. MR 2222269 (2007a:65075)
  • 9. Z. Chen, J. Wu and Y. Xu, Higher-order finite volume methods for elliptic boundary value problems, Adv. Comput. Math., to appear.
  • 10. Z. Chen and Y. Xu, The Petrov-Galerkin and iterated Petrov-Galerkin methods for second-kind integral equations, SIAM J. Numer. Anal., 35 (1998), 406-434. MR 1618413 (99h:65214)
  • 11. 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), 494-507. MR 1618834 (99d:65302)
  • 12. S. H. Chou and D. Y. Kwak, Multigrid algorithms for a vertex-centered covolume method for elliptic problems, Numer. Math., 90 (2002), 441-458. MR 1884225 (2002k:65209)
  • 13. P. G. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, 1978. MR 0520174 (58:25001)
  • 14. W. Dahmen, Wavelet and multiscale methods for operator equations, Acta Numerica 7 (1997), 55-228. MR 1489256 (98m:65102)
  • 15. W. Dahmen and A. Kunoth, Multilevel precorditioning, Numer. Math., 63 (1992), 315-344. MR 1186345 (93j:65065)
  • 16. W. Dahmen, S. Prössdorf, and R. Schneider, Wavelet approximation methods for pseudodifferential equations I: Stability and convergence, Math. Z., 215 (1994), 583-620. MR 1269492 (95g:65148)
  • 17. W. Dahmen, R. Schneider and Y. Xu, Nonlinear functionals of wavelet expansions - Adaptive reconstruction and fast evaluation, Numer. Math. 86 (2000), 49-101. MR 1774010 (2001g:65180)
  • 18. W. Dahmen and R. Stevenson, Element-by-element contruction of wavelets satisfying stability and moment conditions, SIAM J. Numer. Anal. 37(1999), 319-352. MR 1742747 (2001c:65144)
  • 19. R. A. DeVore and G. G. Lorentz, Constructive Approximation, Springer-Verlag, Berlin, 1993. MR 1261635 (95f:41001)
  • 20. R. Eymard, T. Gallouet, and R. Herbin, Finite Volume Methods, in Handbook of Numerical Analysis VII, North-Holland, Amsterdam, 2000, pp. 713-1020. MR 1804748 (2002e:65138)
  • 21. R. E. Ewing, T. Lin, and Y. Lin, On the accuracy of finite volume element method based on piecewise linear polynomials, SIAM J. Numer. Anal., 39 (2002), 1865-1888. MR 1897941 (2003d:65105)
  • 22. S. C. Eisenstat, H. C. Elman, and M. H. Schultz, Variational iterative methods for nonsymmetric linear systems, SIAM. J. Numer. Anal. 20(1983), 345-357. MR 694523 (84h:65030)
  • 23. M. Griebel and P. Oswald, Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems, Adv. Comput. Math., 4 (1995), 171-206. MR 1338900 (96e:65069)
  • 24. R.-Q. Jia and S. T. Liu, Wavelet bases of Hermite cubic splines on the interval, Adv. Comput. Math. 25 (2006), 23-39. MR 2231693 (2007e:42043)
  • 25. U. Kotyczka and P. Oswald, Piecewise linear pre-wavelets of small Support, in Approximation Theory VIII, Vol 2. Wavelets and Multilevel Approximation, Charles K. Chui and Larry L. Schumaker (eds.), 243-250, World Scientific Publishing Co.,1995. MR 1471789 (98e:42035)
  • 26. R. Li, Generalized difference methods for two points boundary problem, Acta Scietiarum Naturalium Universitatis Jilineness, 1 (1982), 26-40 (in Chinese).
  • 27. 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).
  • 28. R. Li, Generalized difference methods for a nonlinear Dirichlet problem, SIAM J. Numer. Anal., 24 (1987), 77-88. MR 874736 (88c:65091)
  • 29. Y. Li and R. Li, Generalized difference methods on arbitrary quadrilateral networks, J. Comput. Math., 17 (1999), 653-672. MR 1723103 (2000g:65103)
  • 30. R. Li, Z. Chen and W. Wu, The generalized difference methods for differential equations (Numerical analysis of finite volume methods), Marcel Dekker, New York, 2000. MR 1731376 (2000j:65003)
  • 31. J. Lv and Y. Li, $ L^2$ error estimate of the finite volume element methods on quadrilateral meshes, Adv. Comput. Math., 33 (2010), 129-148. MR 2659583 (2011e:65234)
  • 32. P. Oswald, On function spaces related to finite element approximatin theory, Zeitschrift f$ \ddot {u}$r Analysis und ihre Anwendungen Bd., 9 (1990), 43-64. MR 1063242 (91g:65246)
  • 33. 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.
  • 34. Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), 856-869. MR 848568 (87g:65064)
  • 35. R. Stevenson, Locally supported, piecewise polynomial biorthogonal wavelets on non-uniform meshes, Constr. Approx., 19 (2003), 477-508. MR 1998901 (2005a:42032)
  • 36. E. Süli, The accuracy of cell vertex finite volume methods on quadrilateral meshes, Math. Comp., 59 (1992), 359-382. MR 1134740 (93a:65158)
  • 37. Y. Sun, Z. Wang, and Y. Liu, Spectral finite volume method for conservation laws on unstructrured grids VI: Extension to viscous flow, J. Comp. Phys., 215 (2006), 41-58. MR 2215651
  • 38. J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review, 34 (1992), 581-613. MR 1193013 (93k:65029)
  • 39. J. Xu, An introduction to multigrid convergence theory, in ``Iterative Methods in Scientific Computing'', (editors: R. Chan, T. Chan and G. Golub), Springer-Verlag, Singapore, 1997. MR 1661962
  • 40. J. Xu, An introduction to multilevel methods, in Wavelets, Multilevel Methods and Elliptic PDEs, 213-302, edited by M. Ainsworth, J. Levesley, M. Marletta, W. A. Light, Oxford Univ. Press, New York, 1997. MR 1600688 (99d:65329)
  • 41. J. Xu and X. Cai, A preconditioned GMRES method for nonsymmetric and indefinite problems, Math. Comp., 59 (1992), 311-319. MR 1134741 (93a:65059)
  • 42. J. Xu, and Y. Zhu, Uniform convergent multigrid methods for elliptic problem with strong discontinuous coefficients, Mathematical Models and Methods in Applied Sciences, 2008, 18, 77-105. MR 2378084 (2008k:65271)
  • 43. J. Xu and Q. Zou,
    Analysis of linear and quadratic finite volume methods for elliptic equations.
    Numerische Mathematik, 111(2009), 469-492. MR 2470148 (2009i:65199)
  • 44. Y. Xu and Q. Zou, Adaptive wavelet methods for elliptic operator equations with nonlinear terms, Adv. Comput. Math., 19 (2003), 99-146. MR 1973461 (2004f:65201)
  • 45. Y. Xu and Q. Zou, Tree wavelet approximations with applications, Sciences in China Ser. A Math., 48 (2005), 680-702. MR 2158483 (2006c:42036)
  • 46. H. Yserentant, On the multi-level splitting of finite element spaces, Numer. Math., 49 (1986), 379-412. MR 853662 (88d:65068a)
  • 47. H. Yserentant, Two preconditioners based on the multi-level splitting of finite element spaces, Numer. Math., 58 (1990), 163-184. MR 1069277 (91j:65076)
  • 48. P. Zhu and R. Li, Generalized difference methods (finite volume methods) for second order elliptic partial differential equations (II), Numer. Math. A Journal of Chinese Univ., 4 (1982), 360-375 (in Chinese). MR 696348 (84m:65116)
  • 49. Q. Zou, Hierarchical error estimates for finite volume approximation solution of elliptic equations, Applied Numerical Mathematics, 60 (2010), 142-153. MR 2566084 (2010j:65215)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65N08, 65F08, 65N55

Retrieve articles in all journals with MSC (2010): 65N08, 65F08, 65N55


Additional Information

Yonghai Li
Affiliation: Department of Mathematics, Jilin University, Changchun, 130012, People’s Republic of China
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
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

DOI: https://doi.org/10.1090/S0025-5718-2012-02582-8
Keywords: The finite volume method, preconditioning, the multilevel method.
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
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society