Multilevel algorithms are a successful class of optimization techniques that address
the mesh partitioning problem for mapping meshes onto parallel computers. They
usually combine a graph contraction algorithm together with a lo-cal optimization
method that refines the partition at each graph level. To date, these algorithms
have been used al-most exclusively to minimize the cut-edge weight in the graph with
the aim of minimizing the parallel communication overhead. However, it has been
shown that for certain classes of problems, the convergence of the underlying
solution algorithm is strongly influenced by the shape or aspect ratio of the
subdomains. Therefore, in this paper, the authors modify the multilevel algorithms
to optimize a cost function based on the aspect ratio. Several variants of the
algorithms are tested and shown to provide excellent results.
Get full access to this article
View all access options for this article.
References
1.
Barnard, S. T.
, and
H. D. Simon
. 1994.
A fast multilevel implementation of recursive spectral bisection for
partitioning un-structured problems
. Concurrency: Practice & Experience6 (2):
101-117
.
2.
Blazy, S.
,
W. Borchers
, and
U. Dralle
. 1995. Parallelization methods for a
characteristic’s pressure correction scheme. In Flow
simulation with high performance computers II: Notes on numerical fluid
mechanics, edited by
E. H. Hirschel
.
Braunschweig: Vieweg
.
3.
Bouhmala, N. 1998. Partitioning of unstructured meshes for parallel
processing. Ph.D. dissertation, Inst. d’Informatique, Univ. Neuchatel.
4.
Bramble, J. H.
,
J. E. Pasciac
, and
A. H. Schatz
. 1986.
The construction of preconditioners for elliptic problems by
sub-structuring I+II
. Math Comp47:
103-134
; 49:1-16.
5.
Diekmann, R.
,
B. Meyer
, and
B. Monien
. 1998.
Parallel decomposition of unstructured FEM-meshes
. Concurrency: Practice & Experience10 (1):
53-72
.
6.
Diekmann, R.
,
F. Schlimbach
, and
C. Walshaw
. 1998.
Quality balancing for parallel adaptive FEM
. In Proceedings of Irregular ‘98: Solving irregularly
structured problems in parallel, vol. 1457 of LNCS, edited
A. Ferreiraet al.
,
170-181
. Berlin: Springer.
7.
Farhat, C.
,
N. Maman
, and
G. Brown
. 1995.
Mesh partitioning for implicit computations via domain decomposition
. Int J Numer Methods Engng38:
989-1000
.
8.
Farhat, C.
,
J. Mandel
, and
F. X. Roux
. 1994.
Optimal convergence properties of the FETI domain decomposition method
. Comput Methods Appl Mech Engng115:
365-385
.
9.
Fiduccia, C. M.
, and
R. M. Mattheyses
. 1982.
A linear time heuristic for improving network partitions
. In Proceedings of the 19th IEEE Design Automation
Conference,
175-181
. Piscataway, NJ: IEEE.
10.
Gupta, A.1996.
Fast and effective algorithms for graph partitioning and sparse matrix reordering
. IBM Journal of Re-search and Development41 (1/2):
171-183
.
11.
Hendrickson, B.
, and
R. Leland
. 1993. A multilevel algorithm for partitioning graphs.
Technical Report SAND 93-1301,
Sandia National Labs, Albuquerque, NM
.
12.
Hendrickson, B.
, and
R. Leland
. 1995.
A multilevel algorithm for partitioning graphs
. In Proceedings of Supercomputing ‘95.
New York: ACM Press.
13.
Hu, Y. F.
,
R. J. Blake
, and
D. R. Emerson
. 1998.
An optimal migration algorithm for dynamic load balancing
. Concurrency: Practice & Experience10 (6):
467-483
.
14.
Karypis, G.
, and
V. Kumar
. 1995a. A fast and high quality multi-level scheme for
partitioning irregular graphs. Report TR 95-035,
Department of Computer Science, University of Minnesota, Minneapolis
.
15.
Karypis, G.
, and
V. Kumar
. 1995b. Multilevel k-way partitioning scheme for irregular
graphs. Report TR 95-064,
Department of Computer Science, University of Minnesota, Minneapolis
.
16.
Kernighan, B. W.
, and
S. Lin
. 1970.
An efficient heuristic for partitioning graphs
. Bell Systems Tech J49:
291-308
.
17.
Kirkpatrick, S.
,
C. D. Gelatt
, and
M. P. Vecchi
. 1983.
Optimization by simulated annealing
. Science220 (4598):
671-680
.
18.
Mitchell, S. A.
, and
S. A. Vasavis
. 1992.
Quality mesh generation in three dimensions
. In Proceedings of ACM Conference on Computer Geometry,
212-221
. New York:ACM Press.
19.
Schlimbach, F. 1998. Load balancing heuristics optimising sub-domain aspect
ratios for adaptive finite element simulations. Diploma thesis, Department of
Mathematics and Computer Science, University of Paderborn.
20.
Vanderstraeten, D.
,
C. Farhat
,
P. S. Chen
,
R. Keunings
, and
O. Zone
. 1996.
A retrofit based methodology for the fast generation and optimization of
large-scale mesh partitions: Be-yond the minimum interface size criterion
. Comput Methods Appl Mech Engng133:
25-45
.
21.
Vanderstraeten, D.
,
R. Keunings
, and
C. Farhat
. 1995. Beyond conventional mesh partitioning algorithms
and the minimum edge cut criterion: Impact on realistic applications.
In Parallel processing for scientific computing, edited by
D. Baileyet al.
, 611-614.
Philadelphia, PA: SIAM
.
22.
Walshaw, C.
, and
M. Cross
. 1998. Mesh partitioning: A multi-level balancing and
refinement algorithm. Technical Report 98/IM/35,
University of Greenwich, London
.
23.
Walshaw, C.
,
M. Cross
,
R. Diekmann
, and
F. Schlimbach
. 1998.
Multilevel mesh partitioning for aspect ratio
. In Proceedings of VecPar’98, Porto, Portugal,
381-394
. Porto, Portugal: Universidade do Porto.
24.
Walshaw, C.
,
M. Cross
, and
M. Everett
. 1997.
Parallel dynamic graph partitioning for adaptive unstructured meshes
. J Par Dist Comput47 (2):
102-108
.
