FLINT3.7.0-dev
/

_nfixed_mat_mul, _nfixed_mat_mul_classical, _nfixed_mat_mul_classical_precise, _nfixed_mat_mul_waksman, _nfixed_mat_mul_strassen

Synopsis#include <flint/nfloat.h>
void _nfixed_mat_mul(nn_ptr C, nn_srcptr A, nn_srcptr B, slong m, slong n, slong p, slong nlimbs)source
void _nfixed_mat_mul_classical(nn_ptr C, nn_srcptr A, nn_srcptr B, slong m, slong n, slong p, slong nlimbs)source
void _nfixed_mat_mul_classical_precise(nn_ptr C, nn_srcptr A, nn_srcptr B, slong m, slong n, slong p, slong nlimbs)source
void _nfixed_mat_mul_waksman(nn_ptr C, nn_srcptr A, nn_srcptr B, slong m, slong n, slong p, slong nlimbs)source
void _nfixed_mat_mul_strassen(nn_ptr C, nn_srcptr A, nn_srcptr B, slong m, slong n, slong p, slong cutoff, slong nlimbs)source

Set the m \times p matrix C to the product of the m \times n matrix A and the n \times p matrix B (dense, row-major). The classical version uses the dot products; the _precise version computes with one extra word and is intended for testing. Waksman's algorithm [Waksman1970] halves the number of multiplications at the cost of more additions, which pays off from about 9 words. Strassen's algorithm [Str1969] recurses down to cutoff (a negative value selects the default). _nfixed_mat_mul chooses: Strassen for dimensions above about 26 to 57 (depending on the precision and parity), otherwise Waksman or classical.

References#

  • [Waksman1970] Waksman, Abraham, "On Winograd's algorithm for inner products", IEEE Transactions on Computers 19.04 (1970): 360-361.
  • [Str1969] V. Strassen, "Gaussian elimination is not optimal", Numerische Mathematik 13 (1969), 354-356, https://doi.org/10.1007/BF02165411
Cite this page

The FLINT team, “_nfixed_mat_mul, _nfixed_mat_mul_classical, _nfixed_mat_mul_classical_precise, _nfixed_mat_mul_waksman, _nfixed_mat_mul_strassen (nfloat.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nfloat/_nfixed_mat_mul.html (generated 2026-10-20).