FLINT3.7.0-dev
/

_flint_mpn_hgcd_matrix_init, _flint_mpn_hgcd_matrix_update_q, _flint_mpn_hgcd_matrix_mul_1, _flint_mpn_hgcd_matrix_mul, _flint_mpn_hgcd_matrix_adjust, _flint_mpn_hgcd_matrix22_mul_strassen_itch, _flint_mpn_hgcd_matrix22_mul_strassen

Synopsis#include <flint/mpn_extras.h>
void _flint_mpn_hgcd_matrix_init(flint_mpn_hgcd_matrix_struct * M, mp_size_t n, mp_ptr p)source
void _flint_mpn_hgcd_matrix_update_q(flint_mpn_hgcd_matrix_struct * M, mp_srcptr qp, mp_size_t qn, unsigned int col, mp_ptr tp)source
void _flint_mpn_hgcd_matrix_mul_1(flint_mpn_hgcd_matrix_struct * M, const flint_mpn_hgcd_matrix1_struct * M1, mp_ptr tp)source
void _flint_mpn_hgcd_matrix_mul(flint_mpn_hgcd_matrix_struct * M, const flint_mpn_hgcd_matrix_struct * M1, mp_ptr tp)source
mp_size_t _flint_mpn_hgcd_matrix_adjust(const flint_mpn_hgcd_matrix_struct * M, mp_size_t n, mp_ptr ap, mp_ptr bp, mp_size_t p, mp_ptr tp)source
mp_size_t _flint_mpn_hgcd_matrix22_mul_strassen_itch(mp_size_t rn, mp_size_t mn)source
void _flint_mpn_hgcd_matrix22_mul_strassen(mp_ptr r0, mp_ptr r1, mp_ptr r2, mp_ptr r3, mp_size_t rn, mp_srcptr m0, mp_srcptr m1, mp_srcptr m2, mp_srcptr m3, mp_size_t mn, mp_ptr tp)source

The matrix operations of the half-GCD, as GMP's mpn_hgcd_matrix_*. _flint_mpn_hgcd_matrix_init initialises MM to the identity for inputs of nn limbs, using FLINT_MPN_HGCD_MATRIX_INIT_ITCH(n) limbs at p. The product and the adjustment ((a,b)←M−1(a,b)(a, b) \gets M^{-1} (a, b) for the low pp limbs of aa and bb) are computed in transform space for large operands (Use in FLINT). _flint_mpn_hgcd_matrix22_mul_strassen is GMP's mpn_matrix22_mul, the classical or a Strassen-like product of 2×22 \times 2 matrices, which the half-GCD uses below the transform-space range; it is not meant as a general 2×22 \times 2 matrix product.

Cite this page

The FLINT team, “_flint_mpn_hgcd_matrix_init, _flint_mpn_hgcd_matrix_update_q, _flint_mpn_hgcd_matrix_mul_1, _flint_mpn_hgcd_matrix_mul, _flint_mpn_hgcd_matrix_adjust, _flint_mpn_hgcd_matrix22_mul_strassen_itch, _flint_mpn_hgcd_matrix22_mul_strassen (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/_flint_mpn_hgcd_matrix_init.html (generated 2026-11-02).