Re: [ublas] finding the second smallest eigenvector of a matrix

From: Gunter Winkler (gunter.winkler_at_[hidden])
Date: 2006-04-12 04:21:01

On Tuesday 11 April 2006 20:27, asaf david wrote:
> hello
> i have a symetric and positive definite matrix A, and i'd like to find the
> second smallest eigenvector v of it (i believe the second smallest
> eignevector is the eigenvector corresponding for the second smallest
> eigenvalue, where the smallest is 0, but i'm not entirely sure about it..).
> Is there any straightforward way to do it in uBLAS? and if not, could you
> please recommend some other package?

You should definitely look for LAPACK or similar to compute eigenvalues and 
eigenvectors. See http://www.netlib.org 

In general you can compute eigenvectors and eigenvalues with a simple 
iteration to compute the largest eigenvalue:

x = any nonzero start vector

iterate:
  y = Ax
  x = y / norm(y)

then norm(y)/norm(x) converges to the largest eigenvalue and x converges to 
the corresponding eigenvector.

In order to compute the smallest eigenvalue of A you compute the largest 
eigenvalue of the inverse of A. (You have to solve Ay=x in every iteration.) 
If 0 is eigenvalue of A you have to compute the nullspace first and use a 
start vector orthogonal to this nullspace and a more general solver, e.g. 
solve norm(Ay - x) -> inf, s.t. y is orthogonal to the nullspace.

All operations can be implemented using ublas, but a more specialized packages 
will be more efficient.

mfg
Gunter