# Ublas :

From: Karl Meerbergen (Karl.Meerbergen_at_[hidden])
Date: 2006-04-12 05:19:35

Hi,

It all depends on the size of the problem. For small problems with dense or
banded matrices I recommend using LAPACK. Some bindings are available in the
boost-sandbox.
For large problems I recommend using ARPACK
(www.caam.rice.edu/software/ARPACK/). You can use Arpack for computing the 2
smallest eigenvalues and eigenvectors. The second computed is the one you
need.

Your problem looks similar to the Laplacian matrix from graph partitioning
where you want to compute the Fiedler vector. Searching the literature on
this topic might also be very useful for your problem.

The power method suggested by Gunther converges very slowly and is not useful
for your problem, unless you have a pretty good idea where the eigenvalue is:
you can then use the iteration:

y = (A-s*I)^-1 * x
x = y/norm_2(x)

where s is an approximation of the eigenvalue.
Use (dense or sparse) direct linear solvers for computing y.

Do not hesitate to ask further questions if you need any.

Good luck,

Karl

On Wednesday 12 April 2006 10:21, Gunter Winkler wrote:
> 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
>
> _______________________________________________
> ublas mailing list
> ublas_at_[hidden]

```--
==============================================
Look at our unique training program and
Register on-line at http://www.fft.be/?id=35
----------------------------------------------
Karl Meerbergen
Free Field Technologies
Axis Park Louvain-la-Neuve
rue Emile Francqui, 1
B-1435 Mont-Saint Guibert - BELGIUM
Company Phone:  +32 10 45 12 26
Company Fax:    +32 10 45 46 26
Mobile Phone:   +32 474 26 66 59
Home Phone:     +32 2 306 38 10
mailto:Karl.Meerbergen_at_[hidden]
http://www.fft.be
==========================================================================================
```