Author 
Message 
Skunk science forum beginner
Joined: 19 Jul 2006
Posts: 2

Posted: Wed Jul 19, 2006 10:19 pm Post subject:
Power Method and negative eigenvalues



Hi,
I implemented the power method algorithm in C++ in order to find the
leading eigenvalue of a real square matrix and its associated eigenvector.
My problem is that this method compute the eigenvalue with the largest
*absolute* value and that i would it to compute the largest *positive*
eigenvalue.
Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?
Thank you very much ! 

Back to top 


Roy Stogner science forum beginner
Joined: 13 Jun 2005
Posts: 38

Posted: Thu Jul 20, 2006 3:22 am Post subject:
Re: Power Method and negative eigenvalues



On Thu, 20 Jul 2006 00:19:11 +0200, Skunk wrote:
Quote:  Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?

The first idea that comes to mind: if the largest magnitude negative
eigenvalue of A is g, can you use the power method to find the largest
magnitude eigenvalue of (A + gI) then subtract g to get the corresponding
eigenvalue of A?

Roy Stogner 

Back to top 


Gottfried Helms science forum Guru
Joined: 24 Mar 2005
Posts: 301

Posted: Thu Jul 20, 2006 7:27 am Post subject:
Re: Power Method and negative eigenvalues



Am 20.07.2006 00:19 schrieb Skunk:
Quote:  Hi,
I implemented the power method algorithm in C++ in order to find the
leading eigenvalue of a real square matrix and its associated eigenvector.
My problem is that this method compute the eigenvalue with the largest
*absolute* value and that i would it to compute the largest *positive*
eigenvalue.
Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?
Thank you very much !
Would it be possible to compute the matrixexponential EA of A 
first? Then the negative eigenvalues of A transform to the
lowest eigenvalues of EA. Then find the highest eigenvalue
of EA with the powermethod and take its log.
Just sketch, no warranty, that this is efficient ...
Gottfried Helms 

Back to top 


Jeremy Watts science forum Guru Wannabe
Joined: 24 Mar 2005
Posts: 239

Posted: Thu Jul 20, 2006 8:47 am Post subject:
Re: Power Method and negative eigenvalues



"Skunk" <skunk@ag.com> wrote in message
news:44beafcc$0$12612$5402220f@news.sunrise.ch...
Quote:  Hi,
I implemented the power method algorithm in C++ in order to find the
leading eigenvalue of a real square matrix and its associated eigenvector.
My problem is that this method compute the eigenvalue with the largest
*absolute* value and that i would it to compute the largest *positive*
eigenvalue.
Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?
Thank you very much !

why not just use the QR algorithm to find the whole spectrum and then search
it to find the largest positive eigenvalue? 

Back to top 


iandjmsmith@aol.com science forum beginner
Joined: 13 Sep 2005
Posts: 15

Posted: Thu Jul 20, 2006 8:48 am Post subject:
Re: Power Method and negative eigenvalues



Skunk wrote:
Quote:  Hi,
I implemented the power method algorithm in C++ in order to find the
leading eigenvalue of a real square matrix and its associated eigenvector.
My problem is that this method compute the eigenvalue with the largest
*absolute* value and that i would it to compute the largest *positive*
eigenvalue.
Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?
Thank you very much !

In
http://groups.google.co.uk/group/sci.math.numanalysis/browse_frm/thread/81322353885a6d4d
there is some discussion on finding the largest positive eigen value of
a real symmetric matrix.
Ian Smith 

Back to top 


Skunk science forum beginner
Joined: 19 Jul 2006
Posts: 2

Posted: Thu Jul 20, 2006 10:29 am Post subject:
Re: Power Method and negative eigenvalues



Roy Stogner wrote:
Quote:  On Thu, 20 Jul 2006 00:19:11 +0200, Skunk wrote:
Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?
The first idea that comes to mind: if the largest magnitude negative
eigenvalue of A is g, can you use the power method to find the largest
magnitude eigenvalue of (A + gI) then subtract g to get the corresponding
eigenvalue of A?

Roy Stogner

It works ! Simple and effective, many thanks ! 

Back to top 


Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Thu Jul 20, 2006 11:14 am Post subject:
Re: Power Method and negative eigenvalues



In article <44beafcc$0$12612$5402220f@news.sunrise.ch>,
Skunk <skunk@ag.com> writes:
Quote:  Hi,
I implemented the power method algorithm in C++ in order to find the
leading eigenvalue of a real square matrix and its associated eigenvector.
My problem is that this method compute the eigenvalue with the largest
*absolute* value and that i would it to compute the largest *positive*
eigenvalue.
Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?
Thank you very much !

not necessarily the best idea but simple:
with a pure power method code: compute the maxnorm of A
max_i sum_j abs(a(i,j) = N
add N to the diagonal elements of A. Now there are no negative
eigenvalues and the largest positive one is shifted by N to the right.
this might slow down convergence .
or, with inverse iteration: subtract N, use inverse iteration with shift zero
to get the reciprocal of the absolute smallest eigenvalue of the shifted
i.e. 1/(lambda_maxN)
hth
peter 

Back to top 


Arnold Neumaier science forum Guru
Joined: 24 Mar 2005
Posts: 379

Posted: Thu Jul 20, 2006 12:46 pm Post subject:
Re: Power Method and negative eigenvalues



Skunk wrote:
Quote:  Hi,
I implemented the power method algorithm in C++ in order to find the
leading eigenvalue of a real square matrix and its associated eigenvector.
My problem is that this method compute the eigenvalue with the largest
*absolute* value and that i would it to compute the largest *positive*
eigenvalue.
Is there a possiblity to adapt the power method to find the largest
positive eigenvalue ? Any ideas i can explore or should i use another
algorithm ?

Try the Lanczsos algorithm. It is much more efficient than the power method.
Arnold Neumaier 

Back to top 


Google


Back to top 


