help-octave
[Top][All Lists]

## Re: Sparse Eigenvalues

 From: David Bateman Subject: Re: Sparse Eigenvalues Date: Sun, 21 Dec 2008 17:02:51 +0100 User-agent: Mozilla-Thunderbird 2.0.0.17 (X11/20081018)

```Chaman Singh Verma wrote:
```
```
```
Well, here is my sincere question. It is my observation that eigs ( which probably based on ARPACK code) seems to take atleast "N" sparse-matrix-vector operations, which could be quite expensive for reasonably large matrices. One of the application where someone may need second eigenvalue is for graph partitioning ( and famous Google rank Matrix). For typical graph of 200,000 rows and 100-200 columns, it takes more than 45-50 minutes on single node machine, which is not competitive to other
```graph partitioning methods such as METIS.
```
```
```
The google rank matrix is just a power method to find the largest eigenvalue, and the google rank matrices is documented as converging in about 6 iterations of the power method. Google page rank doesn't fing the second largest eigenvalue at all. ARPACK is not the same beast!!
```
```
If you only want the largest eigenvalue then use the power method. What ARPACK gets you is the N largest eigenvalues (or N smallest or N closest to a particular value), and to do that it uses a method a bit like the Lanzcos method with restarting.. Lanzcos method finds the largest eigenvalue, then forms a new problem with the largest eigenvalue removed and repeats.. The new problem is formulated with multiple matrix vector products.. Arnoldi's method adds a restarting step such that it can handle eigenvalues that are close together without convergence issues.
```
```
How did you formulate the problems to eigs? Perhaps there is an issue in the manner eigs is calls. For example a function call for the matrix vector product is likely to be slower than a call to blas xGEMM or the sparse equivalent internal to eigs itself.
```
```
Frankly, I've never looked at how METIS does its graph partitioning, but I didn't have the impression it used an eigenvalue method.. METIS has a repudiation as one of the better graph partitioner out there however.
```
```
```Here is my query to all the knowledge people.

```
(1) What is the most competitive algorithms for finding few eigenvalues/eigenvectors compared to ARPACK. Has somebody done any study and have some number to show its
```      superiority.
```
Is the matrix positive definite? Are there eigenvalues in the set you are looking for that are close together? If the matrix is PD and you don't have eigenvalues close together a straight Lanzcos method will probably be the fastest.
```
```
```(2)  Can we reduce the number of Matrix-Vec Operations ?
```
Getting rid of the restarting in the Arnoldi technique will certainly reduce the number, but at the cost of poor convergence if there are eigenvalues close together.
```
```
```(3)  Can spectral decomposition beat METIS type decompositions ?
```
```
```
Perhaps, but I'm an engineer and not a mathematician, so you might want to ask someone who knows more..
```
D.

```
```
Thanks.
csv

```
```

--