FLINT3.7.0-dev
/

nmod_mat_solve_tril_right_recursive, nmod_mat_solve_triu_right_recursive

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

Splits LL (or UU) into blocks of ⌊r/2⌋\lfloor r/2 \rfloor and ⌈r/2⌉\lceil r/2 \rceil rows and columns and solves recursively, reducing the work to matrix multiplications.

For lower triangular LL, the block formula is

(XY)(A0CD)−1=((X−YD−1C)A−1YD−1),\begin{pmatrix} X & Y \end{pmatrix} \begin{pmatrix} A & 0 \\ C & D \end{pmatrix}^{-1} = \begin{pmatrix} (X - Y D^{-1} C) A^{-1} & Y D^{-1} \end{pmatrix},

and for upper triangular UU

(XY)(AB0D)−1=(XA−1(Y−XA−1B)D−1).\begin{pmatrix} X & Y \end{pmatrix} \begin{pmatrix} A & B \\ 0 & D \end{pmatrix}^{-1} = \begin{pmatrix} X A^{-1} & (Y - X A^{-1} B) D^{-1} \end{pmatrix}.

The update of the right-hand side uses nmod_mat_submul and the two half-size systems use nmod_mat_solve_tril_right (nmod_mat_solve_triu_right), which recurses or switches to substitution.

Cite this page

The FLINT team, “nmod_mat_solve_tril_right_recursive, nmod_mat_solve_triu_right_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_right_recursive.html (generated 2026-11-02).