Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Value and heap-effect specifications for ordinary matrix multiplication

Definition
CLRS_Chapter4_Algo2LeanExamples_MatrixMultiply

by Chutong · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgo2lean-clrs-chapter4-fd33cf9algorithmsclrsrunning-timetextbook

This bundle supplies the mathematical value functions, allocation and heap-effect transformers, exact counter vectors, and local invariants used to analyze ordinary matrix multiplication. It retains the source-facing generated call relations. Substantial execution, matrix-correctness and runtime proofs are separate theorem nodes. Inputs contain arbitrary unbounded integers and may share row references; specific separation hypotheses are stated by the lemmas that need them. The measured cost is explicit source ticks, excluding uncharged allocation, bookkeeping and integer bit complexity.

Formalization Note. This content is transcribed from Algo2Lean development snapshot fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41, with explicit platform import and namespace adaptation. It is not attributed to public compiler v0.1.4. The submitted definition bundle must be checked without unfinished-proof assumptions.

Definition code
import Definitions.Def_CLRS_Chapter4_Algo2Lean
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixMultiplyGenerated
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixMultiplyPoints
import Definitions.Def_CLRS_Chapter4_Algo2LeanLib_MatrixHeap
import Std

set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true

namespace CLRS

open MatrixMultiplyLibrary MatrixMultiplyLibrary.Algo2LeanGenerated

/-!
CLRS 4.1 on genuine arrays of row arrays. The inputs may share rows, including
with each other. A fresh row is allocated for every output row. The proof
constructs terminating executions and proves preservation of all pre-existing
objects, the mathematical matrix product, and exactly n³ scalar multiply-adds.
-/
open Algo2LeanCore Algo2LeanGenerated
open Algo2LeanCore.MatrixHeap

namespace MatrixMultiplyAnalysis

/-- The finite row-by-column sum, at arbitrary integer coordinates. -/
def dotFrom (a b : Values) (row column first : Int) : Nat → Int
  | 0 => 0
  | count + 1 => a row first * b first column + dotFrom a b row column (first + 1) count

def entry (a b : Values) (n : Nat) (row column : Int) : Int :=
  dotFrom a b row column 0 n

/-- Both coordinates outside the finite square have value zero. -/
def product (a b : Values) (n : Nat) : Values :=
  fun row column => if 0 ≤ row ∧ row < n ∧ 0 ≤ column ∧ column < n
    then entry a b n row column else 0

/-- Consecutive writes of a mathematical row to one fresh output object. -/
def fill (h : Heap) (r : SeqRef) (values : Seq) (first : Int) : Nat → Heap
  | 0 => h
  | count + 1 => fill (h.write r first (values first)) r values (first + 1) count



























/-- The completed fresh row and its exact cost. -/
def rowHeap (h : Heap) (av bv : Values) (n : Nat) (row : Int) : Heap :=
  (fill (h.allocate (fun _ => 0)) h.nextRef (entry av bv n row) 0 n).tick
    "multiply_add" (n * n)

def rowValues (av bv : Values) (n : Nat) (row : Int) : Seq :=
  fun column => if 0 ≤ column ∧ column < n then entry av bv n row column else 0















/-- The prefix of rows already completed by the outer loop. -/
def partialProduct (av bv : Values) (n : Nat) (limit : Int) : Values :=
  fun row column => if 0 ≤ row ∧ row < limit then rowValues av bv n row column else 0







/-- Each completed row has its own consecutive fresh identity. -/
def RowReferences (h : Heap) (result : CollectionRef) (base count : Nat) : Prop :=
  ∀ i : Nat, i < count → rows.get h result i = some (base + i)



def costs (n : Nat) : Clocks := Clocks.single "multiply_add" (n ^ 3)











-- Main result: Correctness






-- Main result: Running time




end MatrixMultiplyAnalysis

end CLRS
Source
Algo2Lean Chapter 4 development, module Algo2LeanExamples.MatrixMultiply, immutable source fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41: https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/examples/matrix_multiply.algo; https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/examples/analysis/matrix_multiply.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me