一类晶格材料（Lattice Materials）的无结构代数多重网格法
|
摘要
在本文中；我们在已有的以单个椭圆型方程线性元代数系统为背
景的无结构代数多重网格法的基础上，建立了一类应用范围更广、
稳定性更好的新的迭代校正型的无结构代数多重网格KMG）算法。
－针对一类晶格材料①attice maedall）的离散模型，将所构造的 AMG方
法用于子块矩阵求逆，我们得到了相应的基于V七yde方法和预条件
共轭梯度法＊CG）的块Gauss－S削el迭代；利用提升（插值）算子（矩阵）
扩充技术，将此AMG方法推广到方程组情形，我们得到了一类关于
晶格材料离散模型的AMG方法，即所谓的AMy和APCG方法。大
量的数值实验表明：当重要参数a刽0．1，1］时，对q＝1，3，4的晶格材料
离散模型，相应的AMV和AP CG方法的迭代次数基本上与a及同题
的规模无关；当a很小时，对ti习，3的情形，APCG方法的迭代次数
与问题的规模无关，且随。的减小变化不大。从而验证了该算法的
高效性和健壮性，反映了多重网格法在晶格材料大规模科学计算中
的优越性。进一步，通过对晶格材料离散模型的近似连续模型作深
入的理论分析，在q习的情形下，我们证明了以对角块矩阵的逆为
预条件子的PCG方法的条件数和参数。无关的结论，从而在理论上
证明了该数值实验结果的正确性。
In this pWer，we propose a new lteratlve correcting type ofunstructured alge－
braic皿ltipid（AMG）mthod which has。re extensl陀 annlicatlon nrosnects
and better stability on the background of＊theound existent AMG method for eL
liptic PDE．Applying the new AMG method to solve the Inverse ofsu卜bio ＆
matrix weget the corresponding bio出 Gauss－Seldel iteration based on V－Cycle
mthodmd preconditioned coqugate gradient（PCG）mthod for the discrete
mdels on Lattice materials．Using the operator mtrlx）矾tending tecncnolo欧
wegmerali沈 the AMG metbd to the case ofequatlon groups and欧t a tWe
。f AMG method called AMV nd APCG method aboutthe discrete modes of
lattice materials．A great un灿er ofexperlments show th时 when the imper－
tant paramter a E（0．l，l］the iteration number ofcorresponding AMV and
APCG method is on the whole Ind印endent of＊the scale ofquestlons and the
parameter a for thetatlce materlajs discrete modets with q＝l，3 azld 4，that
when a Is very small the iteration un咖er ofAPCG method Is independent
of＊the scale ofquestlons anddauges little s a becomes smaller In the case
ofq二1．3．TherefOrethehlghefficlenCyandrobustness oftheALIG algorithm
havebeen testd．Its superlorltyls shown In thelargesscale scientific compu－
tatlons about lattice materials二Moreoverby m冰ingfurther analysis forthe
approximately continuous models associated wlththe discrete models on fat－
tlce materials with q＝lwe haveproved the result that the condition number
of PCG method，whose preconditioner B Is chosen as the Inverse of the block
dlagonalmatrlx，Is Independent oftheparameter a．Accordingl。，we verify
the correctness of＊thetness corresponding numerical results In theory．
景的无结构代数多重网格法的基础上，建立了一类应用范围更广、
稳定性更好的新的迭代校正型的无结构代数多重网格KMG）算法。
－针对一类晶格材料①attice maedall）的离散模型，将所构造的 AMG方
法用于子块矩阵求逆，我们得到了相应的基于V七yde方法和预条件
共轭梯度法＊CG）的块Gauss－S削el迭代；利用提升（插值）算子（矩阵）
扩充技术，将此AMG方法推广到方程组情形，我们得到了一类关于
晶格材料离散模型的AMG方法，即所谓的AMy和APCG方法。大
量的数值实验表明：当重要参数a刽0．1，1］时，对q＝1，3，4的晶格材料
离散模型，相应的AMV和AP CG方法的迭代次数基本上与a及同题
的规模无关；当a很小时，对ti习，3的情形，APCG方法的迭代次数
与问题的规模无关，且随。的减小变化不大。从而验证了该算法的
高效性和健壮性，反映了多重网格法在晶格材料大规模科学计算中
的优越性。进一步，通过对晶格材料离散模型的近似连续模型作深
入的理论分析，在q习的情形下，我们证明了以对角块矩阵的逆为
预条件子的PCG方法的条件数和参数。无关的结论，从而在理论上
证明了该数值实验结果的正确性。
In this pWer，we propose a new lteratlve correcting type ofunstructured alge－
braic皿ltipid（AMG）mthod which has。re extensl陀 annlicatlon nrosnects
and better stability on the background of＊theound existent AMG method for eL
liptic PDE．Applying the new AMG method to solve the Inverse ofsu卜bio ＆
matrix weget the corresponding bio出 Gauss－Seldel iteration based on V－Cycle
mthodmd preconditioned coqugate gradient（PCG）mthod for the discrete
mdels on Lattice materials．Using the operator mtrlx）矾tending tecncnolo欧
wegmerali沈 the AMG metbd to the case ofequatlon groups and欧t a tWe
。f AMG method called AMV nd APCG method aboutthe discrete modes of
lattice materials．A great un灿er ofexperlments show th时 when the imper－
tant paramter a E（0．l，l］the iteration number ofcorresponding AMV and
APCG method is on the whole Ind印endent of＊the scale ofquestlons and the
parameter a for thetatlce materlajs discrete modets with q＝l，3 azld 4，that
when a Is very small the iteration un咖er ofAPCG method Is independent
of＊the scale ofquestlons anddauges little s a becomes smaller In the case
ofq二1．3．TherefOrethehlghefficlenCyandrobustness oftheALIG algorithm
havebeen testd．Its superlorltyls shown In thelargesscale scientific compu－
tatlons about lattice materials二Moreoverby m冰ingfurther analysis forthe
approximately continuous models associated wlththe discrete models on fat－
tlce materials with q＝lwe haveproved the result that the condition number
of PCG method，whose preconditioner B Is chosen as the Inverse of the block
dlagonalmatrlx，Is Independent oftheparameter a．Accordingl。，we verify
the correctness of＊thetness corresponding numerical results In theory．
引文
[1] 华云龙，余同希，多胞材料的力学行为，力学进展，Vol.21，No．4(1991)，pp．457-569．
[2] Jinchao Xu and Luamil Zikatanov. Lattice Materials, to appear.
[3] [美]S．铁摩辛柯，J．盖尔著，材料力学，科学出版社(1978)．
[4] J.W.Ruge.and. K.Stüben. Algebraic mutigrid, Mutigrid methods[M],SIAM,1987.
[5] Lorna J.Gibson and Michael F.Ashby, Cellular Solids Structure and properties,Cambridge University Press,1997.
[6] T.F.Chan, J.Xu,and L.Zikatanov,An agglomeration multigrid method for unstructured grids. Proceedings of 10-th International conference on Domain Decomposition methods,edit by J.Mandel,C.Farhat,and X.J.Cai, AMS, Providence, RI, to appear.
[7] S.A.Sauter,Mathematical description of periodic trusses,Private communication.
[8] J.Mandel, M.Brezina, P.Vaněk,Energy optimization of algebraic multigrid bases. Computing, to appear.
[9] J.H.Bramble, J.E.Pasciak,and J.Xu, Convergence estimates for multigrid algorithms without regularity assumptions,Math. Comp.,57,pp.23-45, 1991.
[10] T.F.Chan, B.F.Smith,and W.L.Wan,An energy-minimizing interpolation for multigrid methods. Presentation at the 10th International Conference on Domain Decomposition,Boulder,CO,August 1997.
[11] P.Vanēk,J.Mandel,and M.Brezina,Algebraic multigrid on unstructured meshes, UCD/CCM Report 34,Center for Computational Mathematics,University of Colorado at Denver,December 1994.
[12] W.L.Wan,An energy-minimizing interpolation for multigrid methods, UCLA CAM Report 97-18,Department of mathematics,UCLA,April 1997.
[13] J.Mandel,S.McCormick and J.Ruge,.An agebraic theory for multigrid methods for variational problems,SIAM. J.Numer.Anal.,25(1988) ,pp.91-110．
[14] Jinchao Xu and Ludmil Zikatanov,An investigation on some lattice material models,Private communication.
[15] Jinchao Xu,Iterative methods by space decomposition and subspace correction, SIAM Rev.,34(1992) ,pp.581-613．
[16] Jinchao Xu,Jun Zou,Some nonoverlapping domain decomposition methods,SIAM. Rev.,Vol.40,No.4,pp.581-613,December 1998．
[17] Q.S.Chang,Y.S.wong and H.Fu,On the Algebraic Multigrid Methods [J], J. Comput. Phys.,125(1996) ,pp.279-292．
[18] R.H.chan,Q .S .Chang,Y.S .wong and H.W .Sun,Multigrid Method for ill-conditioned Symmetric Toeplitz[J],SIAM J.Sci.Comput.,1998,19(2) ,pp.516-529．
[19] Q.S.Chang,S.Q.Ma and G.Y.Lei,Algebraic Multigrid for Queuing Networks[J],Inter. J.of Computer Math.,70(1999) ,pp.539-552．
[20] J.Mandel, M.Brezina, P.Vsnek.,Energy optimization of algebraic multigrid bases. Computing, to appear.
[21] T.Y.Hou, X.H.Wu,and Z.Q.Cai, Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficents.Submitted to Math.Comp..
[22] J.E.Jones ,and P. S. Vassilevski,AMGE based on element agglomeration, to appear.
[23] J.H.Bramble, J.E.Pasciak,and J. Xu, Convergence estimates for multigrid algo-rithms without regularity assumptions,Math.Comp.,57 ,pp.23-45, 1991．
[24] T.Chan,B.Smith,Domain decomposition and multigrid algorithms for eliptic problems unstructured meshes,Electronic Transactions in Numerical Analysis,2,pp.171-182,1994．
[25] P.Vanek,J.Mandel,and M.Brezina,Algebraic multigrid on unstructured meshes, UCD/CCM Report 34,Center for Computational Mathematics ,Univer-sity of Colorado at Denver,December 1994．
[26] 徐树方，矩阵计算的理论和方法，北京大学初版社，1995．
[27] W.L.Wan,T.F.Chan,and B.Smith,An energy-minimizing interpolation for ro-bust multigrid methods,UCLA CAM Report 98-6,Department of Mathematics, UCLA, February 1998．
[28] R.Bank,and J.Xu,An algorithm for coarsing unstructured meshes, Numer. Math., 73,No.1,pp.1-36, 1996．
[29] W. Hackbusch,Multigrid methods and applications,vol.4 of Computational Mathematics, Spring-Verlag, Berlin, 1985．
[30] A..Brandt,Algebraic multigrid theory: The sysmmetric case,Appl. Math.. Com-puting.,19, pp.23-56, 1986．
[31] D.Braess, Towards algebraic multigrid for elliptic problems of second order, Com-puting, 55, pp.379-393, 1995．
[32] P.Vanek, M.Brezina, and R.Tezaur,Two-grid method for linear elasticity on un-structured meshes, to appear in SIAM J.Sci.Comp.,1998．
[33] P.Vanek, J.Mandel,and M.Brezina,Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, pp.179-196, 1996．
[34] J. Bramble, Multigrid methods, Pitman, Notes on Mathematics, 1994．
[35] P.Vanek, M.Brezina, and J.Mandel, Convergence of algebraic multigrid based on smoothed aggregation, UCD/CCM Report 126, February 1998．
[36] P.Vanek, J.Mandel,and M.Brezina,Algebraic multi-grid by smoothed aggregation for second and forth orer elloptic problems, Computing, 56,pp.179-196, 1996．
[2] Jinchao Xu and Luamil Zikatanov. Lattice Materials, to appear.
[3] [美]S．铁摩辛柯，J．盖尔著，材料力学，科学出版社(1978)．
[4] J.W.Ruge.and. K.Stüben. Algebraic mutigrid, Mutigrid methods[M],SIAM,1987.
[5] Lorna J.Gibson and Michael F.Ashby, Cellular Solids Structure and properties,Cambridge University Press,1997.
[6] T.F.Chan, J.Xu,and L.Zikatanov,An agglomeration multigrid method for unstructured grids. Proceedings of 10-th International conference on Domain Decomposition methods,edit by J.Mandel,C.Farhat,and X.J.Cai, AMS, Providence, RI, to appear.
[7] S.A.Sauter,Mathematical description of periodic trusses,Private communication.
[8] J.Mandel, M.Brezina, P.Vaněk,Energy optimization of algebraic multigrid bases. Computing, to appear.
[9] J.H.Bramble, J.E.Pasciak,and J.Xu, Convergence estimates for multigrid algorithms without regularity assumptions,Math. Comp.,57,pp.23-45, 1991.
[10] T.F.Chan, B.F.Smith,and W.L.Wan,An energy-minimizing interpolation for multigrid methods. Presentation at the 10th International Conference on Domain Decomposition,Boulder,CO,August 1997.
[11] P.Vanēk,J.Mandel,and M.Brezina,Algebraic multigrid on unstructured meshes, UCD/CCM Report 34,Center for Computational Mathematics,University of Colorado at Denver,December 1994.
[12] W.L.Wan,An energy-minimizing interpolation for multigrid methods, UCLA CAM Report 97-18,Department of mathematics,UCLA,April 1997.
[13] J.Mandel,S.McCormick and J.Ruge,.An agebraic theory for multigrid methods for variational problems,SIAM. J.Numer.Anal.,25(1988) ,pp.91-110．
[14] Jinchao Xu and Ludmil Zikatanov,An investigation on some lattice material models,Private communication.
[15] Jinchao Xu,Iterative methods by space decomposition and subspace correction, SIAM Rev.,34(1992) ,pp.581-613．
[16] Jinchao Xu,Jun Zou,Some nonoverlapping domain decomposition methods,SIAM. Rev.,Vol.40,No.4,pp.581-613,December 1998．
[17] Q.S.Chang,Y.S.wong and H.Fu,On the Algebraic Multigrid Methods [J], J. Comput. Phys.,125(1996) ,pp.279-292．
[18] R.H.chan,Q .S .Chang,Y.S .wong and H.W .Sun,Multigrid Method for ill-conditioned Symmetric Toeplitz[J],SIAM J.Sci.Comput.,1998,19(2) ,pp.516-529．
[19] Q.S.Chang,S.Q.Ma and G.Y.Lei,Algebraic Multigrid for Queuing Networks[J],Inter. J.of Computer Math.,70(1999) ,pp.539-552．
[20] J.Mandel, M.Brezina, P.Vsnek.,Energy optimization of algebraic multigrid bases. Computing, to appear.
[21] T.Y.Hou, X.H.Wu,and Z.Q.Cai, Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficents.Submitted to Math.Comp..
[22] J.E.Jones ,and P. S. Vassilevski,AMGE based on element agglomeration, to appear.
[23] J.H.Bramble, J.E.Pasciak,and J. Xu, Convergence estimates for multigrid algo-rithms without regularity assumptions,Math.Comp.,57 ,pp.23-45, 1991．
[24] T.Chan,B.Smith,Domain decomposition and multigrid algorithms for eliptic problems unstructured meshes,Electronic Transactions in Numerical Analysis,2,pp.171-182,1994．
[25] P.Vanek,J.Mandel,and M.Brezina,Algebraic multigrid on unstructured meshes, UCD/CCM Report 34,Center for Computational Mathematics ,Univer-sity of Colorado at Denver,December 1994．
[26] 徐树方，矩阵计算的理论和方法，北京大学初版社，1995．
[27] W.L.Wan,T.F.Chan,and B.Smith,An energy-minimizing interpolation for ro-bust multigrid methods,UCLA CAM Report 98-6,Department of Mathematics, UCLA, February 1998．
[28] R.Bank,and J.Xu,An algorithm for coarsing unstructured meshes, Numer. Math., 73,No.1,pp.1-36, 1996．
[29] W. Hackbusch,Multigrid methods and applications,vol.4 of Computational Mathematics, Spring-Verlag, Berlin, 1985．
[30] A..Brandt,Algebraic multigrid theory: The sysmmetric case,Appl. Math.. Com-puting.,19, pp.23-56, 1986．
[31] D.Braess, Towards algebraic multigrid for elliptic problems of second order, Com-puting, 55, pp.379-393, 1995．
[32] P.Vanek, M.Brezina, and R.Tezaur,Two-grid method for linear elasticity on un-structured meshes, to appear in SIAM J.Sci.Comp.,1998．
[33] P.Vanek, J.Mandel,and M.Brezina,Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, pp.179-196, 1996．
[34] J. Bramble, Multigrid methods, Pitman, Notes on Mathematics, 1994．
[35] P.Vanek, M.Brezina, and J.Mandel, Convergence of algebraic multigrid based on smoothed aggregation, UCD/CCM Report 126, February 1998．
[36] P.Vanek, J.Mandel,and M.Brezina,Algebraic multi-grid by smoothed aggregation for second and forth orer elloptic problems, Computing, 56,pp.179-196, 1996．