Load and memory balanced mesh partitioning for a parallel en

Abstract. We use a parallel direct solver based on the Schur complement method for solving large sparse linear systems arising from the finite element method. A domain decomposition of a problem is performed using a graph partitioning. It results in sparse

LoadandMemoryBalancedMeshPartitioning

foraParallelEnvelopeMethod

OndˇrejMedek,PavelTvrd´ k,andJaroslavKruis

CzechTechnicalUniversity,Prague,CzechRepublic,

xmedeko@fel.cvut.cz,tvrdik@fel.cvut.cz,kruis@fsv.cvut.cz

Abstract.WeuseaparalleldirectsolverbasedontheSchurcomple-mentmethodforsolvinglargesparselinearsystemsarisingfromthe niteelementmethod.Adomaindecompositionofaproblemisperformedus-ingagraphpartitioning.Itresultsinsparsesubmatriceswithbalancedsizes.Anenvelopemethodisusedtofactorizethesesubmatrices.How-ever,thememoryrequirementstostorethemandthecomputationalcosttofactorizethemdependsheavilyontheirstructure.Weproposeatech-niquethatmodi esthemultilevelgraphpartitioningschematobalancerealcomputationalloadormemoryrequirementsofthesolver.

1Introduction

Manyengineeringandscienti cproblemsaresolvedusingthe niteelementmethod(FEM).Weconsiderameshof niteelements.Oneelementconsistsofseveralnodes.Eachnodehasitsdegreesoffreedom(DOFs).Inotherwords,thenodescontainvariables.Globally,thesevariablesformasystemofequationsAx=b,whereAisann×nsparsematrixofcoe cients.AmeshisusuallyrepresentedbyadualgraphGDandanodalgraphGN.Theverticesinthedualgraphrepresentthe niteelementsand2verticesareadjacentifandonlyifthecorrespondingelementsshareacommonsurfacein3Doracommonedgein2D.Theverticesinthenodalgraphrepresentthemeshnodes.Allverticesthatrepresentmeshnodesbelongingtooneelementformaclique.AnexampleofaFEmeshanditsdualandnodalgraphisonFig.1.

WeusesolverSIFEL,developedattheCzechTechnicalUniversity,forsolvingproblemsbytheFEM.Amongothers,itcansolveproblemsinparallelbythepopularmethodoftheSchurcomplements,whicharecomputedbyanenvelopemethod[1].Asolutionofaproblemconsistsof6followingphases:1.

2.

3.

4.

5.Domaindecomposition.Orderingofnodes.Assemblingofsubmatrices.Factorizationofsubmatrices(computationoftheSchurcomplements).Solutionofthereducedproblem.