Skip to content

The singular value decomposition

Computing with large matrices

Large sparse matrices are too big for elimination, so they are handled by repeating a cheap step. This topic finds the eigenvector of the largest eigenvalue by power iteration, as page ranking does, and solves systems with Jacobi, Gauss–Seidel and conjugate gradients.

Lessons on this topic

Animation: four pages with links 1 to 2 and 3, 2 to 3, 3 to 1 and 2, 4 to 1 and 3; each page has a bar for its share of importance. Damping 0.85. After step 14 the shares are (0.2311, 0.3134, 0.418, 0.0375). They settle on (0.2311, 0.3134, 0.418, 0.0375).Animation: four pages with links 1 to 2 and 3, 2 to 3, 3 to 1 and 2, 4 to 1 and 3; each page has a bar for its share of importance. Damping 0.85. After step 14 the shares are (0.2311, 0.3134, 0.418, 0.0375). They settle on (0.2311, 0.3134, 0.418, 0.0375).

Advanced · 25 minYou are hereRead

Power iteration and ranking pages

Multiply and rescale until a vector settles on the dominant eigenvector, predict how fast it gets there, and rank a small web of pages the same way.

Animation: contour ellipses of the bowl for A = [2 1.6; 1.6 2], from the start (10, −8). Steepest descent, 31 of 31 zig-zag steps drawn. Conjugate gradients, 2 of 2 steps drawn, ending at (0, 0).Animation: contour ellipses of the bowl for A = [2 1.6; 1.6 2], from the start (10, −8). Steepest descent, 31 of 31 zig-zag steps drawn. Conjugate gradients, 2 of 2 steps drawn, ending at (0, 0).

Advanced · 30 minYou are hereRead

Iterative solvers

Solve huge systems by repeated sweeps instead of elimination, see steepest descent zig-zag down a long bowl, and watch conjugate gradients reach the bottom in two steps.

Related topics

Where to go next.

Phasorium

Account

Sign inKeep your place on any device

Subjects

Signal processing
Linear algebra
Probability and statistics
Machine learning

Site

Look