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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-21 Formalized: true Formalizes: title=Gaussian elimination is not optimal identifier= relationship=formalizes Formalizes: title=Triangular factorization and inversion by fast matrix multiplication identifier= relationship=adapts Formalizes: title=Generalized nested dissection identifier= relationship=adapts Page: https://delphi.science/r/palomar/PALOMAR-2026-11-21-000018 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…