资源描述:
《AN AGGREGATION-BASED ALGEBRAIC MULTIGRID METHOD》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、ANAGGREGATION-BASEDALGEBRAICMULTIGRIDMETHODYVANNOTAY∗Abstract.Analgebraicmultigridmethodispresentedtosolvelargesystemsoflinearequations.Thecoarsen-ingisobtainedbyaggregationoftheunknowns.Theaggregationschemeusestwopassesofapairwisematchingalgorithmapplie
2、dtothematrixgraph,resultinginmostcasesinadecreaseofthenumberofvariablesbyafactorslightlylessthanfour.Thematchingalgorithmfavorsthestrongestnegativecoupling(s),inducingaproblemdepen-dantcoarsening.Thisaggregationiscombinedwithpiecewiseconstant(unsmoothed)
3、prolongation,ensuringlowsetupcostandmemoryrequirements.Comparedwithpreviousaggregation-basedmultigridmethods,thescalabilityisenhancedbyusingaso-calledK-cyclemultigridscheme,providingKrylovsubspaceaccelerationateachlevel.Thispaperisthelogicalcontinuationo
4、f[SIAMJ.Sci.Comput.,30(2008),pp.1082–1103],wheretheanalysisofamodelanisotropicproblemshowsthataggregation-basedtwo-gridmethodsmayhaveoptimalorderconvergence,andof[Numer.Lin.Alg.Appl.,15(2008),pp.473–487],whereitisshownthatK-cyclemultigridmayprovideoptima
5、lornearoptimalconvergenceundermildassumptionsonthetwo-gridscheme.Whereasinthesepapersonlymodelproblemswithgeometricaggregationwereconsidered,hereatrulyalgebraicmethodispresentedandtestedonawiderangeofdiscretesecondorderscalarellipticPDEs,includingnonsymm
6、etricandunstructuredproblems.NumericalresultsindicatethattheproposedmethodmaybesignificantlymorerobustasblackboxsolverthantheclassicalAMGmethodasimplementedinthecodeAMG1R5byK.St¨uben.Theparallelimplementationisalsodiscussed.Satisfactoryspeedupsareobtained
7、onamediumsizemulti-processorclusterthatistypicaloftodaycom-putermarket.AcodeimplemantingthemethodisfreelyavailablefordownloadbothasaFortranprogramandaMatlabfunction.Keywords.multigrid,linearsystems,iterativemethods,AMG,preconditioning,parallelcomputingAM
8、Ssubjectclassifications.65F10,65N551.Introduction.Weconsidertheiterativesolutionoflargesparsen×nlinearsystems(1.1)Au=barisingfromthediscretizationofsecondorderellipticPDEs.Inthiscontext,multigridmeth-ods[39]areamongthemoste