Andrew Knyazev has received an MS degree in Computer Sciences from the Moscow State University in 1981 and a Ph.D. in Numerical Mathematics from the Institute of Numerical Mathematics Russian Academy of Sciences in 1985. After being employed as a Software Engineer at the Kurchatov's Institute of Atomic Energy in 1981-83, Andrew Knyazev started his research carrier at the Institute of Numerical Mathematics Russian Academy of Sciences, where he worked for nine years. In 1992, Andrew Knyazev has moved to the USA and became a visiting scientist at the Courant Institute of Mathematical Sciences, New York University for two years. Since 1994, he is an associate professor at the Department of Mathematics, University of Colorado Denver. One of the main research topics of Andrew Knyazev is numerical solution of large-scale symmetric eigenvalue problems on highly parallel computer systems and applications of eigenproblems in engineering. He is one of the contributors to the Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Editors: Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk Van der Vorst, SIAM, pp. 337-368, 2000.
Friday February 20, 2004
“Modern Preconditioned Eigensolvers for Spectral Image Segmentation”
Several computationally efficient approaches to clustering large-scale and high-dimensional data are based on finding several extreme eigenvalues and corresponding eigenvectors of large sparse symmetric matrices. For example, a well-known problem of image segmentation can be mathematically formulated as a problem of minimization of normalized cuts, which leads to an eigenvalue problem.
Numerical solution of eigenvalue problems poses major computational challenges for large size matrices. As even low-end digital cameras produce mega-pixel images nowadays, it is typical to face image segmentation problems that lead to eigenvalue problems with millions unknowns. Eigenvalue problems for matrices so large are difficult to solve numerically at present. Moreover, it might be expected that the demands for the increased resolution and the needs to treat live feed dynamic images will continue to overgrow the increase in the computational power. An efficient choice of a method for numerical solution of the eigenvalue problem becomes crucial. The ultimate goal could be to find a method with a linear complexity, in other words, a method with computational costs that scale linearly with the problem size.
In the talk, we present an overview of numerical eigenvalue solvers used for image segmentation and introduce a locally optimal block preconditioned conjugate gradient (LOBPCG) method recently suggested and studied by the speaker. The LOBPCG is publicly available in MATLAB, see http://math.ucdenver.edu/˜aknyazev/software/CG/ and in C using MPI and HYPRE libraries for massively parallel computers, see http://www.llnl.gov/CASC/hypre/
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.