FLINT3.7.0-dev
/

gr_mat_gr_poly_solve_lode_newton, _gr_mat_gr_poly_solve_lode_newton, _gr_mat_gr_poly_solve_lode_newton_start, _gr_mat_gr_poly_solve_lode_newton_step

Synopsis#include <flint/gr_mat.h>
int gr_mat_gr_poly_solve_lode_newton(gr_mat_t Y, const gr_mat_t A_numerator, const gr_poly_t A_denominator, const gr_mat_t Y0, slong len, gr_ctx_t A_poly_ctx, gr_ctx_t sol_poly_ctx)source
int _gr_mat_gr_poly_solve_lode_newton(gr_mat_t Y, gr_mat_t Z, const gr_mat_t A_numerator, const gr_poly_t A_denominator, const gr_mat_t Y0, slong len, gr_ctx_t A_poly_ctx, gr_ctx_t sol_poly_ctx)source
int _gr_mat_gr_poly_solve_lode_newton_start(gr_mat_t Y, gr_mat_t Z, gr_poly_t A_denominator_inv, const gr_mat_t A_numerator, const gr_poly_t A_denominator, const gr_mat_t Y0, gr_ctx_t sol_poly_ctx)source
int _gr_mat_gr_poly_solve_lode_newton_step(gr_mat_t Y, gr_mat_t Z, gr_poly_t A_denominator_inv, slong len, const gr_mat_t A_numerator, const gr_poly_t A_denominator, int A_is_companion, gr_ctx_t sol_poly_ctx)source

Solve the system of linear differential equations Y'(t) = A(t) Y(t) with Y(0) = Y_0, where A(t) is a matrix of rational functions given by a matrix of polynomials A_numerator (over the polynomial ring A_poly_ctx) and a common denominator A_denominator with nonzero constant term, and set Y to the power series solution truncated to length len. The entries of Y are polynomials over the ring sol_poly_ctx.

The algorithm is the Newton iteration of Bostan, Chyzak, Ollivier, Salvy, Schost and Sedoglavic [BCOSSS2007], which doubles the precision of Y and of an approximation Z of Y^{-1} at each step, combined with a Newton iteration for the power series inverse of the denominator and a dedicated multiplication by A(t) \bmod t^m when A is a companion matrix. The precisions follow an optimal sequence ending at len, which need not be a power of two. The start and step functions perform the initialisation and one step to length len (A_is_companion selects the companion matrix multiplication), for callers that drive the iteration themselves.

References#

  • [BCOSSS2007] A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, É. Schost, A. Sedoglavic. "Fast computation of power series solutions of systems of differential equations". Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2007) 1012-1021
Cite this page

The FLINT team, “gr_mat_gr_poly_solve_lode_newton, _gr_mat_gr_poly_solve_lode_newton, _gr_mat_gr_poly_solve_lode_newton_start, _gr_mat_gr_poly_solve_lode_newton_step (gr_mat.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_mat/gr_mat_gr_poly_solve_lode_newton.html (generated 2026-10-20).