[Date Index] [Thread Index] [Author Index]

Re: Is there a lowest Eigenvalues function around?

• To: mathgroup@smc.vnet.net
• Subject: [mg11032] Re: Is there a lowest Eigenvalues function around?
• From: Paul Abbott <paul@physics.uwa.edu.au>
• Date: Wed, 18 Feb 1998 20:31:33 -0500
• Organization: University of Western Australia
• References: <6c8q6s$ats@smc.vnet.net>

Christopher R. Carlen wrote:

> I have to find the eigenvalues of very large matrices, ie 1024x1024 up
> to over 10000x10000 .  I run out of memory when trying to do more than
> about 1600x1600 .  I know there are algorithms to find the lowest or
> highest eigenvalues of a matrix, but the Mathematica function
> Eigenvalues[] finds all of them.
> 
> Does anyone know if there is an implementation of a lowest-eigenvalues
> function anywhere?  I have looked aroung at www.wolfram.com but didn't
> find anything.

I set this as a problem for my students in their 1997 Computational
Physics exam.  The exam Notebook is available from 

http://www.pd.uwa.edu.au/Physics/Courses/Third_Year/Computational_Physics.html

The largest or smallest eigenvalue of a matrix (and the corresponding
eigenvector) can be computed using the power method [G H Golub and C F
van Loan, Matrix Computations, Johns Hopkins Press, Baltimore, 1989]. 

Here is a simple implementation for finding the largest eigenvalue (and
the corresponding eigenvector) using Nest. 

In[1]:= A = Table[Random[], {300}, {300}]; 

In[2]:= f[A_] := f[A] = Compile[{{q, _Real, 1}}, Module[{z = A.q},
z/Sqrt[z.z]]]

Starting with 

In[3]:= q0 := Table[1., {Length[A]}]

we Nest f a number of times to approximately obtain the eigenvector
corresponding to the largest eigenvalue: 

In[4]:= (q = Nest[f[A], q0, 10];) //Timing//First Out[4]= 1.39 Second

The largest eigenvalue is then

In[5]:= q.A.q//Timing
Out[5]= {0.47 Second,149.638}

Compare this with

In[6]:= Eigenvalues[A]//Sort//Last//Timing Out[6]= {14.55
Second,149.638}

Cheers,
	Paul 

____________________________________________________________________ 
Paul Abbott                                   Phone: +61-8-9380-2734
Department of Physics                           Fax: +61-8-9380-1014
The University of Western Australia            Nedlands WA  6907       
mailto:paul@physics.uwa.edu.au  AUSTRALIA                            
http://www.pd.uwa.edu.au/~paul

            God IS a weakly left-handed dice player
____________________________________________________________________