Scribd
Upload
10 views23 pages

Partitioning

Uploaded by

abhishek
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
10 views23 pages

Partitioning

Uploaded by

abhishek
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 23

Spectral Partitioning: One way to

slice a problem in half

A C B
 2
8
Laplacian of a Graph G
2 5
3 2 -1 -1 v1 0
5
3 -1 3 -1 -1 v2 0
1 4 6
4 -1 -1 3 -1 v3 = 1
2 7 -1 3 -1 -1 v4 -1
1 6 -1 -1 3 -1 v5 0
Battery -1 -1 2 v6 0
VB volts

( )ii=

G
2 degree of node i

( G )ij= -1 for edges i, j


2

Edge-Node Incidence Matrix
1 2 3 4 5 6
2 -1 -1 1 1 -1
-1 3 -1 -1 2 1 -1
2 MG= 3 1 -1

G =
-1 -1 3 -1
4 1 -1
-1 3 -1 -1 5
-1 -1 3 -1 1 -1
6 1 -1
-1 -1 2 7 1 -1
8 8 1 -1
2 5
3 5
1 3 4 6  2
4 G
= M T
G M G
2 7
1 6
Spectral Partitioning
Express partition problem with linear algebra!
Partition vector: xi= 1 denotes i’s partition.

n 2
(MGx)i T 2
=(MGx) (MGx)=x MGMGx=x Gx

T T T

i=1

 2
xT G x = 4(# cross partition edges)
Goal is to minimize this for xi=1 and xi=0.
2
Bounded above by minimizing over ball xi =n.
Solve as an eigenvalue problem!
Geometric Mesh Partitioning:
The Miller, Teng, Thurston,
Vavasis Algorithm

A C B
Graph Partitioning
• Division of graph into subgraphs with goal
of minimizing communication and
maximizing load balance.

Geometric Methods
• Uses not only the graph (= combinatorial
information) but also geometrical coordinates
(x,y) or (x,y,z) for the nodes.
Edge Separator Vertex Separator

A C B

Remove Separator Nodes = AB C


Edges No edges between
A and B
Simple Geometric Partitioner:
Coordinate Bisection
• 1. Compute median of x and y coordinates
• 2. Count edges along x=mean(x) and y=mean(y)
• 3. Use cut which minimizes the two
• OK for Bad
Theory vs. Practice
• Random Graphs may have lousy separators
• Practical Numerical Meshes often have good
separators
• Fact: For numerical reasons, meshes have good
aspect ratios
• In 2-d:
• A1=longest edge/shortest edge
• A2=circumsphere/inscribed sphere
• A3=diameter / volume^(1/d)
Need Theoretical Class of Good
Graphs
• Defn: k-ply neighborhood system = closed disks
no (k+1) of which overlap

3-ply
4-ply

• A (1,k) overlap graph for a k-ply system =graph


obtained by connecting centers of intersecting
circles
• (,k) overlap graph = connect centers if Di
Dj (
Why is this useful?
• Intuitively: Good overlap graph = bounded
aspect ratio
• Theoretical Theorems best proved about
overlap graphs. Example:
• Geometric Separator Theorem:
Geometric Separator Theorem
If G=(,k) overlap graph in d dimensions,
there exists a vertex separator with
O(k^(1/d) n^((d-1)/d)) vertices.
In English: All good overlap graphs behave
as if they are cubes. A d-cube with n vertices
has a separator of size n^((d-1)/d).

1/3
 n n

2/3
n
n
Miller, Teng, Thurston, Vavasis
algorithm for finding separator
1) Stereographic Projection
2) Find centerpoint
3) Conformal Map
4) Find Great Circle
5) Project Back
6) Create Separator
Details ...
Step 1:Stereographic Projection
N

Rd Project P to sphere along


the line to the north pole.
S P

Mercator Map
Ster Proj Log z

Not cylindicrical projection!


Step 2: Find Centerpoint
Definition: A Centerpoint is a point C such
that every hyperplane through C roughly
divides the points evenly.

Theorem: Every finite set has a centerpoint --


may be found my linear programming (not
practical). Later: A practical heuristic.
Step 3: Conformal Map to move
centerpoint to center of sphere
Why? Increases chances of a good cut.

Rotate and Dilate:


Rotate: centerpoint to (0,0,r)
Dilate: centerpoint to (0,0,0)
Steps 4 through 6
4) Cut with a random great circle.
5) Stereographic projection back to the plane
from the sphere.
6) Convert the circle in the plane to a
separator.

DEMO!
Centerpoint Computation
Heuristic runs in linear time by computing
Radon points.
Definition: q is a Radon point of a set of
points P if P=P1 P2 (disjoint union )
and q is in both the convex hull of
P1 and P2.
Convex hull -- smallest convex polygon
containing the set.

Convex Not Convex


Radon Points
Definition: q is a Radon point of a set of points P if
P=P1 P2 (disjoint union ) and q is in both the convex
hull of P1 and P2.

Examples: (d+2 points in d dims)

d=2 d=3
Radon Point
Computing Radon Pnts = Linear Algebra
A point P is in the convex hull of a set of points P i
if and only if it has the form P=iPi:i=1, i0.

Solve

Let c =
(
 
P1 P2 … Pd+2

i = 1-i.1The
…Radon )( )
1 point is then
.1
..
= 0

d+2
Pos Neg  P /c=- P /c.
i i i i

i i
Pos Neg
i i
Geometric Sampling
Select random sample of points.
Randomly replace d+2 points with Radon pt

A few tricks
1) Try a few random great circles (using
normal dist)
2) Weigh the normal vector in the moment of
inertia direction
METIS and Parmetis

You might also like