Bilkent University
Department of Computer Engineering
S E M I N A R
A Recursive Graph Bipartitioning Algorithm by Vertex Separators for Block-diagonal Matrices with Overlap
Seher Acer
MSc. Student
Computer Engineering Department
Bilkent UniversitySolving linear systems in the form of Ax = b using preconditioners can be efficiently parallelized if matrix A is in block-diagonal form with overlap. A matrix is in block diagonal form with overlap if it is a block diagonal matrix whose consecutive diagonal blocks may overlap. We present the problem of permuting a symmetric matrix into block diagonal form with overlap as a graph-theoretical problem. For this purpose, we introduce Ordered Graph Partitioning by Vertex Separators Problem (OGPVS). Solution of OGPVS problem finds a partition of the vertex set of a given graph into ordered set of balanced vertex parts and vertex separators in such a way that each two consecutive vertex parts are connected through a vertex separator, while minimizing the number of vertices in vertex separators. We present an algorithm to solve OGPVS Problem, that recursively bipartitions the given graph until the desired number of parts is reached. Necessary and sufficient conditions are analyzed for feasibility. Experiments performed on real-world matrices show the usefulness of this approach.
DATE: 21 March, 2011, Monday @ 15:40
PLACE: EA409