Load and memory balanced mesh partitioning for a parallel en(3)

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

factorizationtimeestimations.Thisinfactleadstoshorterexecutiontimeoftheparallelsolver.Theideaistointegrateanorderingalgorithmintoamultilevelgraphpartitioningschema.

Section2describesthepreviouswork.InSection3,thenewre nementheuris-ticsthatallowstobalancebettermemoryorcomputingcomplexityisexplained.InSection4,theresultsofexperimentsarepresentedandSection5concludesthepaper.

2

2.1PreviousWorkDomainDecomposition(Phase1)

Commonmethodsfordomaindecompositionarebasedongraphpartitioning,typicallyofdualgraphs.Asubdomainismadeofelementsfromthesameparti-tion.Thenodesbelongingtomorethanonesubdomainarecalledboundaryandtheremainingnodesareinternal.Variablesoftheinternal(boundary)nodesarecalledcorrespondingly.AnexampleonFig.2(a)showsa2-waypartitioningofGDofthequadrilateralmeshfromFig.1.Thecorrespondingdomaindecompo-sitionisshownonFig.2(b).Theboundarynodesare3,7,10,11,and14.NotethatthiswayofdomaindecompositionproducespartitioningofthenodalgraphGNbyanodecut,asshownonFig.2(c).

1

9

135adg14142610be371110h153711cfi1648(a)(b)(c)

Fig.2.PartitioningofthemeshfromFig.1usingitsdualgraph(a)into2partitions(b)andcorrespondingpartitioningofthenodalgraph(c).Theedgecut(a)isindicatedbyadashedlineandnodesinthenodecut(c)as lledsquares.

MultilevelGraphPartitioning.Popularmultilevelgraphpartitioningsoft-wareisMETIS[4,5],CHACO[6],JOSTLE[7],andSCOTCH[8].Ourworkisbasedonthemultilevelk-waygraphpartitioningimplementedinMETIS[5].Thisschemaconsistsofthefollowing3phases,shownonFig.3.

Coarsening.AsequenceofsmallergraphsGl=(Vl,El)isconstructedfrom

theoriginalgraphG=G0=(V0,E0)sothat|Vl|>|Vl+1|.Thesequenceof