Ordinary multiplication: completion of the remaining dot-product loop
ProvedCLRS.MatrixMultiplyAnalysis.dot_loopConsider a configuration immediately before the named dot-product loop in the
compiled matrix_dot function. Its local inputs are represented nested matrices
, row , column , upper bound , current index , and accumulator
. Let be a natural number with . Matrix references and all local
values must match the supplied configuration; the inputs may share storage.
Then the remaining call has a finite completion with return value
Its final heap is the initial heap with exactly added to multiply_add;
every other heap component is unchanged. The sum is empty when .
This is a local loop contract, requiring the named location and the stated
local-variable observations but not a separate reachability assumption.
Platform namespace. The imported Chapter 4 source declarations live under CLRS in this upload to avoid collisions with independently published compiler versions. The immutable source reference retains the original declaration names.
Catalog organization (2026-10-11). This record was retired from the active Chapter 4 catalog to focus the presentation on three algorithms and four reusable recurrence results. Its mathematical statement and proof status are unchanged, and existing imports and links remain valid. The retained results are CLRS.Chapter4Publication.MatrixMultiply.correctness_and_running_time. Supporting lemmas needed by the retained results are included in their accepted proof files.
import Definitions.Def_CLRS_Chapter4_Algo2Lean import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixMultiply 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 end CLRS open CLRS open MatrixMultiplyLibrary MatrixMultiplyLibrary.Algo2LeanGenerated open Algo2LeanCore Algo2LeanGenerated open Algo2LeanCore.MatrixHeap namespace CLRS.MatrixMultiplyAnalysis end CLRS.MatrixMultiplyAnalysis open CLRS.MatrixMultiplyAnalysis
theorem CLRS.MatrixMultiplyAnalysis.dot_loop (count : Nat) (state : Configuration)
(a b : CollectionRef) (av bv : Values) (n row column first total : Int)
(location : matrix_dot.At.dot_loop state)
(ra : matrix_dot.Local.a state = some a)
(rb : matrix_dot.Local.b state = some b)
(rn : matrix_dot.Local.n state = some n)
(rr : matrix_dot.Local.row state = some row)
(rc : matrix_dot.Local.column state = some column)
(rk : matrix_dot.Local.k state = some first)
(rt : matrix_dot.Local.total state = some total)
(bound : n = first + (count : Int))
(va : Stored state.heap a av) (vb : Stored state.heap b bv) :
matrix_dot.CallFrom state (state.heap.tick "multiply_add" count)
(total + dotFrom av bv row column first count) := by sorry