FLINT3.7.0-dev
/

_nfixed_mat_mul_bound, _nfixed_mat_mul_bound_classical, _nfixed_mat_mul_bound_waksman, _nfixed_mat_mul_bound_strassen, _nfixed_complex_mat_mul_bound

Synopsis#include <flint/nfloat.h>
void _nfixed_mat_mul_bound(double * bound, double * error, slong m, slong n, slong p, double A, double B, slong nlimbs)source
void _nfixed_mat_mul_bound_classical(double * bound, double * error, slong m, slong n, slong p, double A, double B, slong nlimbs)source
void _nfixed_mat_mul_bound_waksman(double * bound, double * error, slong m, slong n, slong p, double A, double B, slong nlimbs)source
void _nfixed_mat_mul_bound_strassen(double * bound, double * error, slong m, slong n, slong p, double A, double B, slong cutoff, slong nlimbs)source
void _nfixed_complex_mat_mul_bound(double * bound, double * error, slong m, slong n, slong p, double A, double B, double C, double D, slong nlimbs)source

For an m×n×pm \times n \times p product at precision nlimbs with entries of AA and BB bounded by A and B, set bound to a bound for all intermediate values of the corresponding algorithm, which must be less than 1 for the computation to be valid, and error to a bound for the output error in ulps. _nfixed_mat_mul_bound follows the algorithm choice of _nfixed_mat_mul. The bounds are nondecreasing in A and B. For complex matrices, the entries are bounded by A+BiA + Bi and C+DiC + Di.

A truncated product of two nn-word numbers has an error of at most 2n−12n - 1 ulps, so the classical algorithm has error at most n(2 nlimbs−1)n(2\,\mathit{nlimbs} - 1) ulps for an inner dimension nn and intermediate values bounded by nABnAB. Waksman's and Strassen's algorithms form sums and differences of entries before multiplying, which increases both the bound on intermediate values (for example by 6⌊n/2⌋(A+B)26\lfloor n/2 \rfloor (A + B)^2 for Waksman) and the error; the fixed-point multiplication scales its inputs down until the bound is below 1.

Cite this page

The FLINT team, “_nfixed_mat_mul_bound, _nfixed_mat_mul_bound_classical, _nfixed_mat_mul_bound_waksman, _nfixed_mat_mul_bound_strassen, _nfixed_complex_mat_mul_bound (nfloat.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nfloat/_nfixed_mat_mul_bound.html (generated 2026-11-02).