Mathematics
The Power Method for Finding Dominant Eigenvalues
Quick fact
The power method is so simple it can be written in a few lines of code, yet it is the engine behind Google's original PageRank algorithm, which ranks web pages by repeatedly multiplying a vector by a huge matrix.
Why this is interesting
Ever wondered how Google ranks billions of web pages in milliseconds? The answer lies in a surprisingly simple mathematical trick called the power method.
Read the full explanation
Understanding The Power Method for Finding Dominant Eigenvalues
Imagine you have a list of numbers (a vector) and a rule (a matrix) that transforms one list into another. The power method asks what happens if you apply this rule over and over, each time rescaling the list so its largest entry becomes 1. In many cases, after many repetitions, the list settles down into a pattern that points in the direction of a special vector called an eigenvector. The amount by which the rule amplified the vector is the associated eigenvalue. This repeated application and rescaling is the power method. It is like repeatedly stretching a piece of dough in the same way; eventually it takes on a shape determined by the most dominant stretching direction.
A deeper explanation
The power method works because each application of a matrix to a vector can be seen as a combination of its eigenvectors, with the dominant eigenvector (the one with the largest magnitude eigenvalue) growing faster than the others. After many iterations, the contributions from non-dominant eigenvectors decay relative to the dominant one, leaving a vector increasingly aligned with the dominant eigenvector. The scaling step (normalizing) prevents overflow, and the ratio of a component of the new vector to the corresponding component of the old vector approaches the dominant eigenvalue. This converges linearly, with a rate determined by the ratio of the second-largest and largest eigenvalues. Because it requires only matrix-vector products, the power method is extremely efficient for large sparse matrices, making it a cornerstone of computational linear algebra and the basis for Google's PageRank algorithm.