Matrices of polynomials

A d \times d matrix whose entries are polynomials of degree less than \ell can be seen as a polynomial of degree less than \ell with matrix coefficients. The two views suggest the two families of fast algorithms: treat the matrix as a big integer matrix (Kronecker substitution) or as a polynomial to be multiplied by evaluation and interpolation, which reduces everything to scalar matrix products. FLINT implements both for fmpz_poly_mat (\mathbb{Z}[x]) and nmod_poly_mat ((\mathbb{Z}/n\mathbb{Z})[x]), and uses fraction-free elimination (Fraction-free elimination) for determinants, ranks and solving. Asymptotically faster algorithms for the latter, based on minimal approximant bases [BL1994; GJV2003], are not implemented. Matrices over gr_poly rings in gr_mat use the generic algorithms of gr_mat.h instead.

Multiplication#

Classical#

fmpz_poly_mat_mul_classical and nmod_poly_mat_mul_classical compute each entry as a sum of k polynomial products, mkn polynomial multiplications in all, with the fast polynomial multiplication of fmpz_poly.h and nmod_poly.h. For 2 \times 2 squares, nmod_poly_mat_sqr_classical uses the formulas (A^2)_{00} = a^2 + bc, (A^2)_{01} = b(a + d) and so on, with five products.

Kronecker substitution#

Substituting x = 2^s for a large enough s turns each polynomial into an integer from which its coefficients can be read off [Kro1882], and turns the matrix product into one integer matrix product.

fmpz_poly_mat_mul_KS packs each entry with fmpz_poly_bit_pack at s = a + b + [\text{signed}] + \lceil \log_2 \min(\ell_A, \ell_B) \rceil + \lceil \log_2 k \rceil bits, multiplies the integer matrices with fmpz_mat_mul, and unpacks. nmod_poly_mat_mul_KS does the same with coefficients in [0, n), so s = 2 \log_2 n + \log_2 \min(\ell_A, \ell_B) + \log_2 k (rounded up), and reduces the unpacked coefficients modulo n. All the multimodular and floating-point machinery of fmpz_mat_mul (Multiplying matrices over the integers) then applies to the packed matrices, whose entries have about \ell s bits.

Evaluation and interpolation#

Over a field with at least \ell_A + \ell_B - 1 elements, the product is determined by its values at that many points. nmod_poly_mat_mul_interpolate evaluates every entry of A and B at the points 0, 1, \ldots, \ell_A + \ell_B - 2 with a subproduct tree (Multipoint evaluation and interpolation), multiplies the \ell_A + \ell_B - 1 pairs of scalar matrices with nmod_mat_mul, and interpolates each entry of the product. This costs O(\ell \, d^\omega) operations modulo n for the products plus O(d^2 M(\ell) \log \ell) for evaluation and interpolation, so the fast matrix products of nmod_mat dominate for large d. It requires n to be a prime at least \ell_A + \ell_B - 1; it throws if n is smaller.

Transformed entries#

nmod_poly_mat_mulmid_fft_small computes a window of coefficients [z_l, z_h) of each entry of AB by transforming every entry of A and B once in the transformed polynomial ring of gr (gr_ctx_init_gr_poly_transformed_repr), built on the small-prime FFT of fft_small.h. Each entry of the product is a sum of k pointwise products in the transformed domain, followed by one inverse transform and Chinese remaindering restricted to the window. The transforms of the mk + kn inputs are computed once instead of mkn times, so for long polynomials the cost is close to (mk + kn + mn) transforms plus mkn pointwise products, the analogue of Transformed entries. The conversions and the output entries are distributed over threads. If the storage for the transforms exceeds the budget of fft_small.h, the product is computed in row and column blocks. The function returns 0 if fft_small is unavailable or no transform plan exists for the accumulation bound.

Choice#

fmpz_poly_mat_mul uses the classical algorithm if any dimension is less than 8 and Kronecker substitution otherwise; fmpz_poly_mat_sqr likewise. nmod_poly_mat_mul, with d the smallest dimension and \ell the smaller of the maximal lengths of the entries of A and B:

Here c = 64, or 32 when n has more than 40 bits, doubled for d = 2. nmod_poly_mat_sqr follows the same rules without the transformed method, with the interpolation threshold d > 80 + \sqrt{\ell}.

Truncated products and powers#

fmpz_poly_mat_mullow and fmpz_poly_mat_sqrlow multiply and truncate entrywise; fmpz_poly_mat_pow and nmod_poly_mat_pow use binary powering, fmpz_poly_mat_pow_trunc binary powering with truncation after each step, and fmpz_poly_mat_prod a balanced product tree of the factors.

Determinants#

By Laplace expansion, the determinant of a d \times d matrix with entries of length at most \ell has degree at most d(\ell - 1), so it is determined by its values at d(\ell - 1) + 1 points.

• For d \le 2 an explicit formula is used, and for 3 \le d \le 14 fraction-free elimination (fmpz_poly_mat_det_fflu, nmod_poly_mat_det_fflu), whose last pivot is the determinant up to the sign of the row permutation; the pivots are chosen of low degree.
• For d \ge 15, fmpz_poly_mat_det_interpolate evaluates the matrix at the integers -\lfloor L/2 \rfloor, \ldots, L = d(\ell - 1) + 1, computes the L integer determinants with fmpz_mat_det, and interpolates with fmpz_poly_interpolate_exact. nmod_poly_mat_det_interpolate evaluates at 0, 1, \ldots, L - 1, uses nmod_mat_det and nmod_poly_interpolate_nmod_vec, and falls back to fraction-free elimination when L exceeds the modulus. Interpolation needs the differences of the points to be invertible, so the modulus should be a prime.

The interpolation method costs L scalar determinants, O(d^{\omega + 1} \ell) operations modulo a prime, against O(d^3) operations on polynomials of degree up to d\ell for fraction-free elimination.

Rank, solving and inverses#

fmpz_poly_mat_rank, fmpz_poly_mat_solve, fmpz_poly_mat_inv, fmpz_poly_mat_rref and fmpz_poly_mat_nullspace, and their nmod_poly_mat analogues, are built on fraction-free elimination over the polynomial ring, with exact polynomial divisions. Solutions and inverses are returned with a polynomial denominator: fmpz_poly_mat_solve(X, den, A, B) gives AX = \mathit{den} \cdot B with \mathit{den} = \pm \det A. By Theorem 1 of Fraction-free elimination all intermediate entries are minors of the input, of degree at most d(\ell - 1), so the cost is O(d^3) multiplications and exact divisions of polynomials of that degree, O(d^3 M(d \ell)) coefficient operations over \mathbb{Z}/n\mathbb{Z}. The rank is the number of pivots.

Use in FLINT#

@misc{flint-doc-algorithms-linear-algebra-polynomial-matrices,
  author       = {{The FLINT team}},
  title        = {{Matrices of polynomials}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/linear-algebra/polynomial-matrices.html},
  note         = {Generated 2026-10-20}
}