FLINT3.7.0-dev

nmod_mat_solve_tril_right_classical, nmod_mat_solve_triu_right_classical

Synopsis#include <flint/nmod_mat.h>
void nmod_mat_solve_tril_right_classical(nmod_mat_t X, const nmod_mat_t L, const nmod_mat_t B, int unit)source
void nmod_mat_solve_triu_right_classical(nmod_mat_t X, const nmod_mat_t U, const nmod_mat_t B, int unit)source

Substitution, for an r×rr \times r triangular matrix, with three methods. If BB has at least max⁡(6,r/4)\max(6, r/4) rows (max⁡(6,r/2)\max(6, r/2) for n>231n > 2^{31}, or n>215n > 2^{15} with 32-bit words), as nmod_mat_solve_tril_classical (nmod_mat_solve_triu_classical) with delayed reductions on the transposed system, BB being transposed by blocks of 256 rows. Otherwise, if r≤128r \le 128 (r≤64r \le 64 for these larger moduli) or BB has at most 4 rows, each row xx of XX is computed from the last entry to the first for LL (from the first to the last for UU): once xjx_j is known, xjx_j times the row jj of the triangular matrix is added to the unreduced sums of the remaining entries, each reduced once. Otherwise (a large triangular matrix and a few rows), each entry is computed with one dot product and one reduction, the columns of the triangular matrix being copied to rows 64 at a time so that the dot products read contiguous memory. The inverses of the diagonal entries are computed once.

Cite this page

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