Multilevel Mesh Partitioning for Optimising Domain

MultilevelMeshPartitioningforOptimisingDomainShapeC.Walshaw,M.Cross,R.DiekmannandF.SchlimbachSchoolofComputingandMathematicalSciences,UniversityofGreenwich,London,SE186PF,UK;DepartmentofComputerScience,UniversityofPaderborn,F¨urstenallee11,D-33102Paderborn,Germany.email:[e-mail]ort98/IM/38July24,1998AbstractMultilevelalgorithmsareasuccessfulclassofoptimisationtechniqueswhichaddressthemeshparti-tioningproblem.Theyusuallycombineagraphcontractionalgorithmtogetherwithalocaloptimisationmethodwhichrenesthepartitionateachgraphlevel.Todatethesealgorithmshavebeenusedalmostexclusivelytominimisethecut-edgeweightinthegraphwiththeaimofminimisingtheparallelcommu-nicationoverhead.Howeverithasbeenshownthatforcertainclassesofsolutionalgorithm,theconver-genceofthesolverisstronglyinuencedshapeoraspectratioofthesubdomains.Inthispapertherefore,wemodifythemultilevelalgorithmsinordertooptimiseacostfunctionbasedonaspectratio.Severalvariantsofthealgorithmsaretestedandshowntoprovideexcellentresults.Keywords:graph-partitioning,mesh-partitioning,multilevelalgorithms,aspectratio,domaindecom-positionpreconditioning.1IntroductionTheneedformeshpartitioningarisesnaturallyinmanyniteelement(FE)andnitevolume(FV)applica-tions.Meshescomposedofelementssuchastrianglesortetrahedraareoftenbettersuitedthanregularlystructuredgridsforrepresentingcompletelygeneralgeometriesandresolvingwidevariationsinbehaviourviavariablemeshdensities.Meanwhile,themodellingofcomplexbehaviourpatternsmeansthattheprob-lemsareoftentoolargetotontoserialcomputers,eitherbecauseofmemorylimitationsorcomputationaldemands,orboth.Distributingthemeshacrossaparallelcomputersothatthecomputationalloadisevenlybalancedandthedatalocalitymaximisedisknownasmeshpartitioning.ItiswellknownthatthisproblemisNP-complete,soinrecentyearsmuchattentionhasbeenfocusedondevelopingsuitableheuristics,andsomepowerfulmethods,manybasedonagraphcorrespondingtothecommunicationrequirementsofthemesh,havebeendevised,e.g.[12].Aparticularlypopularandsuccessfulclassofalgorithmswhichaddressthismeshpartitioningproblemareknownasmultilevelalgorithms.Theyusuallycombineagraphcontractionalgorithmwhichcreatesaseriesofprogressivelysmallerandcoarsergraphstogetherwithalocaloptimisationmethodwhich,start-ingwiththecoarsestgraph,renesthepartitionateachgraphlevel.Todatethesealgorithmshavebeenusedalmostexclusivelytominimisethecut-edgeweight,acostwhichapproximatesthetotalcommuni-cationsvolumeintheunderlyingsolver.Thisisanimportantgoalinanyparallelapplication,inordertominimisethecommunicationsoverhead,however,ithasbeenshown,[19],thatforcertainclassesofsolu-tionalgorithm,theconvergenceofthesolverisactuallyheavilyinuencedbytheshapeoraspectratio(AR)ofthesubdomains.Inthispapertherefore,wemodifythemultilevelalgorithms(thematchingandlocaloptimisation)inordertooptimiseacostfunctionbasedonAR.Wealsoabstracttheprocessofmodication1inordertosuggesthowthemultilevelstrategycanbemodiedintoagenerictechniquewhichcanoptimisearbitrarycostfunctions.1.1DomaindecompositionpreconditionersandaspectratioTomotivatetheneedforaspectratiooptimisationweconsidertherequirementsofaclassofsolutiontech-niques.Anaturalparallelsolutionstrategyfortheunderlyingproblemistouseaniterativesolversuchastheconjugategradient(CG)algorithmtogetherwithdomaindecomposition(DD)preconditioning,e.g.[2].DDmethodstakeadvantageofthepartitionofthemeshintosubdomainsbyimposingarticialboundaryconditionsonthesubdomainboundariesandsolvingtheoriginalproblemonthesesubdomains,[4].Thesubdomainsolutionsareindependentofeachother,andthuscanbedeterminedinparallelwithoutanycommunicationbetweenprocessors.Inasecondstep,an`interface'problemissolvedontheinnerbound-arieswhichdependsonthejumpofthesubdomainsolutionsovertheboundaries.Thisinterfaceproblemgivesnewconditionsontheinnerboundariesforthenextstepofsubdomainsolution.AddingtheresultsofthethirdsteptotherstgivesthenewconjugatesearchdirectionintheCGalgorithm.ThetimeneededbysuchapreconditionedCGsolverisdeterminedbytwofactors,themaximumtimeneededbyanyofthesubdomainsolutionsandthenumberofiterationsoftheglobalCG.Bothareatleastpartiallydeterminedbytheshapeofthesubdomains.Whilstanalgorithmsuchasthemultigridmethodasthesolveronthesubdomainsisrelativelyrobustagainstshape,thenumberofglobaliterationsareheavilyinuencedbytheARofsubdomains,[18].Essentially,thesubdomainscanbeviewedaselementsoftheinterfaceproblem,[7,8],andjustaswiththenormalniteelementmethod,wheretheconditionofthematrixsystemisdeterminedbytheARofelements,theconditionofthepreconditioningmatrixisheredependentontheARofsubdomains.1.2RelatedworkTheideaofoptimisingARinordertomaintainscalabilityinthesolverwasrstdevelopedbyFarhatetal.,[7,8].ThiswasbackedupbyVanderstraetenetal.whoshowedthatpartitioningforcut-edgeweightwasnotnecessarilythemostappropriateoptimisationforeverysolver[18,19].HowevertheeldofmeshpartitioninghaschangedsomewhatsincethisworkwascarriedoutandalthoughothermorerecentworkexistswhichtakesARintoaccount,e.g.[5,6,17],ouraiminthispaperistoextendtheidea