matlab — fast matrix multiplication via tensor decomposition over GF(2) (started 2026-10-31)

Idea

A way to multiply matrices with R scalar multiplications = a rank-R decomposition of the matmul tensor T_ over a field. Over GF(2) this is a clean combinatorial object and every candidate is EXACTLY verifiable (reconstruct T, compare). This is literally "new algorithms from new math" (the frame of AlphaTensor 2022 and the Kauers-Moosbauer flip-graph, 2022-2025).

Tools

search.c : simulated annealing on all bits at FIXED rank R, minimise Hamming(reconstruction, T).

              Geometric cooling 2.5*exp(-3 t) finds Strassen <2,2,2>=7 (~1/4000 restarts). Weak method.

flip.c : FLIP-GRAPH (the method that found real records). Terms are rank-1 u|v|w bitmasks (<=64 bit);

              invariant: XOR of all terms == T. A flip rewrites two terms sharing one factor (exact identity,
              rank-preserving); a reduction fires when a flip zeroes a term (rank-1) or duplicates another
              (cancel mod 2, rank-2). Random walk + opportunistic reduction; `RT` env = steps before
              restart-from-best (RT huge = pure long walk, reaches deepest). verify() checks the saved
              decomposition against T (full, exact).

verify.c : standalone check that a hardcoded Strassen reconstructs T exactly (convention sanity). OK.

Validation (exact, verified)

  <2,2,2> -> 7   (Strassen)      MATCHES best known 7
  <3,3,3> -> 23  (Laderman)      MATCHES best known 23, found in <1 s
  <2,2,3> -> 11                  MATCHES best known 11
  <2,3,3> -> 15                  MATCHES best known 15

Plain flip graph plateaus slightly above best known on medium formats:

  <3,3,4> -> 30  (best known 29)   one reduction short
  <3,4,4> -> 40  (best known 38)
  <4,4,4> -> ~49-55 so far (best known GF2 47 = AlphaTensor/KM; Strassen^2 = 49)

Honest standing

The tool is correct and reproduces famous results. Matching the frontier on medium formats needs long walks (running) and, for actual record-BEATING, the symmetry-constrained flip graph (Moosbauer-Poole got <5,5,5>=93) and/or GPU-scale search (Perminov 2026). Beating a world record on this shared CPU box in one session is unlikely; the value is a verified record-search lab + transparent reporting of where each run lands vs. Sedoglavic's catalogue (fmm.univ-lille.fr).

Traps

Never pipe a timed-out search's stderr to tail: SIGTERM drops the buffer and you see nothing.

  Redirect to a file. (Cost me a false "it's broken".)

pkill/pgrep -f matching the binary name kills the orchestrating shell (exit 144). Use pkill -x .
flip2.c (efficiency rewrite) has an index-juggling bug in its local reduction; use flip.c (v1).

Symmetry-constrained flip graph — symflip.c (2026-10-31)

The record-finding trick (Moosbauer-Poole). For SQUARE , with the index convention

  a=(i,k)=i*n+k,  b=(k,j)=k*n+j,  c=(j,i)=j*n+i

the matmul tensor is invariant under the cyclic rotation rho(u,v,w) = (w,u,v) on raw bitmasks. (Verified: build_and_verify builds T in this convention and checks the EXPANDED scheme against it.) We search over rho-INVARIANT schemes, stored as one representative per orbit; the real scheme is the union of expand(rep) = {rep, rho rep, rho^2 rep} (3 terms, or 1 if u==v==w a fixed point). Key fact that makes it correct: a flip on two representatives preserves the expanded sum, because rho is linear (r1+r2 = r1'+r2' => expand(r1)+expand(r2) = expand(r1')+expand(r2')). Reductions remove whole orbits (zero factor, or two reps in the same orbit cancel mod 2). rank = sum(1 if fixed else 3). IMPORTANT fix: partner search must try all 3 rho-rotations of each candidate orbit (else 2/3 of the legal flips are invisible and the walk stalls at ~25 for n=3). Behaviour: symmetry is a CONSTRAINT -> it hurts on tiny formats (n=3 symmetric stalls ~25 vs plain 23) but is the way to search LARGE formats where the unconstrained space is too big. Campaign 2 runs n=4 (target 47), n=5 (target 97/93), n=6 (target 153) symmetric + rectangular plain; logs in sym/.

flip3 — faster + smarter plain flip graph (2026-10-31, "flip3" thread)

flip3.c, usage flip3 n m p seconds seed out.txt [start.txt], env L (plateau length), TGT (stop at rank), EXC/PMAX (max excursion above best / max plus-transitions before reset). Three changes vs flip.c: 1. targeted partner choice (term i, then a j that SHARES a factor) — v1's random pairs were >95% no-ops; 2. MERGE reduction: two terms sharing two factors -> one term (v1 only cancelled exact duplicates); 3. plateau escape by plus-transition abc+a'b'c' = (a^a')bc + a'(b^b')c + a'b'(c^c') (rank+1) after L

   stalled steps; reset to best when the excursion exceeds EXC.

kron.py = Kronecker product of two schemes (v3/strassen2.txt = Strassen⊗Strassen, rank 49, verified). Results (all verify OK):

  <3,3,4> 29 = BEST KNOWN, in 1–22 s (flip.c: 30 after 40 min x 6 cores). L=2000 and L=2e6 both hit.
  <3,4,4> 39 in ~100 s (best known 38; flip.c 40).
  <4,4,4> naive start 52 in 100 s; Strassen² start stays at 49 even with +8 excursions (its factors
          are all distinct -> no flips without plus-transitions). KM reached 47 with far more compute.

Running: v3campaign.sh (1 h, 4 workers) -> v3/c/, tgsend summary. Division of labour with the sibling thread: it does symflip (symmetric n=5/6) and ported (2)+(3) there.

GRENZWERK