← All Cracked Math projects
PM-B05NOT STARTEDBEGINNERMATHPYTHONIMPACT ★★☆☆☆

Gaussian elimination that breaks on purpose

Write three LU solvers, then build the matrices that break each one.

EST.6 h
REWARD+200 XP
AFTERoriginal

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Normwise backward error ||Ax - b|| / (||A|| ||x||) on 4 matrix families, n = 50..1000 (roughly, how much you would have to change the problem for your answer to be exact); growth factor (how much the entries grow during elimination)
GOAL · Partial-pivot backward error within 10x of LAPACK on all families. Growth factor 2^(n-1) reproduced exactly for n <= 60. Run time <= 20x LAPACK's at n = 1000.
numpy.linalg.solve (LAPACK getrf/getrs) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

LU factorisation is Gaussian elimination written as A = LU, a lower-triangular matrix times an upper-triangular one. Pivoting means swapping rows (partial pivoting) or rows and columns (complete pivoting) so you never divide by a tiny number. Implement LU with no pivoting, partial pivoting and complete pivoting, using vectorised row operations. From the factorisation, derive det, log|det|, numerical rank (how many independent directions the matrix really has, once rounding is taken into account) and a null-space basis (vectors the matrix sends to zero). Then construct adversarial inputs that break each variant: tiny pivots, Wilkinson's 2^(n-1) growth-factor matrix (a matrix whose entries double at every elimination step even with partial pivoting), and near-singular Hilbert matrices. Explain each failure.

VICTORY CONDITIONS

  1. Partial-pivot backward error within 10x of LAPACK on all families. Growth factor 2^(n-1) reproduced exactly for n <= 60. Run time <= 20x LAPACK's at n = 1000. (Normwise backward error ||Ax - b|| / (||A|| ||x||) on 4 matrix families, n = 50..1000 (roughly, how much you would have to change the problem for your answer to be exact); growth factor (how much the entries grow during elimination)).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Pivoting
Reordering rows (and possibly columns) during elimination so that the number you divide by is as large as possible.
Backward error
The size of the smallest change to the input problem that would make your computed answer exactly correct.
Growth factor
The ratio between the largest entry that appears during elimination and the largest entry of the original matrix; large growth means large rounding errors.
Hilbert matrix
A matrix with entries 1/(i+j-1) that is almost singular, so tiny rounding errors produce huge errors in the solution.

Why it rates ★★☆☆☆

Textbook material. The adversarial cases are what show you understand stability rather than just reciting it.