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