Eight-way block multiplication has a finite execution with its specified effect
ProvedCLRS.MatrixRecursiveAnalysis.block_summaryLet be a natural recursion depth. Suppose outer arrays have valid
allocated row references described by three supplied row-reference functions
in the initial heap. For arbitrary integer stride and block offsets, the
compiled matrix_block call at block size terminates with return value
zero and final heap exactly equal to its mathematical block-effect transformer:
This execution theorem does not require separation of the inputs and output; it tracks the actual sequential heap effect even under aliasing. The separate block-correctness theorem adds the separation and row-distinctness assumptions needed to interpret that effect as an ordinary dot-product contribution.
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.MatrixRecursive.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_MatrixRecursive import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixRecursiveGenerated 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 MatrixRecursiveLibrary MatrixRecursiveLibrary.Algo2LeanGenerated open Algo2LeanCore Algo2LeanGenerated namespace CLRS.MatrixRecursiveAnalysis end CLRS.MatrixRecursiveAnalysis open CLRS.MatrixRecursiveAnalysis set_option maxRecDepth 10000 set_option maxHeartbeats 2000000
theorem CLRS.MatrixRecursiveAnalysis.block_summary (depth : Nat) (heap : Heap) (a b c : CollectionRef)
(ar br cr : Int → SeqRef)
(stride row col inner : Int)
(ha : HasRows heap a ar) (hb : HasRows heap b br) (hc : HasRows heap c cr) :
matrix_block.Call heap (a, b, c, stride, row, col, inner, (2 ^ depth : Nat))
(blockEffect ar br cr stride depth heap row col inner) 0 := by sorry