Preprocessing for 2D FE-BE domain decomposition me

Preprocessingfor2DFE{BEDomainDecompositionMethodsG.HaaseM.KuhnInstituteofAnalysisandComputationalMathematicsJohannesKeplerUniversityLinz,AltenbergerStr.69A-4040Linz,Austria.([e-mail],[e-mail])AbstractThenon-overlappingDomainDecomposition(DD)methodisapowerfultoolforthecouplingofFiniteElement(FE)andBoundaryElement(BE)methods.Moreoveritprovidesanaturalbasisforconstructingecientparallelsolvers.However,both,theeciencyandtherobustnessofDD{solversdependsheavilyontheunderlyingdecompositionofthedomainofinterestintosubdomains.Inthispaper,weintroducetheAdaptiveDomainDecompositionPreprocessorADDPrewhichrealizesanautomaticdecompositionofthecomputationaldo-mainintopsubdomains,wherepisthenumberofprocessorstobeused.Wediscussthecodesbeinginvolved,thealgorithmswhichtheyarebasedonandthedata{formatsbeingusedfordescribingthedecompositionoftheproblem.Numericalexamples,demonstratingtheperformanceofthepreprocessorarepresented.Keywords:DomainDecompositionMethods,Preprocessing,ParallelSolversforPartialDierentialEquations,CouplingofFEMandBEM.AMSsubjectclassications:65N55,65N22,65F10,65N30,65N38,65Y10,65Y05,05C90.1IntroductionNowadays,DomainDecomposition(DD)andrelatedalgorithmsareofgreatinterest,sincetheyarethebasictoolforconstructingalgorithmswhicharewellsuitedtorunonMultipleInstructionMultipleData(MIMD)parallelcomputers,includingclustersofworkstations,withmessage-passing.TheseparallelmachinesprovidesucientCPUpowerandsucientlylargestoragecapacityasitisnecessaryforthenumericalsimulationofcomplexprocesses.Anotherimportantaspectisthatnon-overlappingAcknowledgments:ThisworkhasbeensupportedbytheAustrianScienceFund{’FondszurForderungderwissenschaftlichenForschung’{withintheSFBF013NumericalandSymbolicScienticComputing.1DDmethodsallowustomarrytheadvantagesoftheFiniteElementMethod(FEM)tothoseoftheBoundaryElementMethod(BEM)viaauniedcoupledvariationalformulation,see[6,14]andthereferencestherein.Therefore,ecientparallelsolversforlargesystemsofalgebraicequationsresultingfrom,e.g.,theniteelement(FE),theboundaryelement(BE),oracoupledFE/BEdiscretizationofthepartialdierentialequation,havebeendeveloped[6,14,15].Toachievetheinherenthighparalleleciencyofthesolversitisnecessarytodistributetheworktothepprocessorsoftheparallelcomputerwithagoodloadbalance.Thelattermeansthatthetotalwaitingtime,i.e.,thesumoverallprocessorsofthetimethataprocessorhastowaitidlefortheothers,shouldbesmall.Asanexample,intheFEM-DDforlinearellipticproblems,almostequalnumbersofnodes,elements,andcouplingboundariesshouldbeassignedtoeachprocessor.However,forDDmethodswhichwehaveinmindasimple(evenloadbalanced)distributionofthemeshisnotsucient.Insteadawellshapeddecompositionofthecomputationaldomainintosubdomainsisrequired.ForthispurposewehavedevelopedthepreprocessingtoolADDPre(AdaptiveDomainDecompositionPreprocessor)whichisgoingtobediscussedinthispaper.Inarststage,thetoolrequiressomealgorithmfordistributingmeshes.Sev-eralsuchalgorithmshavebeendescribedintheliterature.EventoolsasChaco[8],TOP/DOMDEC[3],Jostle[19],Metis[10]areavailable.Furthermore,thetoolEx-adasy[11]providesageneraluserinterfaceallowingtheapplicationandcomparisonofseveralsuchtoolsformeshpartitioning.Here,werestrictourconsiderationstothetherecursivespectralbisectionmethod(rsb)[2,17]whichallowstopartitionmeshesrepresentedbytheirgraphs.Wewillapplyageneralizedversionthatallowsustodecomposeanaturallygiven(bythematerialcoecients)initialdecomposi-tionconsistingofPmatsubregionsofdierentsizeintoanarbitrarynumberpofnalwell-balancedsubdomains.First,wedeterminethenumberofsubdomainsinwhicheachsubregionistobedecomposed(itneedsnottobeapowerof2),thenweapplythemodiedrsbtoeachsubregion.Further,complicatedcouplingboundariesbetweenthesubdomainscanreducetheeciencyoftheDDbasedsolversmentionedabove.Thus,itisdesirabletosmooththecouplingboundariesthatseparatesubdomainsinsideasubregion.Roughlyspeaking,welookforwellshapedsubdomains.ThisgoalistreatedinasecondstageofADDPre.Hereby,thecouplingboundariesthatseparatesubregionswithdierentcoecientsremainunchangedasinthestandardDDmethods.Asathirdaspect,adaptiverenementstrategiescanleadtoload-imbalanceonthenegrids.Therefore,weprovidethepossibilitytogenerateana-priorirenedmeshinthepreprocessing.Ifthismeshisusedasaninputforthespectralbisectionmethod,therewillbeaquasi-staticloadbalanceonthenegrids.Inthispaper,weconsiderapotentialproblemarising,e.g.,frommagnetostatics,asatestproblem.Itreadsformallyasfollowsdiv((x)ru(x))=S(x)+@H0y(x)@x@H0x(x)@y;x2(1)u(x)=0;x2D:=@:(2)Here,isaboundeddomain,anddenotesapiecewiseconstantcoecientfunction2whichdenesana-prioridecompositionofthedomainby=Pmat[j=1^j;with^i\^j=;8i6=j;and(x)=jforx2^j:(3)Forthephysicalmodel,andforH0xandH0ywhichstandforsourcesassociatedwithpermanentmagnets,wereferto[14].Therestofthepaperisorganizedasfollows.InSection2,wedescribethecontinuousproblemtogetherwiththeobjectivesofouralgorithms.Aswewillsee,theproblemsplitsbasicallyintotwosubtasks,thepartitioningofmeshes,whichisdiscussedinSe