nmod_mat_solve_tril_recursive, nmod_mat_solve_triu_recursive
Synopsis
#include <flint/nmod_mat.h>void nmod_mat_solve_tril_recursive(nmod_mat_t X, const nmod_mat_t L, const nmod_mat_t B, int unit)sourcevoid nmod_mat_solve_triu_recursive(nmod_mat_t X, const nmod_mat_t U, const nmod_mat_t B, int unit)sourceSplits L (or U) into blocks of \lfloor r/2 \rfloor and \lceil r/2 \rceil rows and solves recursively, reducing the work to matrix multiplications.
For lower triangular L, the block formula is
\begin{pmatrix} A & 0 \\ C & D \end{pmatrix}^{-1}
\begin{pmatrix} X \\ Y \end{pmatrix} =
\begin{pmatrix} A^{-1} X \\ D^{-1} ( Y - C A^{-1} X ) \end{pmatrix},
and for upper triangular U
\begin{pmatrix} A & B \\ 0 & D \end{pmatrix}^{-1}
\begin{pmatrix} X \\ Y \end{pmatrix} =
\begin{pmatrix} A^{-1} (X - B D^{-1} Y) \\ D^{-1} Y \end{pmatrix}.
The update of the right-hand side uses nmod_mat_submul and the two half-size systems use nmod_mat_solve_tril (nmod_mat_solve_triu), which recurses or switches to substitution.
Cite this page
The FLINT team, “nmod_mat_solve_tril_recursive, nmod_mat_solve_triu_recursive (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_recursive.html (generated 2026-10-20).
@misc{flint-doc-nmod-mat-nmod-mat-solve-tril-recursive,
author = {{The FLINT team}},
title = {{nmod\_mat\_solve\_tril\_recursive, nmod\_mat\_solve\_triu\_recursive (nmod\_mat.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/nmod_mat/nmod_mat_solve_tril_recursive.html},
note = {Generated 2026-10-20}
}