FLINT3.7.0-dev
/

nmod_poly_evaluate_mat, nmod_poly_evaluate_mat_horner, nmod_poly_evaluate_mat_paterson_stockmeyer

Synopsis#include <flint/nmod_poly.h>
void nmod_poly_evaluate_mat(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c)source
void nmod_poly_evaluate_mat_horner(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c)source
void nmod_poly_evaluate_mat_paterson_stockmeyer(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c)source

Set dest to the matrix \mathit{poly}(c), for a square matrix c with the modulus of poly; dest must have the same dimensions and may be c. The Horner version uses \deg(\mathit{poly}) matrix multiplications, the Paterson–Stockmeyer version [PS1973] about 2\sqrt{\deg} matrix multiplications and O(\deg) scalar multiply-adds. nmod_poly_evaluate_mat uses Horner's rule if \mathit{len} < 5 or \mathit{len} \cdot r < 425 for an r \times r matrix, and Paterson–Stockmeyer otherwise.

The characteristic and minimal polynomials of c, which vanish at c, are computed by nmod_mat_charpoly and nmod_mat_minpoly (Computing characteristic and minimal polynomials).

References#

  • [PS1973] M. S. Paterson and L. J. Stockmeyer, "On the number of nonscalar multiplications necessary to evaluate polynomials", SIAM J. Comput (1973)
Cite this page

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