Skip to content

jgdumas/Fast-Matrix-Multiplication

Repository files navigation


Fast-Matrix-Multiplication

Accuracy of Fast matrix multiplication Algorithms via 2x2 recursion


Authors: Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic

About: This is a Fork of the Complex-Matrix-Multiplication repository, created for the numerical experiments of the paper:


FMM-matlab-benchmarks, Accuracy benchmarks with Matlab:

Program Growth Factor Description
strassenw.m 17.8530 original Winograd's algorithm
strassen.m 14.8284 original Strassen's algorithm
DPS_evenpow.m 12.2034 using only powers of 2
DPS_smallrat.m 12.2034 small rational coefficients
DPS_intermediate.m 12.0695 fast rational
DPS_integral.m 12.0662 large rational coefficients
DPS.m 12.0660 most accurate, with sqrt(3)

Faster Algorithms, Faster variants, using an alternative basis from:

Program Complexity bound Description
Strassen_aternative.m $5n^{\log_2(7)}$ Strassen's algorithm, sparsified
Winograd_aternative.m $5n^{\log_2(7)}$ Winograd's algorithm, sparsified
DPS_aternative.m $5n^{\log_2(7)}$ DPS's algorithm, sparsified

All "aternative" variants use left/right and inverse change of basis (*CoB* files) together with an inner sparse multiplication (*mul* files).

Benchmarks, Accuracy comparison with symbolic matrix multiplication:

  • accuracy_2x2_real.m: comparing algorithms accuracy
  • accuracy_alternative_real.m: comparing alternative change of basis
  • gallery_alternative_real.m: change of basis on large condition number

FMM-plinopt-codegen, Progam generation via the PLinOpt library:

Command-line scritps generating optimized matlab programs.

Examples: DPS.plo, DPS_evenpow.plo, DPS_smallrat.plo, DPS_intermediate.plo, DPS_integral.plo, DPS_CoB.plo.

  • PLinOpt library: Routines handling linear, bilinear & trilinear programs.

FMM-maple-proofs, Proofs of accuracy bounds in Maple:

  • Minimal2Norm: Proof of the Frobenius norm minimal point of Fast Matrix Multiplication in Strassen's orbit
  • LowerBoundGamma: Proof of a lower bound on the growth factor of Fast Matrix Multiplication in Strassen's orbit