一种求解三维弹性问题有限元方程的并行DDM预条件子
|
摘要
弹性力学问题有着广泛的实际应用背景,有限元方法是求解此类问题最常用的离散化方法之一,由于该有限元离散系统系数矩阵的条件数强依赖于网格规模,因此设计其相应的快速算法非常必要.
本文针对三维线弹性问题线性有限元离散系统,将非重叠区域分解法(DDM)和代数多层网格(AMG)法相结合,首先为其设计了一种基于简单粗空间的并行非重叠DDM预条件子,它本质性地将原线性代数系统的预条件子构造问题转化为三类子系统的求解问题.接着,根据三类子系统的特性,分别为其设计了相应的快速算法.特别地,通过改变经典AMG法(C-AMG)中的粗化策略和提升算子的构造方法,为第三类子系统设计了一种新的AMG(简记为AMG-T)法.数值实验结果表明,当子系统规模足够大时,AMG-T法比C-AMG法无论在迭代次数还是在CPU时间方面都有优势.由此获得了一种求解三维线弹性问题线性元离散系统的新的预条件子Bamgddm,通过合理的并行数据结构设计,实现了关于Bamgddm并行程序模块.数值实验结果表明,基于该预条件子Bamgddm的并行PCG算法是高效和健壮的,且具有良好的算法可扩展性和并行可扩展性.
Elasticity problem has wide applications in many fields, and Finite element method is one of the most commonly used methods for solving it. However, the condition number of stiffness matrix strongly depends on mesh size, which leads to great necessity to study the corresponding fast algorithms.
In this paper, we first propose a new preconditioner for the linear finite element discrete system of 3D elastic problem by combining DDM and AMG. It is constructed based on simple coarse spaces and only needs to solve three classes of subsystems. Then corresponding fast algorithms are discussed respectively according to their specific characteristics. In particular, a so-called AMG-T solver is designed for the third class of subsystems by modifying the coarsening and interpolation strategies in the classical AMG(C-AMG). When the size of the subsystem is sufficiently large, experimental results show that AMG-T is better than C-AMG and CG both in the number of iteration and computing time. We also accomplish the parallel implement of the new preconditioner by using proper data structure. Numerical results show that PCG based on our new preconditioner is robust and efficient, and that it also has good scalability.
本文针对三维线弹性问题线性有限元离散系统,将非重叠区域分解法(DDM)和代数多层网格(AMG)法相结合,首先为其设计了一种基于简单粗空间的并行非重叠DDM预条件子,它本质性地将原线性代数系统的预条件子构造问题转化为三类子系统的求解问题.接着,根据三类子系统的特性,分别为其设计了相应的快速算法.特别地,通过改变经典AMG法(C-AMG)中的粗化策略和提升算子的构造方法,为第三类子系统设计了一种新的AMG(简记为AMG-T)法.数值实验结果表明,当子系统规模足够大时,AMG-T法比C-AMG法无论在迭代次数还是在CPU时间方面都有优势.由此获得了一种求解三维线弹性问题线性元离散系统的新的预条件子Bamgddm,通过合理的并行数据结构设计,实现了关于Bamgddm并行程序模块.数值实验结果表明,基于该预条件子Bamgddm的并行PCG算法是高效和健壮的,且具有良好的算法可扩展性和并行可扩展性.
Elasticity problem has wide applications in many fields, and Finite element method is one of the most commonly used methods for solving it. However, the condition number of stiffness matrix strongly depends on mesh size, which leads to great necessity to study the corresponding fast algorithms.
In this paper, we first propose a new preconditioner for the linear finite element discrete system of 3D elastic problem by combining DDM and AMG. It is constructed based on simple coarse spaces and only needs to solve three classes of subsystems. Then corresponding fast algorithms are discussed respectively according to their specific characteristics. In particular, a so-called AMG-T solver is designed for the third class of subsystems by modifying the coarsening and interpolation strategies in the classical AMG(C-AMG). When the size of the subsystem is sufficiently large, experimental results show that AMG-T is better than C-AMG and CG both in the number of iteration and computing time. We also accomplish the parallel implement of the new preconditioner by using proper data structure. Numerical results show that PCG based on our new preconditioner is robust and efficient, and that it also has good scalability.
引文
[1]A. Brandt. Algebraic Multigrid theory:the symmetric case, App. Math. Comp. 19:23-25,1986.
[2]A. Brandt. General highly accurate algebraic coarsening, ETNA,10:1-20,2000.
[3]A. Brandt, S. McCormick and J. Ruge. Algebraic multigrid (AMG) for auto-matic multigrid solution with application to geodetic computations. Institute for Computational Studies, POB 1852, Fort Collins, Colorado,1982.
[4]M. Brezina, A. J. Cleary, R. D. Falgout, V. E. Henson, J. E. Jones, T. A. Manteuffel, S. F. McCormick and J. W. Ruge. Algebraic multigrid based on element interpolation(AMGe). SIAM J. Sci. Comput.,22:1570-1592,2000.
[5]M. Brezina, R. D. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick and J. Ruge. Addaptive smoothed aggregation(aSA). SIAM Review,47(2):317-346, 2005.
[6]J. Bramble, J. Pasciak and A. Schatz. The construction of preconditioners for elliptic problems by substructuring. I. Math. Comp.,47:103-134,1986.
[7]J. Bramble, J. Pasciak and A. Vassilev. Analysis of non-overlapping domain decomposition algorithms with inexact solvers. Math. Comput.,67:1-19,1998.
[8]T. Chartier, R. D. Falgout, V. E. Henson, J. E. Jones, T. Maneuffel, S. F. McCormick, J. W. Ruge and P. S. Vassilevski. Spectral AMGe (pAMGe). SIAM J. Sci. Comp.,20(1):1-20,2003.
[9]T. F. Chan, L. Zikatanov and J. Xu. An agglomeration multigrid method for unstructured grids. Proceedings of the 10th International Conference on DD Methods, Contemporary Mathematics,218:67-81, SIAM,1998.
[10]程常韵,朱媛媛.弹性力学.上海大学出版社,2005年9月.
[11]Q. Chang, Y. Wong, and H. Fu. On the algebraic multigrid method. J. Comput. Phys.,125(2):279-292,1996.
[12]M. Dryja, F. Smith, and O. Widlund. Schwarz analysis of iterative substruc-turing algorithms for elliptic problems in three dimensions. SIAM J. Numer. Anal.,31(6):1662-1694,1994.
[13]M. Dryja and O. Widlund. Schwarz methods of neumann type for three-dimensional elliptic finite element problems. Comm. Pure Appl. Math.,48:121-155,1995.
[14]R. D. Falgout. An introduction to algebraic multigrid. Computing in Science and Engineering, special issue on multigrid computing,8:24-33,2006. Also appear in LLNL report NO. UCRL-JRNL-220851,2006.
[15]C. Farhat, J. Mandel, and F. Roux. Optimal convergence properties of the feti domain decomposition method. Comput. Methods. Appl. Mech. Enarq., 115:367-388,1994.
[16]C. Greif and D. Schotzau. Preconditioners for the discretized time-harmonic maxwell equations in mixed form. Numer. Linear Algebra Appl.,73(245):35-61, 2003.
[17]Q. Y. Hu, S.Shu and J. X. Wang. Nonoverlapping Domain Decomposition Meth-ods with a Simple Coarse Space for Elliptic Problems. Mathematics of Compu-tation, Accepted.
[18]Y. Q. Huang, S. Shu and X. J. Yu. Preconditioning higher order finite element systems by algebraic multigrid method of linear elements. J. Comp. Math., 24(2006),5:657-664.
[19]Q. Hu, Z. Shi, and D. Yu. Efficient solvers for saddle-point problems arising from domain decompositions with lagrange multipliers. SIAM J. Numer. Anal., 42(3):905-933,2004.
[20]V. E. Henson, U. M. Yang. BoomerAMG:a parallel algebraic multigrid solver and preconditioner. Applied Numerical Mathematics,41:155-177.2002. [21] R. D. Falgout, A. Baker, E. Chow, VE Henson, E. Hill, J. Jones, T. Kolev, B. Lee, J. Painter, C. Tong, and others. HYPRE:High performance preconditioner. https://computation.llnl.gov/casc/hypre/software.html
[221 J. E. Jones, P. S. Vassilevski, AMGe based on agglomeration, SIAM J. Sci. Comp.23:109-133,2001.
[23]A. Klawonn, O. B. Widlund, and M. Dryja. Dual-primal feti methods for three-dimensional elliptic problems with heterogeneous coefficients. SIAM J. Numer. Anal.,40(1):159-179,2002.
[24]刘春梅.求解平面弹性问题的自适应有限元法及多层网格法.
[25]龙驭球.有限元法概论.人民教育出版社,1978.
[26]罗振东.混合有限元法基本理论及应用[M].山东教育出版社.1996.
[27]J. Mandel, M. Brezina and P.Vanek. Energy optimization of algebraic multigrid bases. Computing 62(3),205-228,1999.
[28]J. W. Ruge, K. Stiiben. Algebraic multigrid, in Multigrid Methods. Frontiers Appl.Math.3, S.F.McCormick.editor, SIAM, Philadelphia,73-130,1987.
[29]S. Shu, I. Babuska, Y. X. Xiao, J. Xu and L. Zikatanov. Multilevel precon-ditioning methods for discrete models of lattice block materials. SIAM J. Sci. Comput.31(1),2008:687-707.
[30]H. D. Sterck, R. D. Falgout, J. Nolting, etc. Distance-two interpolation for parallel algebraic multigrid. SciDAC07 report, Boston USA, June,2007.
[31]舒适,黄云清,阳莺,蔚喜军.一类三维等代数结构面网格剖分下的代数多重网格法.计算物理,22(6)：480-488,2005.
[32]H. D. Sterck, U. M. Yang and J. J. Heys. Reducing complextity in parallel algebraic multigrid preconditioners. SIAM J.Mat.Anal.& Appl.27(4):1019-1039, 2006.
[33]B. Smith. A domain decomposition algorithm for elliptic problems in three dimensions. Numer. Math.,60:219-234,1991.
[34]黄云清,舒适,陈艳萍,金继承,文立平.数值计算方法.科学出版社,2009年1月.
[35]U. M. Ulrike. Parallel algebraic multigrid methods-high performance precon-ditioners, in Numerical solution of partial differential equations on parallel computers (edited by A.M. Bruaset& A.Tveito),209-236, Springer-Verlag,2006. Also available as LLNL Technical Report No.UCRL-BOOK-208032.
[36]P.Vanek, J. Mandel and M. Brezina. Algebraic multigrid by smoothed aggre-gation for second and fourth order elliptic problems. Computing,56:179-196, 1996.
[37]王敏中,王炜,武际可.弹性力学教程.北京大学出版社,2002年8月.
[38]徐小文,可扩展并行代数多重网格算法研究,博士学位论文,北京：北京应用物理与计算数学研究所,2006.
[39]徐小文,莫则尧.一种新的并行代数多重网格粗化算法.计算数学.27(3)：325-336,2005.
[40]J. Xu and J. Zou. Some nonoverlapping domain decomposition methods. SIAM Review,24:857-914,1998.
[41]J. Xu, L. Zikatanov. On the energy minimizing base for algebraic multigrid methods. Computing and Visualization in Science,7:121-127,2004.
[42]肖映雄,张平,舒适等,一种计算复合材料等效弹性性能的有限元方法,固体力学学报,27(1)：77-82,2006.
[43]U. M. Yang. Long-range interpolation for parallel algebraic multigrid. ICI-AMG07 talk, Zurich, July,2007.
[2]A. Brandt. General highly accurate algebraic coarsening, ETNA,10:1-20,2000.
[3]A. Brandt, S. McCormick and J. Ruge. Algebraic multigrid (AMG) for auto-matic multigrid solution with application to geodetic computations. Institute for Computational Studies, POB 1852, Fort Collins, Colorado,1982.
[4]M. Brezina, A. J. Cleary, R. D. Falgout, V. E. Henson, J. E. Jones, T. A. Manteuffel, S. F. McCormick and J. W. Ruge. Algebraic multigrid based on element interpolation(AMGe). SIAM J. Sci. Comput.,22:1570-1592,2000.
[5]M. Brezina, R. D. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick and J. Ruge. Addaptive smoothed aggregation(aSA). SIAM Review,47(2):317-346, 2005.
[6]J. Bramble, J. Pasciak and A. Schatz. The construction of preconditioners for elliptic problems by substructuring. I. Math. Comp.,47:103-134,1986.
[7]J. Bramble, J. Pasciak and A. Vassilev. Analysis of non-overlapping domain decomposition algorithms with inexact solvers. Math. Comput.,67:1-19,1998.
[8]T. Chartier, R. D. Falgout, V. E. Henson, J. E. Jones, T. Maneuffel, S. F. McCormick, J. W. Ruge and P. S. Vassilevski. Spectral AMGe (pAMGe). SIAM J. Sci. Comp.,20(1):1-20,2003.
[9]T. F. Chan, L. Zikatanov and J. Xu. An agglomeration multigrid method for unstructured grids. Proceedings of the 10th International Conference on DD Methods, Contemporary Mathematics,218:67-81, SIAM,1998.
[10]程常韵,朱媛媛.弹性力学.上海大学出版社,2005年9月.
[11]Q. Chang, Y. Wong, and H. Fu. On the algebraic multigrid method. J. Comput. Phys.,125(2):279-292,1996.
[12]M. Dryja, F. Smith, and O. Widlund. Schwarz analysis of iterative substruc-turing algorithms for elliptic problems in three dimensions. SIAM J. Numer. Anal.,31(6):1662-1694,1994.
[13]M. Dryja and O. Widlund. Schwarz methods of neumann type for three-dimensional elliptic finite element problems. Comm. Pure Appl. Math.,48:121-155,1995.
[14]R. D. Falgout. An introduction to algebraic multigrid. Computing in Science and Engineering, special issue on multigrid computing,8:24-33,2006. Also appear in LLNL report NO. UCRL-JRNL-220851,2006.
[15]C. Farhat, J. Mandel, and F. Roux. Optimal convergence properties of the feti domain decomposition method. Comput. Methods. Appl. Mech. Enarq., 115:367-388,1994.
[16]C. Greif and D. Schotzau. Preconditioners for the discretized time-harmonic maxwell equations in mixed form. Numer. Linear Algebra Appl.,73(245):35-61, 2003.
[17]Q. Y. Hu, S.Shu and J. X. Wang. Nonoverlapping Domain Decomposition Meth-ods with a Simple Coarse Space for Elliptic Problems. Mathematics of Compu-tation, Accepted.
[18]Y. Q. Huang, S. Shu and X. J. Yu. Preconditioning higher order finite element systems by algebraic multigrid method of linear elements. J. Comp. Math., 24(2006),5:657-664.
[19]Q. Hu, Z. Shi, and D. Yu. Efficient solvers for saddle-point problems arising from domain decompositions with lagrange multipliers. SIAM J. Numer. Anal., 42(3):905-933,2004.
[20]V. E. Henson, U. M. Yang. BoomerAMG:a parallel algebraic multigrid solver and preconditioner. Applied Numerical Mathematics,41:155-177.2002. [21] R. D. Falgout, A. Baker, E. Chow, VE Henson, E. Hill, J. Jones, T. Kolev, B. Lee, J. Painter, C. Tong, and others. HYPRE:High performance preconditioner. https://computation.llnl.gov/casc/hypre/software.html
[221 J. E. Jones, P. S. Vassilevski, AMGe based on agglomeration, SIAM J. Sci. Comp.23:109-133,2001.
[23]A. Klawonn, O. B. Widlund, and M. Dryja. Dual-primal feti methods for three-dimensional elliptic problems with heterogeneous coefficients. SIAM J. Numer. Anal.,40(1):159-179,2002.
[24]刘春梅.求解平面弹性问题的自适应有限元法及多层网格法.
[25]龙驭球.有限元法概论.人民教育出版社,1978.
[26]罗振东.混合有限元法基本理论及应用[M].山东教育出版社.1996.
[27]J. Mandel, M. Brezina and P.Vanek. Energy optimization of algebraic multigrid bases. Computing 62(3),205-228,1999.
[28]J. W. Ruge, K. Stiiben. Algebraic multigrid, in Multigrid Methods. Frontiers Appl.Math.3, S.F.McCormick.editor, SIAM, Philadelphia,73-130,1987.
[29]S. Shu, I. Babuska, Y. X. Xiao, J. Xu and L. Zikatanov. Multilevel precon-ditioning methods for discrete models of lattice block materials. SIAM J. Sci. Comput.31(1),2008:687-707.
[30]H. D. Sterck, R. D. Falgout, J. Nolting, etc. Distance-two interpolation for parallel algebraic multigrid. SciDAC07 report, Boston USA, June,2007.
[31]舒适,黄云清,阳莺,蔚喜军.一类三维等代数结构面网格剖分下的代数多重网格法.计算物理,22(6)：480-488,2005.
[32]H. D. Sterck, U. M. Yang and J. J. Heys. Reducing complextity in parallel algebraic multigrid preconditioners. SIAM J.Mat.Anal.& Appl.27(4):1019-1039, 2006.
[33]B. Smith. A domain decomposition algorithm for elliptic problems in three dimensions. Numer. Math.,60:219-234,1991.
[34]黄云清,舒适,陈艳萍,金继承,文立平.数值计算方法.科学出版社,2009年1月.
[35]U. M. Ulrike. Parallel algebraic multigrid methods-high performance precon-ditioners, in Numerical solution of partial differential equations on parallel computers (edited by A.M. Bruaset& A.Tveito),209-236, Springer-Verlag,2006. Also available as LLNL Technical Report No.UCRL-BOOK-208032.
[36]P.Vanek, J. Mandel and M. Brezina. Algebraic multigrid by smoothed aggre-gation for second and fourth order elliptic problems. Computing,56:179-196, 1996.
[37]王敏中,王炜,武际可.弹性力学教程.北京大学出版社,2002年8月.
[38]徐小文,可扩展并行代数多重网格算法研究,博士学位论文,北京：北京应用物理与计算数学研究所,2006.
[39]徐小文,莫则尧.一种新的并行代数多重网格粗化算法.计算数学.27(3)：325-336,2005.
[40]J. Xu and J. Zou. Some nonoverlapping domain decomposition methods. SIAM Review,24:857-914,1998.
[41]J. Xu, L. Zikatanov. On the energy minimizing base for algebraic multigrid methods. Computing and Visualization in Science,7:121-127,2004.
[42]肖映雄,张平,舒适等,一种计算复合材料等效弹性性能的有限元方法,固体力学学报,27(1)：77-82,2006.
[43]U. M. Yang. Long-range interpolation for parallel algebraic multigrid. ICI-AMG07 talk, Zurich, July,2007.