Sparse Eigenvalues

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Sparse Eigenvalues

Chaman Singh Verma-3
Hello,

Does anyone know any performance results of Sparse-Eigenvalue solver (i.e. eigs ) ? My observation
is that it is too slow.

Thanks.
csv


_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Sparse Eigenvalues

John W. Eaton
Administrator
On 20-Dec-2008, Chaman Singh Verma wrote:

| Does anyone know any performance results of Sparse-Eigenvalue solver (i.e.
| eigs ) ? My observation
| is that it is too slow.

What is the purpose of sending a message like this?  Do you think that
it helps in some way?  If you think that there is something that could
be improved, then I suggest helping our community by working on the
problem and submitting a patch, not just complaining in vague terms
that something doesn't meet your expectations.

jwe
_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Sparse Eigenvalues

Jaroslav Hajek-2
In reply to this post by Chaman Singh Verma-3
On Sat, Dec 20, 2008 at 12:56 PM, Chaman Singh Verma <[hidden email]> wrote:
> Hello,
>
> Does anyone know any performance results of Sparse-Eigenvalue solver (i.e.
> eigs ) ? My observation
> is that it is too slow.
>

Too slow for what?


--
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz
_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Sparse Eigenvalues

Chaman Singh Verma-3
In reply to this post by John W. Eaton


On Sat, Dec 20, 2008 at 9:16 PM, John W. Eaton <[hidden email]> wrote:
On 20-Dec-2008, Chaman Singh Verma wrote:

| Does anyone know any performance results of Sparse-Eigenvalue solver (i.e.
| eigs ) ? My observation
| is that it is too slow.

What is the purpose of sending a message like this?  Do you think that
it helps in some way?  If you think that there is something that could
be improved, then I suggest helping our community by working on the
problem and submitting a patch, not just complaining in vague terms
that something doesn't meet your expectations.

jwe

Hello,

Sorry, if my sentence hurt in any way somebody's feelings, it was unintentional.
but you are correct that I should have been more objective. I will be careful next time.
But surely, I was not critical about Octave, it is WONDERFUL software.

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.

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.
(2)  Can we reduce the number of Matrix-Vec Operations ?
(3)  Can spectral decomposition beat METIS type decompositions ?

Thanks.
csv




_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Sparse Eigenvalues

John W. Eaton
Administrator
On 20-Dec-2008, Chaman Singh Verma wrote:

| more than 45-50 minutes on single node machine, which is not competitive to
| other
| graph partitioning methods such as METIS.

METIS is distributed under terms that are incompatible with the GPL,
so it can't be used with Octave.

jwe
_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Sparse Eigenvalues

Jordi Gutiérrez Hermoso
2008/12/20 John W. Eaton <[hidden email]>:
> On 20-Dec-2008, Chaman Singh Verma wrote:
>
> | more than 45-50 minutes on single node machine, which is not competitive to
> | other
> | graph partitioning methods such as METIS.
>
> METIS is distributed under terms that are incompatible with the GPL,
> so it can't be used with Octave.

What are the distribution terms, btw? I can't find them. It's in
Debian's contrib, and the source tarball doesn't seem to have a clear
copyright statement other than saying it's copyrighted by the regents
of the university of Minnesota. There's a statement on the webpage
indicating some restrictions on commercial use. It also seems to be
supported by the US military, which I thought meant no copyright.

Do they have an actual copyright statement at all?

I wonder if we could convince them to change the terms...

- Jordi G. H.
_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Sparse Eigenvalues

bpabbott
Administrator

On Dec 20, 2008, at 9:39 PM, Jordi Gutiérrez Hermoso wrote:

> 2008/12/20 John W. Eaton <[hidden email]>:
>> On 20-Dec-2008, Chaman Singh Verma wrote:
>>
>> | more than 45-50 minutes on single node machine, which is not  
>> competitive to
>> | other
>> | graph partitioning methods such as METIS.
>>
>> METIS is distributed under terms that are incompatible with the GPL,
>> so it can't be used with Octave.
>
> What are the distribution terms, btw? I can't find them. It's in
> Debian's contrib, and the source tarball doesn't seem to have a clear
> copyright statement other than saying it's copyrighted by the regents
> of the university of Minnesota. There's a statement on the webpage
> indicating some restrictions on commercial use. It also seems to be
> supported by the US military, which I thought meant no copyright.
>
> Do they have an actual copyright statement at all?
>
> I wonder if we could convince them to change the terms...
>
> - Jordi G. H.


The license is included with the sources

        http://glaros.dtc.umn.edu/gkhome/metis/metis/download

-------------------------------------------
Copyright Notice
----------------

The METIS package is copyrighted by the Regents of the University of
Minnesota. It can be freely used for educational and research purposes
by non-profit institutions and US government agencies only. Other
organizations are allowed to use METIS only for evaluation purposes,
and any further uses will require prior approval. The software
may not be sold or redistributed without prior approval. One may
make copies of the software for their use provided that the copies,
are not sold or distributed, are used under the same terms and
conditions.

As unestablished research software, this code is provided on an
``as is'' basis without warranty of any kind, either expressed or
implied. The downloading, or executing any part of this software
constitutes an implicit agreement to these terms. These terms and
conditions are subject to change at any time without prior notice.
-------------------------------------------

I'm not an expert, but there appears to be GPL'd options. For  
example ...

        http://www.sandia.gov/~bahendr/chaco.html

Ben






_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Sparse Eigenvalues

David Bateman-2
In reply to this post by Chaman Singh Verma-3
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
>


--
David Bateman                                [hidden email]
35 rue Gambetta                              +33 1 46 04 02 18 (Home)
92100 Boulogne-Billancourt FRANCE            +33 6 72 01 06 33 (Mob)

_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Sparse Eigenvalues

Przemek Klosowski
In reply to this post by John W. Eaton
On 20-Dec-2008, Chaman Singh Verma wrote:

   | Does anyone know any performance results of Sparse-Eigenvalue solver (i.e.
   | eigs ) ? My observation
   | is that it is too slow.

And John correctly responded:

   What is the purpose of sending a message like this?  Do you think that
   it helps in some way?  If you think that there is something that could

Amen to that---indeed, 'slow compared to what'? It reminds me of an old
absurd joke:

"What is the difference between the sparrow?"

"It has a shorter leg."

OK, so maybe it's only funny in Polish :)
_______________________________________________
Help-octave mailing list
[hidden email]
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave