Modern Preconditioned Eigensolvers for Spectral Image Segmentation and Graph Bisection 

Andrew Knyazev, CU-Denver
andrew.knyazev@ucdenver.edu

Known spectral methods for graph bipartition and image
segmentation require numerical solution of eigenvalue
problems with the graph Laplacian. We discuss several
modern preconditioned eigenvalue solvers for computing
the Fiedler vectors of large scale eigenvalue problems. The
ultimate goal is to find a method with a linear complexity,
i.e. a method with computational costs that scale linearly
with the problem size. A locally optimal block preconditioned
conjugate gradient (LOBPCG) method might be a promising candidate
(if matched with a high quality preconditioner), compared
against the Lanczos method. 

The LOBCPG code is available at http://math.ucdenver.edu/~aknyazev/software/CG/
The slides of the talk will be availabe at 
http://math.ucdenver.edu/~aknyazev/research/conf/
after the conference. 

This material is based upon work supported by the National Science Foundation
and the Intelligence Technology Innovation Center through the joint
"Approaches to Combat Terrorism" Program Solicitation NSF 03-569.

Part of CP3: Filtering and Segmentation Session
SIAM Conference on Imaging Science
Salt Lake City, May 3-5, 2004