← All Cracked Math projects
PM-A06NOT STARTEDADVANCEDMATHPYTHONIMPACT ★★★☆☆

Lanczos on a two-million-node road network

Watch ghost eigenvalues appear, remove them, then cut California's road graph in half with the Fiedler vector.

EST.28 h
REWARD+400 XP
AFTERSNAP + 1

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Wall time and max residual ||Lv - lambda v|| for k = 100; edge cut of spectral bisection (the number of edges crossing between the halves)
GOAL · All residuals <= 1e-8 within 2x ARPACK wall time; spectral-bisection edge cut within 2x of METIS
scipy.sparse.linalg.eigsh (ARPACK) and METIS edge cut (METIS is the standard graph-partitioning tool) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

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

  1. 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)).
  2. 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.