{"id":"palomar/PALOMAR-2026-11-21-000018","url":"https://github.com/RBarish-UTokyo/FastGaussianElimination-Lean4/tree/df458a8744e1cbe02cb4ca51f391344a3f11cbb7","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-21-000018-v1.json","repo":"https://github.com/RBarish-UTokyo/FastGaussianElimination-Lean4","tags":["cs.DS","math.NA","msc:68Q25","msc:68W40","msc:65F05","msc:65F50","msc:15A15","msc:05C10"],"score":0,"title":"Strassen's algorithm, inversion in O(M(n)) and nested dissection with fast matrix multiplication, in Lean 4","trust":"high","domain":"cs.DS","source":"palomar","authors":["Robert D. Barish"],"reviews":0,"subject":"cs.DS","summary":"A Lean 4 and Mathlib formalization, in the arithmetic cost model, of fast matrix multiplication and its use in Gaussian elimination. Algorithms are written in a writer monad that charges one unit for every addition, subtraction, negation, multiplication and inversion performed through its primitives; costs are statements about these explicit algorithms, whose definitions are part of the statements. A matrix multiplication algorithm is a counted procedure together with proofs that it computes the product and performs at most M(n) operations on n x n matrices, M monotone. Six theorems are…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-11-21","reactions":{},"formalized":true,"formalizes":[{"title":"Gaussian elimination is not optimal","identifier":"","relationship":"formalizes"},{"title":"Triangular factorization and inversion by fast matrix multiplication","identifier":"","relationship":"adapts"},{"title":"Generalized nested dissection","identifier":"","relationship":"adapts"}]}