求解二阶混合有限体元离散系统的高效预条件子
|
摘要
有限体元(FVE)法是一种常用的偏微分方程离散化方法最近发展起来的二阶混合有限体元法由于具有保持局部守恒性以及控制体结构简单等特点，受到人们的关注，本文将为该方法对应的离散系统设计快速算法
首先，针对‘种含跳系数的椭圆问题在分层基下的二阶混台有限体元离散系统，利用基于两种常用预条件子，ILu和AMG的PGMRES(m)法进行求解数值结果表明，它们的求解效率都不高，其迭代次数依赖于网格规模和跳系数因此，有必要发展新的高效预条件了
接着，奉文为上述离散系统设计了两种预条件了：块对角预条件了和两水平预条件了对于前者，在‘致三角形剖分下给出了相应的理论分析，得到了预条件系统谱条件数‘致有界的结论数值结果表明，我们设计的预条件了是高效的，相应PGMRES(m)法的迭代次数明显减少，它个依赖于网格规模，且对跳系数和重启参数m的选取均个敏感
Finite Volume Element (FVE) method is one of the discretization methods for partialdifferential equations. Second order mixed-type finite volume element method which wasdeveloped recently has many advantages, such as being able to preserve local conservationof certain physical quantities. Fast algorithms for the corresponding discretization systemswill be discussed in this paper.
Firstly, ILU- and AMG-GMRES(m) are employed to solve the linear systems arisingfrom second order mixed-type finite volume element scheme for an elliptic problem withjump coefficients. Numerical results show that the numbers of iteration of the two PGM-RES (m) are unstable which strongly depend on not only the mesh size but also the jumpcoefficient. Therefore, it is quite necessary to develop newly efficient preconditioners.
Secondly, two new preconditioners are designed for the above linear systems, i.e., blockdiagonal and two-level preconditioner. For consistent mesh, theoretical analysis of the for-mer is given, and it is proved that the spectral condition number of the preconditioned sys-tem is uniformly bounded. Numerical results show that our preconditioners are stable andefficient. The numbers of iteration of the corresponding PGMRES (m) are significantly re-duced, furthermore, they are independent of mesh size and insensitive to jump coefficient orrestart parameter.
首先，针对‘种含跳系数的椭圆问题在分层基下的二阶混台有限体元离散系统，利用基于两种常用预条件子，ILu和AMG的PGMRES(m)法进行求解数值结果表明，它们的求解效率都不高，其迭代次数依赖于网格规模和跳系数因此，有必要发展新的高效预条件了
接着，奉文为上述离散系统设计了两种预条件了：块对角预条件了和两水平预条件了对于前者，在‘致三角形剖分下给出了相应的理论分析，得到了预条件系统谱条件数‘致有界的结论数值结果表明，我们设计的预条件了是高效的，相应PGMRES(m)法的迭代次数明显减少，它个依赖于网格规模，且对跳系数和重启参数m的选取均个敏感
Finite Volume Element (FVE) method is one of the discretization methods for partialdifferential equations. Second order mixed-type finite volume element method which wasdeveloped recently has many advantages, such as being able to preserve local conservationof certain physical quantities. Fast algorithms for the corresponding discretization systemswill be discussed in this paper.
Firstly, ILU- and AMG-GMRES(m) are employed to solve the linear systems arisingfrom second order mixed-type finite volume element scheme for an elliptic problem withjump coefficients. Numerical results show that the numbers of iteration of the two PGM-RES (m) are unstable which strongly depend on not only the mesh size but also the jumpcoefficient. Therefore, it is quite necessary to develop newly efficient preconditioners.
Secondly, two new preconditioners are designed for the above linear systems, i.e., blockdiagonal and two-level preconditioner. For consistent mesh, theoretical analysis of the for-mer is given, and it is proved that the spectral condition number of the preconditioned sys-tem is uniformly bounded. Numerical results show that our preconditioners are stable andefficient. The numbers of iteration of the corresponding PGMRES (m) are significantly re-duced, furthermore, they are independent of mesh size and insensitive to jump coefficient orrestart parameter.
引文
[1] O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, UK,1994.
[2] A.Brandt, Algebraic Multigrid theory: the symmetric case, App.Math.Comp., 19:23-25,1986.
[3] W.L.Briggs, V.E.Henson, S.F.McCormick, A multigrid tutorial, 2nd Edition, SIAM Publi-cation, 2000.
[4] Alison Baker, Elizabeth R Jessup, and Tz. V. Kolev, A simple srategy for varying the restartparameter in GMRES(m), Journal of Computational and Applied Mathematics, 26:962,2009.
[5] A. H. Baker, E. R. Jessup, T. Manteuffel, A technique for accelerating the convergenceof restarted GMRES, SIAM Journal on Matrix Analysis and Applications, 26(4):962-984,2005.
[6] A.Brandt, S.McCormick, J.Ruge, Algebraic multigrid (AMG)for automatic multigrid so-lution with application to geodetic computations, Institute for Computational Studies, POB1852, Fort Collins, Colorado, 1982.
[7] R.E. Bank , D.J. Rose, Some error estimates for the box scheme, SIAM Journal on Numer-ical Analysis, 24:777-787, 1987.
[8] L. Chen , A new class of high order finite volume methods for second order elliptic equa-tions[J], SIAM Journal on Numerical Analysis, 47(6): 4021-4043, 2010.
[9] A.J.Cleary, R.D.Falgout, V.E.Henson, J.E.Jones, Coarse-grid selection for parallel algebraicmultigrid, Lecture Notes in Computer Science 1457, Springer Verlag, New York,104-115,1998.
[10] Q.S.Chang, Z.H.Huang, Efficient algebaic multigrid algorithms and their convergence[J],SIAM J.Sci.Comp, 24(2): 597-618, 2002.
[11] S.H. Chou, D.Y. Kwak and Q. Li, Lp error estimates and superconvergence for covolumeor finite volume element methods, Numer. Methods Partial Differential Equations, 19: 463-486, 2003.
[12] E. Chow and Y. Saad, Experimental study of ILU preconditioners of indenite matrices, J.Comput. Appl. Math, 387-414, 86 (1997).
[13] Q.S.Chang, Y.S.Wong, H.Fu, On the algebraic multigrid method, JCP, 125: 279-292, 1996.
[14] T.F.Chan, L.Zikatanov, J.Xu, An agglomeration multigrid method for unstructured grids,Proceedings of the 10th International Conference on DD Methods, Contemporary Mathe-matics, SIAM, 218:67-81, 1998.
[15] E. F. D’Azevedo, P. A. Forsyth, and W.-P. Tang, Towards a costeffctive ILU preconditionerwith high level fill, BIT, 442-463, 32 (1992).
[16] R.D.Falgout, An introduction to algebraic multigrid, Computing in Science and Engineer-ing, special issue on multigrid computing, 8:24-33, 2006. Also appear in LLNL reportNO.UCRL-JRNL-220851, 2006.
[17] R.D.Falgout, P.S.Vassilevski, On generalizing the AMG framework, SIAM J. Numer. Anal,42:1669-1693, 2004.
[18] J. R. Gilbert and J. W. H. Liu, Elimination structures for unsymmetric sparse LU factors,SIAM J. Mat. Anal. and App, 334-352, 14 (1993).
[19] W. Hackbusch, On first and second order box schemes, Computing, 41:277-296, 1989.
[20] W.Z.Huang, Convergence of algebraic multigrid methods for symmetric positive-definitematrices with weak diagonal dominance, Appl.Math.Comp, 46:145-164, 1991.
[21] HYPRE: High performance preconditioner,http://computation.llnl.gov/casc/hypre/software.html
[22] D. Hysom, New Sequential and Scalable Parallel Algorithms for Incomplete Factor Precon-ditioning, PhD thesis, Old Dominion University, December 2001.
[23] David Hysom, Alex Pothen, Level-based Incomplete LU FactorizationGraph Model andAlgorithms, SIAM Journal On Matrix Analysis and Applications, 2002.
[24] D.S. Kershaw, Differencing of the diffusion equation in Lagrangle hydrodynamic code, J.Comput. Phys, 39:375-395, 1981.
[25] Ronghua Li, Zhongying Chen, Generalized difference methods for differential equa-tions[M], Jilin University Press, 1994.
[26] Junliang Lv ,Yonghai Li , L2 error estimate of the finite volume element methods on quadri-lateral meshes[J], Advances in Computational Mathematics, 33: 129-148, 2010.
[27]李德元，水鸿寿，汤敏君，关于非矩形网格上的二维抛物型力程的差分格式，数值计算与计算机应／可，1(4)：217-224，1980
[28]李荣，祝巫琦，二阶椭圆偏微分力程的广义差分法[I]-i角网情形，高校计算数学学报，2：140-152，1982
[29]李荣华，祝巫琦，二阶椭圆偏微分力程的广义差分法[II]-四边形网情形，高校计算数学学报，4：360．375，1982
[30]S Ma and Y Saad，Distributed ILU(0)and SOR Preconditioners for Unstructured Sparse Linear Systems，Tech report 94-27，Army High Performance Computing Research Center，University ofMinnesota,Minneapolis，MN,1994
[31]Cunyun Nie，Shi Shu，Zhiqiang Sheng，Symmetry-preserving finite volume element scheme on unstructured quadrilateral grids[J]，Chinese Journal ofComputational Physics，26(2)：91-99，2009
[32]J W．Ruge，K Sfiiben，Algebraic multigrid，in Multigrid Methods，Frontiers"Appl~ath 3，S．~EMcCormick．editor,SIAM,Philadehia，73-130，1987
[33]D J Rose，R E Tarjan，and G S Lueker,Algorithmic aspects of vertex elimination on graphs，SLAM，Comput，266-283，5(1976)
[34]Yousef Saad，Iterative Methods for Sparse Linear Systems，Second edition with corrections，January 3rd，2000
[35]T Schmidt，Box schemes on quadrilateral meshes，Computing，51：271-292，1993
[36]K St~ben，Algebraic multigrid(AMG)：an introduction with applications，GMD Report No 70．1999．Also available as an appendix in n4“，#grid,U Trottenberg,C H~Oosterlee．A Schuller,Academic PMSS．413-532．2001
[37]s Shu，I Babuska，Y．X Xiao，J Xu and L Zikatanov,Multilevel preconditioning methods for discrete models ofla~ice block materials，SLAM，Sci Comput，31(1)：687-707，2008
[38]s Shu，D Sun，J．Xu，An Algebraic Multigrid Method for Higher-order Finite Element Dis- cretizations，Computing 77，347-377，2006
[39]Y Saad and M Schultz，GMRES：A generalized minimal residual algorithm for solv- ing nonsymmetric linear systems，SIAM Journal on Scienitific and Statistical Computing, 7(3)：856 869，1986
[40]Shi Shu，Haiyuan Yu，Yunqing Huang，Cunyun Nie，A preserving-symmetry finite volume scheme and superconvergence on quadrangle grids[J]，Numerical Analysis and Modeling，3(3)：348-360，2006
[41]Tian Mingzhong，Chen Zhongying，A generalized difference method for second order ellip- tic partial differential equations[J]，NumericalMathematics．"A Journal ofChinese Univer- sities，2：99-1 13，1991
[42]谭敏，肖映熊舒适，‘种各向异性四边形网格l、的代数多重网格法，湘潭大学自然科学学报，27(1)：78-84，2005
[43]u M Ulrike，Parallel algebraic multigrid methods-high performance precondi oners，in Nu- merical solution ofpa~iM differential equations on parallel computers(edited by A M Bru- aset&A Tveito)，209-236，Springer-Verlag，2006，Also available as LL TechnicalReport NO UCRL-BooK-208032
[44]EVanek，J Mandel，M Brezina，Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems，Computing,56：179-196，1996
[45]Wang Ping，Zhang Zhiyue，Finite volume element method in air pollution model[J]，Chinese Journal ofComputational Physics，26(5)：655-664，2009
[46]Yx Xiao，s Shu，EZhang，M Tan，An algebraic multigrid method for isotropic linear elas-ticity on anisotropic meshes，Commun Numer3deth Engng(2008)_Online in Inter-Science(www．interscience~iley．com)，DoI：lO 1002／cnm 1140
[47]J．Xu，L Zikatanov,On the energy minimizing base for algebraic multigrid methods，Com—pu#ng and Visualization in Science，7：121-127，2004
[48]Xu 5nchao，Zou Qingsong，Analysis oflinear and quadratic simplicial finite volume meth- ods for elliptic equations[J]，Numerische Mathematik,1 1 1(3)：469-492，2009
[49]Min Yang，Cubic finite volume methods for second order elliptic equations with variable coeficients，NortheasternMathematicalJourna 21(2)：146-152，2005
[50]I J_M Yang，Long-range interpolation for parallel algebraic multigrid，ICIAMG07 talk Zurich，July,2007
[51]L Zaslavsky,An adaptive algebraic m~tigrid fo reactor critically calculations，SIAM J．Sci Comp，16：840-847，1995
[52]周志阳，聂存云，舒适，‘种二阶混合有限体元格式的GAMG预条子，计算，己接收
[2] A.Brandt, Algebraic Multigrid theory: the symmetric case, App.Math.Comp., 19:23-25,1986.
[3] W.L.Briggs, V.E.Henson, S.F.McCormick, A multigrid tutorial, 2nd Edition, SIAM Publi-cation, 2000.
[4] Alison Baker, Elizabeth R Jessup, and Tz. V. Kolev, A simple srategy for varying the restartparameter in GMRES(m), Journal of Computational and Applied Mathematics, 26:962,2009.
[5] A. H. Baker, E. R. Jessup, T. Manteuffel, A technique for accelerating the convergenceof restarted GMRES, SIAM Journal on Matrix Analysis and Applications, 26(4):962-984,2005.
[6] A.Brandt, S.McCormick, J.Ruge, Algebraic multigrid (AMG)for automatic multigrid so-lution with application to geodetic computations, Institute for Computational Studies, POB1852, Fort Collins, Colorado, 1982.
[7] R.E. Bank , D.J. Rose, Some error estimates for the box scheme, SIAM Journal on Numer-ical Analysis, 24:777-787, 1987.
[8] L. Chen , A new class of high order finite volume methods for second order elliptic equa-tions[J], SIAM Journal on Numerical Analysis, 47(6): 4021-4043, 2010.
[9] A.J.Cleary, R.D.Falgout, V.E.Henson, J.E.Jones, Coarse-grid selection for parallel algebraicmultigrid, Lecture Notes in Computer Science 1457, Springer Verlag, New York,104-115,1998.
[10] Q.S.Chang, Z.H.Huang, Efficient algebaic multigrid algorithms and their convergence[J],SIAM J.Sci.Comp, 24(2): 597-618, 2002.
[11] S.H. Chou, D.Y. Kwak and Q. Li, Lp error estimates and superconvergence for covolumeor finite volume element methods, Numer. Methods Partial Differential Equations, 19: 463-486, 2003.
[12] E. Chow and Y. Saad, Experimental study of ILU preconditioners of indenite matrices, J.Comput. Appl. Math, 387-414, 86 (1997).
[13] Q.S.Chang, Y.S.Wong, H.Fu, On the algebraic multigrid method, JCP, 125: 279-292, 1996.
[14] T.F.Chan, L.Zikatanov, J.Xu, An agglomeration multigrid method for unstructured grids,Proceedings of the 10th International Conference on DD Methods, Contemporary Mathe-matics, SIAM, 218:67-81, 1998.
[15] E. F. D’Azevedo, P. A. Forsyth, and W.-P. Tang, Towards a costeffctive ILU preconditionerwith high level fill, BIT, 442-463, 32 (1992).
[16] R.D.Falgout, An introduction to algebraic multigrid, Computing in Science and Engineer-ing, special issue on multigrid computing, 8:24-33, 2006. Also appear in LLNL reportNO.UCRL-JRNL-220851, 2006.
[17] R.D.Falgout, P.S.Vassilevski, On generalizing the AMG framework, SIAM J. Numer. Anal,42:1669-1693, 2004.
[18] J. R. Gilbert and J. W. H. Liu, Elimination structures for unsymmetric sparse LU factors,SIAM J. Mat. Anal. and App, 334-352, 14 (1993).
[19] W. Hackbusch, On first and second order box schemes, Computing, 41:277-296, 1989.
[20] W.Z.Huang, Convergence of algebraic multigrid methods for symmetric positive-definitematrices with weak diagonal dominance, Appl.Math.Comp, 46:145-164, 1991.
[21] HYPRE: High performance preconditioner,http://computation.llnl.gov/casc/hypre/software.html
[22] D. Hysom, New Sequential and Scalable Parallel Algorithms for Incomplete Factor Precon-ditioning, PhD thesis, Old Dominion University, December 2001.
[23] David Hysom, Alex Pothen, Level-based Incomplete LU FactorizationGraph Model andAlgorithms, SIAM Journal On Matrix Analysis and Applications, 2002.
[24] D.S. Kershaw, Differencing of the diffusion equation in Lagrangle hydrodynamic code, J.Comput. Phys, 39:375-395, 1981.
[25] Ronghua Li, Zhongying Chen, Generalized difference methods for differential equa-tions[M], Jilin University Press, 1994.
[26] Junliang Lv ,Yonghai Li , L2 error estimate of the finite volume element methods on quadri-lateral meshes[J], Advances in Computational Mathematics, 33: 129-148, 2010.
[27]李德元，水鸿寿，汤敏君，关于非矩形网格上的二维抛物型力程的差分格式，数值计算与计算机应／可，1(4)：217-224，1980
[28]李荣，祝巫琦，二阶椭圆偏微分力程的广义差分法[I]-i角网情形，高校计算数学学报，2：140-152，1982
[29]李荣华，祝巫琦，二阶椭圆偏微分力程的广义差分法[II]-四边形网情形，高校计算数学学报，4：360．375，1982
[30]S Ma and Y Saad，Distributed ILU(0)and SOR Preconditioners for Unstructured Sparse Linear Systems，Tech report 94-27，Army High Performance Computing Research Center，University ofMinnesota,Minneapolis，MN,1994
[31]Cunyun Nie，Shi Shu，Zhiqiang Sheng，Symmetry-preserving finite volume element scheme on unstructured quadrilateral grids[J]，Chinese Journal ofComputational Physics，26(2)：91-99，2009
[32]J W．Ruge，K Sfiiben，Algebraic multigrid，in Multigrid Methods，Frontiers"Appl~ath 3，S．~EMcCormick．editor,SIAM,Philadehia，73-130，1987
[33]D J Rose，R E Tarjan，and G S Lueker,Algorithmic aspects of vertex elimination on graphs，SLAM，Comput，266-283，5(1976)
[34]Yousef Saad，Iterative Methods for Sparse Linear Systems，Second edition with corrections，January 3rd，2000
[35]T Schmidt，Box schemes on quadrilateral meshes，Computing，51：271-292，1993
[36]K St~ben，Algebraic multigrid(AMG)：an introduction with applications，GMD Report No 70．1999．Also available as an appendix in n4“，#grid,U Trottenberg,C H~Oosterlee．A Schuller,Academic PMSS．413-532．2001
[37]s Shu，I Babuska，Y．X Xiao，J Xu and L Zikatanov,Multilevel preconditioning methods for discrete models ofla~ice block materials，SLAM，Sci Comput，31(1)：687-707，2008
[38]s Shu，D Sun，J．Xu，An Algebraic Multigrid Method for Higher-order Finite Element Dis- cretizations，Computing 77，347-377，2006
[39]Y Saad and M Schultz，GMRES：A generalized minimal residual algorithm for solv- ing nonsymmetric linear systems，SIAM Journal on Scienitific and Statistical Computing, 7(3)：856 869，1986
[40]Shi Shu，Haiyuan Yu，Yunqing Huang，Cunyun Nie，A preserving-symmetry finite volume scheme and superconvergence on quadrangle grids[J]，Numerical Analysis and Modeling，3(3)：348-360，2006
[41]Tian Mingzhong，Chen Zhongying，A generalized difference method for second order ellip- tic partial differential equations[J]，NumericalMathematics．"A Journal ofChinese Univer- sities，2：99-1 13，1991
[42]谭敏，肖映熊舒适，‘种各向异性四边形网格l、的代数多重网格法，湘潭大学自然科学学报，27(1)：78-84，2005
[43]u M Ulrike，Parallel algebraic multigrid methods-high performance precondi oners，in Nu- merical solution ofpa~iM differential equations on parallel computers(edited by A M Bru- aset&A Tveito)，209-236，Springer-Verlag，2006，Also available as LL TechnicalReport NO UCRL-BooK-208032
[44]EVanek，J Mandel，M Brezina，Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems，Computing,56：179-196，1996
[45]Wang Ping，Zhang Zhiyue，Finite volume element method in air pollution model[J]，Chinese Journal ofComputational Physics，26(5)：655-664，2009
[46]Yx Xiao，s Shu，EZhang，M Tan，An algebraic multigrid method for isotropic linear elas-ticity on anisotropic meshes，Commun Numer3deth Engng(2008)_Online in Inter-Science(www．interscience~iley．com)，DoI：lO 1002／cnm 1140
[47]J．Xu，L Zikatanov,On the energy minimizing base for algebraic multigrid methods，Com—pu#ng and Visualization in Science，7：121-127，2004
[48]Xu 5nchao，Zou Qingsong，Analysis oflinear and quadratic simplicial finite volume meth- ods for elliptic equations[J]，Numerische Mathematik,1 1 1(3)：469-492，2009
[49]Min Yang，Cubic finite volume methods for second order elliptic equations with variable coeficients，NortheasternMathematicalJourna 21(2)：146-152，2005
[50]I J_M Yang，Long-range interpolation for parallel algebraic multigrid，ICIAMG07 talk Zurich，July,2007
[51]L Zaslavsky,An adaptive algebraic m~tigrid fo reactor critically calculations，SIAM J．Sci Comp，16：840-847，1995
[52]周志阳，聂存云，舒适，‘种二阶混合有限体元格式的GAMG预条子，计算，己接收