Abstract. BDDC methods are nonoverlapping iterative substructuring domain decomposition methods for the solution of large sparse linear algebraic systems arising from discretization of elliptic boundary value problems. Its coarse problem is given by a smal
TR2005-862
THREE-LEVELBDDCINTHREEDIMENSIONS
XUEMINTU
Abstract.BDDCmethodsarenonoverlappingiterativesubstructuringdomaindecompositionmethodsforthesolutionoflargesparselinearalgebraicsystemsarisingfromdiscretizationofellipticboundaryvalueproblems.Itscoarseproblemisgivenbyasmallnumberofcontinuityconstraintswhichareenforcedacrosstheinterface.Thecoarseproblemmatrixisgeneratedandfactoredbydirectsolversatthebeginningofthecomputationanditcanultimatelybecomeabottleneck,ifthenumberofsubdomainsisverylarge.Inthispaper,twothree-levelBDDCmethodsareintroducedforsolvingthecoarseproblemapproximatelyinthreedimensions.Thisisanextensionofpreviousworkforthetwodimensionalcaseandsincevertexconstraintsalonedonotsu cetoobtainpolylogarithmicconditionnumberbound,edgeconstraintsareconsideredinthispaper.Somenewtechnicaltoolsarethenneededintheanalysisandthismakesthethreedimensionalcasemorecomplicatedthanthetwodimensionalcase.Estimatesoftheconditionnumbersareprovidedfortwothree-levelBDDCmethodsandnumericalexperimentsarealsodiscussed.
Keywords.BDDC,three-level,threedimensions,domaindecomposition,coarseproblem,conditionnumber,Chebysheviteration
AMSsubjectclassi cations.65N30,65N55
1.Introduction.BDDC(BalancingDomainDecompositionbyConstraints)methods,whichwereintroducedandanalyzedin[3,7,8],aresimilartothebalancingNeumann-Neumannalgorithms.However,thecoarseproblem,inaBDDCalgorithm,isgivenintermsofasetofprimalconstraintsandthematrixofthecoarseproblemisgeneratedandfactoredbyusingdirectsolversatthebeginningofthecomputation.Wenotethattherearenowcomputersystemswithmorethan100,000powerfulpro-cessors,whichallowverylargeanddetailedsimulations.Thecoarsecomponentofatwo-levelpreconditionercanthereforebeabottleneckifthenumberofsubdomainsisverylarge.Onewaytoremovethisdi cultyistointroduceoneormoreadditionallevels.Inourrecentpaper[11],twothree-levelBDDCmethodswereintroducedfortwodimensionalproblemswithvertexconstraints.Wesolvethecoarseproblemap-proximately,byusingtheBDDCidearecursively,whileagoodrateofconvergencestillcanbemaintained.However,inthreedimensionalspace,vertexconstraintsalonearenotenoughtoobtaingoodpolylogarithmicconditionnumberboundduetomuchweakerinterpolationestimateandconstraintsontheaveragesoveredgesorfacesareneeded.Thenewconstraintsleadtoaconsiderablymorecomplicatedcoarseproblemandtheneedfornewtechnicaltoolsintheanalysis.Inthispaper,weextendthetwothree-levelBDDCmethodsin[11]tothethreedimensionalcaseusingprimaledgeaverageconstraints.Withthehelpofthenewtechnicaltools,weprovideestimatesoftheconditionnumberboundsofthesystemwiththesetwonewpreconditioners.
Therestofthepaperisorganizedasfollows.We rstreviewthetwo-levelBDDCmethodsbrie yinSection2.Weintroduceour rstthree-levelBDDCmethodandthe
1inSection3.WegivesomeauxiliaryresultsinSec-correspondingpreconditionerM
tion4.InSection5,weprovideanestimateoftheconditionnumberboundforthesys- 2 1 temwiththepreconditionerMwhichisoftheformC1+logH,
h
,H,andharetypicaldiametersofthesubregions,subdomains,andelements,whereH
TR2005-862 THREE-LEVEL BDDC IN THREE DIMENSIONS XUEMIN TU? Abstract. BDDC methods are nonoverlapping iterative substructuring domain decomposition methods for...
TR856 Dept. CS, New York University, November 2004. Xuemin Tu. Three-level BDDC in three dimensions. TR862 Dept. CS, New York University, April ...
TR856 Dept. CS, New York University, November 2004. Xuemin Tu. Three-level BDDC in three dimensions. TR862 Dept. CS, New York University, April ...
热门文档