Multilevel preconditioning for the finite volume method

Li, Yonghai; Shu, Shi; Xu, Yuesheng; Zou, Qingsong

doi:10.1090/S0025-5718-2012-02582-8

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