Sexta-feira, 15 de outubro de 1999
Auditório Jacy Monteiro
Instituto de Matemática e Estatística, USP
5:30 - 6:20 Marcos Kiwi, Universidad de Chile, Chile
Min-Max-Boundary Domain Decomposition
Domain decomposition is one of the most effective and popular parallel
computing techniques for solving large scale numerical systems and partial
differential equations numerically. It also has applications in circuit
layout, simulations of the $N$-body problem, etc.
When the amount of computation in a subdomain is proportional to the volume of
the subdomain, domain decomposition amounts to minimizing the surface area of
each subdomain while dividing the volume evenly. Motivated by this fact, we
study the following min--max boundary multi--way partitioning problem: Given a
graph $G$ and an integer $k$, we would like to divide $G$ into $k$ subgraphs
(by removing edges) such that (i) the vertex size of each subgraph is
$\Theta(|G|/k)$; and (ii) the maximum boundary size of any subgraph (the set
of edges connecting it with other subgraphs) is minimized.
We provide an algorithm that given a graph satisfying some hipotesis, in
particular given a well--shaped mesh in $d$ dimensions, finds a partition of
the graph into $k$ subgraphs, each one with $\Theta(|G|/k)$ vertices and the
number of edges connecting each subgraph with the other subgraphs is
$O((|G|/k)^{1-1/d})$. Finally, we extend our results to vertex--weighted and
vertex--based graph decomposition. Our results can be used to simultaneously
balance the computational and memory loads on a distributed--memory parallel
computer without incurring large communication overhead.
The results discussed in this talk are joint work with Dan Spielman (MIT) and
Shang-Hua Teng (University of Illinois, Urbana-Champaign)
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Fri Oct 8 11:51:59 EDT 1999