Brief
Lanczos finds a few eigenvalues of a huge sparse symmetric matrix by building a small tridiagonal matrix from repeated matrix-vector products. In floating point its basis vectors slowly stop being orthogonal, which creates ghost eigenvalues (spurious duplicate copies of real ones). Implement Lanczos with full, selective and no reorthogonalisation (making the basis vectors perpendicular again always, only when needed, or never). Add thick restarts (restart while keeping the best vectors found so far, to limit memory) and shift-invert (solve systems with L - sigma I to target eigenvalues near sigma) via your I08 PCG. Compute the 100 smallest eigenpairs of the graph Laplacian (degree matrix minus adjacency matrix; its smallest eigenvectors reveal cluster structure) of SNAP roadNet-CA (1,965,206 nodes, 2,766,607 edges). Document ghost eigenvalues when reorthogonalisation is off. Use the Fiedler vector (the eigenvector of the second-smallest eigenvalue) for recursive spectral bisection: split the nodes by the sign of the vector, then repeat on each half.
VICTORY CONDITIONS
- All residuals <= 1e-8 within 2x ARPACK wall time; spectral-bisection edge cut within 2x of METIS (Wall time and max residual ||Lv - lambda v|| for k = 100; edge cut of spectral bisection (the number of edges crossing between the halves)).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- Lanczos algorithm
- An iterative method that approximates the extreme eigenvalues of a large symmetric matrix using only matrix-vector products.
- Ghost eigenvalues
- Spurious repeated copies of already-found eigenvalues that appear when Lanczos vectors lose orthogonality through rounding.
- Reorthogonalisation
- Explicitly removing the components of new Lanczos vectors along earlier ones, to undo the loss of orthogonality.
- Graph Laplacian
- The degree matrix minus the adjacency matrix; its eigenvectors with small eigenvalues vary slowly across well-connected regions.
- Fiedler vector
- The eigenvector of the Laplacian's second-smallest eigenvalue; splitting nodes by its sign gives a good cut of the graph.
- Shift-invert
- Running the eigensolver on (L - sigma I)^-1, which turns eigenvalues near sigma into the largest ones so they converge fast.
Why it rates ★★★☆☆
Hard-won Krylov intuition at real scale (Krylov methods are the family Lanczos and CG belong to). It is the backbone of W02, W06 and W07.