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

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

parisonoftheFMandQBheuristics

METIS

#k

14

5243889227

16

1405623400

1603540777

8

533

32

34

42557336176

16

87441288023

91517489307

8

23982987406

32

54

174711810322

16

59171838763971229MemoryBalancingLoadBalancing|Ec|Wmax Wtmax ttp34373125811.0931.01.27491.3515.51.726298.91.096694411758111.073.21.33491.361.51.7914470.81.111251.087.41.141576.51.101028815234601.063.21.33161.352.31.916631.61.6110210723083191.090.51.35462753179726401.03233.71.072191.1265.11.20430351.91.03222604527474721.2215.31.392821.335.11.5189863.01.123501.24167.91.3993097.61.0376162856623141.0934.21.13591.4814.61.6724609.01.139234717498441.092.21.21104999202694551.07178.01.171171.31106.11.58180267.91.08156317335579041.0621.31.151571.2910.01.7064206.51.33577References

1.George,A.,Liu,J.:ComputerSolutionofLargeSparsePositiveDe niteSystems.PrenticeHall,EnglewoodCli s,NJ(1981)

2.Hendricson,B.:Graphpartitioningandparallelsolvers:Hasemperornoclothes?Irregular’98,LectureNotesinComputerScience1457(1998)218–225

3.Hendricson,B.:Loadbalancing ctions,falsehoodsandfallacies.AppliedMathe-maticalModelling25(2000)99–108

4.Karypis,G.,Kumar,V.:put.20(1998)359–392

5.Karypis,G.,Kumar,V.:put.48(1998)96–129

6.Hendrickson,B.,Leland,R.:Amultilevelalgorithmforpartitioninggraphs.In:Proceedingsofthe1995ACM/IEEEconferenceonSupercomputing(CDROM),ACMPress(1995)28

7.Walshaw,C.,Cross,M.:MeshPartitioning:aMultilevelBalancingandRe put.22(2000)63–80(originallypublishedasUniv.GreenwichTech.Rep.98/IM/35).

8.Pellegrini,F.:Staticmappingbydualrecursivebipartitioningofprocessandarchi-tecturegraphs.SHPCC’94(1994)486–493

9.Kumfert,G.,Pothen,A.:Twoimprovedalgorithmsforenvelopeandwavefrontreduction.BIT37(1997)559–590