FLINT3.7.0-dev
/

nmod_mat_mul_strassen

Synopsis#include <flint/nmod_mat.h>
void nmod_mat_mul_strassen(nmod_mat_t C, const nmod_mat_t A, const nmod_mat_t B)source

Sets C = AB by one level of the Strassen–Winograd algorithm: seven products of half-size blocks, each computed by nmod_mat_mul (which may recurse), and 15 block additions. C must not be aliased with A or B.

The operation schedule is Bodrato's variant [Bodrato2010] arranged as in [DPZ2009], with two temporary matrices of about a quarter of the size of C. Odd dimensions are handled by virtual padding: the blocks are treated as if padded with a zero row or column, which costs no copies. If any dimension is at most 4, nmod_mat_mul is called directly.

AlgorithmStrassen–Winograd multiplicationThe 7-multiplication scheme FLINT uses for large matrix products over \mathbb{Z}/n\mathbb{Z}, with Bodrato's operation sequence, a schedule with two temporaries, and odd dimensions handled by virtual zero padding.

References#

  • [Bodrato2010] Bodrato, Marco : A Strassen-like Matrix Multiplication Suited for Squaring and Higher Power Computation. Proceedings of the ISSAC 2010 München, Germany, 25-28 July, 2010
  • [DPZ2009] J.-G. Dumas, C. Pernet and W. Zhou, "Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm", Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation (ISSAC) (2009), 135-143, https://doi.org/10.1145/1576702.1576713
Cite this page

The FLINT team, “nmod_mat_mul_strassen (nmod_mat.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_mat/nmod_mat_mul_strassen.html (generated 2026-10-20).