Wednesday June 11th, 2008
Wean 8220
1:30pm
Title: Graph partitioning into isolated, high conductance clusters: Theory, computation and applications to preconditioning.
Yiannis Koutis, CMU
Abstract:
We study the problem of decomposing a weighted graph with $n$ vertices into a collection $P$ of vertex disjoint clusters such that, for all clusters $C$ in $P$, the graph induced by the vertices in $C$ and the edges leaving $C$, has conductance bounded below by a constant $\phi$. We show that for constant average degree graphs we can compute a decomposition $P$ such that $|P| < n/a$, where $a$ is a constant, in $O(\log n)$ parallel time with $O(n)$ work. We show how these decompositions can be used in the first known linear work parallel and quite practical construction of provably good preconditioners for the important class of fixed degree graph Laplacians. On a more theoretical note, we present upper bounds on the Euclidean distance of eigenvectors of the normalized Laplacian from the space of vectors which consists of the cluster-wise constant vectors.
