Added an Algorithm

edit

I added an algorithm to calculate the power iteration in a C program. Comments/Questions? Rankmaniac42 (talk) 03:51, 12 November 2008 (UTC)Reply

In the algorithm, shouldn't you have a b=tmp, instead of r=tmp? You want to update and move away from the initial b values. --76.100.191.59 (talk) 02:59, 24 April 2009 (UTC)Reply

I think there is an error in the algorithm,.
tmp[i] += b[j]*A[j][i];
should be changed to
tmp[i] += b[j]*A[i][j];
Reference in Networkx (python graph library) source code and other code references on the web.
https://networkx.lanl.gov/trac/browser/networkx/trunk/networkx/algorithms/centrality/eigenvector.py
http://adorio-research.org/wordpress/?p=1308
What do you think?--4nT0 (talk) 13:17, 28 August 2010 (UTC)Reply

Should be something like this instead, I think. (See algorithm description on the page for Primary Component Analysis)

   for(i=0; i<n; i++)
        tmp[i] = 0;
   
   for(i=0; i<n; i++)
   {
       bdotx = 0;
       
       for (j=0; j<n; j++)
           bdotx += A[i][j] * b[j];
       
       for (j=0; j<n; j++)
           tmp[i] += bdotx * A[i][j];
   }

Finding the 2nd Eigenvalue

edit

I would like to add the following - please let me know if there are any comments.

In order to find the second eigenvalue, the Power Method can be used on the following matrix:

 

where

 .

The matrix   has the same eigenvectors and eigenvalues as   with the exception that  . To see this we multiply by  

 

for any other eigenvector we have

 

since   and   are orthogonal to each other. --Adieyal 15:05, 5 July 2007 (UTC)Reply

Why are   and   orthogonal to each other? If I understand you correctly,   and   are (normalized) eigenvectors. Eigenvectors of a general matrix are not orthogonal, but eigenvalues of a symmetric matrix (and, more generally, a normal matrix) are. Perhaps you're assuming that A is symmetric? -- Jitse Niesen (talk) 20:48, 6 July 2007 (UTC)Reply

Clearly you're right - I'm not sure why I thought that the matrix was symmetric. Regardless, the above method is still useful for symmetric matrices. --Adieyal 17:50, 29 July 2007 (UTC)Reply

Is this the procedure called deflation? Anyway, feel free to add it in, preferably with a reference. It would be great if you could check the rest of the article and rewrite the parts where you can improve on it. -- Jitse Niesen (talk) 04:12, 30 July 2007 (UTC)Reply

For w2, surely A'w2 should be lambda2 X w2, not lambda1 X w1 since the inner product term disappears, and Aw2=lambda2 X w2 by definition. Sorry about my formatting. —Preceding unsigned comment added by 147.114.226.173 (talk) 12:21, 10 July 2008 (UTC)Reply

The Power Method uses Power Iteration and deflation to try to estimate all eigenvalues and vectors of a matrix of any size, by repeating this step after each eigenpair has been found. I propose that a new article Power Method be made to describe this complete process. (see http://distance-ed.math.tamu.edu/Math640/chapter6/node4.html at the bottom) Also, power iteration can be performed on the inverse of a matrix to find the smallest eigenvector. It is also very widely used in practice for engineering applications when dealing with large matricies. 192.102.214.6 (talk) 12:23, 15 August 2008 (UTC)Reply

Also see http://www.maths.lancs.ac.uk/~gilbert/m306c/node10.html . The term Power Method is also very widely known. 192.102.214.6 (talk) 13:02, 15 August 2008 (UTC)Reply

edit

I think the first reference to http://www4.ncsu.edu/~ipsen/ps/slides_imacs.pdf is broken. Please check. —Preceding unsigned comment added by 81.33.18.197 (talk) 09:31, 4 October 2007 (UTC)Reply

multiple eigenvalues by power method

edit

"However, it will find only one eigenvalue (the one with the greatest absolute value) and it may converge only slowly."


I guess it is a matter of semantics, but this statement is not true for all power methods. It is certainly true for the power method presented in the article, but it is not true for the power method presented in

"Multiple extremal eigenpairs by the power method," Journal of Computational Physics, Volume 227 , Issue 19 (October 2008)

Maybe different names are needed for these slightly different "power methods?" Certainly the statements:

"The power iteration is a very simple algorithm. It does not compute a matrix decomposition, and hence it can be used when A is a very large sparse matrix."

are true for the aforementioned alternate power method.


Nooseweak


The lines:

   for(k=0; k<n; k++){
        norm_factor += tmp[k];
   }

are not calculating a vector norm - just look at the wikipedia definition of a norm. I guess it should mean:

   for(k=0; k<n; k++){
        norm_factor += abs(tmp[k]);
   }

Which would refer to the 1-Norm (Manhattan-Norm)

Konan —Preceding unsigned comment added by 93.134.111.116 (talk) 21:41, 17 May 2011 (UTC)Reply

The code presented is inaccurate

edit

The algorithm illustrated by the code appears to be innacurate. The normalisation of the generated vector (which is the product of the matrix and the previous eigenvector) is done by finding the maximum element in the vector, and not by finding the magnitude of the vector. This does not affect the outcome of the power method in itself, but it can affect the outcome of variations of the power method, such as the Inverse Power Method, the Shifted Power Method, and the Shifted Inverse Power Method.

Sources: > http://math.fullerton.edu/mathews/n2003/PowerMethodMod.html > http://math.bard.edu/greg/math301/NumericalAnalysis.pdf > http://macs.citadel.edu/chenm/344.dir/08.dir/lect4_2.pdf — Preceding unsigned comment added by Krodh (talkcontribs) 12:39, 21 March 2012 (UTC)Reply

Why does the introduction have the assumption that the matrix is diagonalizable?

edit

The proof given in the analysis section does not use this assumption. — Preceding unsigned comment added by 73.42.179.192 (talk) 02:51, 26 November 2020 (UTC)Reply