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

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

Fig.4.Data owoftheQBheuristics

NNtoelementsfromGD0,pcorrespondtoapartitionGpofG.Thentheinternal

NverticesofGNparereorderedbytheSloanalgorithm.Finally,thequalityofGpisestimatedandreturnedtothere nementheuristics.

InthecurrentimplementationoftheQBheuristics,nodeshaveeithercon-stantnumberofDOFsd>0orareconstrained,i.e.,thenumberofDOFsis0.NAllconstrainednodesareomittedinthestepofprojectionofGD0,ptoGp,i.e.,thereorderingisperformedonlywithnodeswiththenumberofDOFsd>0.Afterthat,nodeigeneratesequationsnumbereddi,di+1,...di+d 1andwavefrontswdi(A),wdi+1(A),...,wdi+d 1(A).

TheoriginalFMheuristicscomputessumsofweightsofverticesinthesourceandtargetpartitionsforeverycandidatemove.Infact,theweightofthecan-didatevertexissubtractedfromtheweightofthesourcepartitionandaddedtotheweightofthetargetpartition.However,intheQBheuristics,thiswouldimplythereorderingandestimationcomputingforeverycandidatemoveandthiswouldextremelyslowdownthere nement.Thus,wehadtomodifytheconditionsofmoveacceptanceasfollows:

1.Thesizeoftheedgecutisdecreasedandthetargetpartitionisnotoverbal-anced.

2.Thequalityqsofthesourcepartitionisgreaterthanthequalityqtofthetargetpartition,butthesizeoftheedgecutisnotincreased.

Theconditionsofmoveacceptanceofthebalancingsteparealsomodi ed:

1.qs>qt.

2.Thesizeoftheedgecutisdecreasedandqs>=qt.

Onlyifamoveisaccepted,thequalitiesqsandqtarerecomputed.Notethatthenewconditionsmayleadtooverbalancingofthetarget,oreventhesource,partitions.Therefore,ifthenewvalueqsisgreaterthanitspreviousvalue,thevertexmoveisnulli ed.