![]() |
This file implements functions for fast multiplication and division with remainder. More...
#include "debug.h"#include "config.h"#include "canonicalform.h"#include "facMul.h"#include "cf_util.h"#include "templates/ftmpl_functions.h"#include <NTL/lzz_pEX.h>#include "NTLconvert.h"#include "FLINTconvert.h"Go to the source code of this file.
This file implements functions for fast multiplication and division with remainder.
Nomenclature rules: kronSub* -> plain Kronecker substitution reverseSubst* -> reverse Kronecker substitution kronSubRecipro* -> reciprocal Kronecker substitution as described in D. Harvey "Faster polynomial multiplication via multipoint Kronecker substitution"
Definition in file facMul.cc.
| CanonicalForm divFLINTQ | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G | ||
| ) |
Definition at line 170 of file facMul.cc.
| CanonicalForm divNTL | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const modpk & | b = modpk() |
||
| ) |
division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked
| [in] | F | a univariate poly |
| [in] | G | a univariate poly |
| [in] | b | coeff bound |
Definition at line 850 of file facMul.cc.
| void divrem | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| CanonicalForm & | Q, | ||
| CanonicalForm & | R, | ||
| const CFList & | MOD | ||
| ) |
division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
| [in] | F | multivariate, compressed polynomial |
| [in] | G | multivariate, compressed polynomial |
| [in,out] | Q | dividend |
| [in,out] | R | remainder, degree (R, 1) < degree (G, 1) |
| [in] | MOD | only contains powers of Variables of level higher than 1 |
Definition at line 3583 of file facMul.cc.
| void divrem2 | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| CanonicalForm & | Q, | ||
| CanonicalForm & | R, | ||
| const CanonicalForm & | M | ||
| ) |
division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
| [in] | F | bivariate, compressed polynomial |
| [in] | G | bivariate, compressed polynomial |
| [in,out] | Q | dividend |
| [in,out] | R | remainder, degree (R, 1) < degree (G, 1) |
| [in] | M | power of Variable (2) |
Definition at line 3516 of file facMul.cc.
|
inlinestatic |
Definition at line 3376 of file facMul.cc.
|
inlinestatic |
Definition at line 3447 of file facMul.cc.
| void kronSubFp | ( | nmod_poly_t | result, |
| const CanonicalForm & | A, | ||
| int | d | ||
| ) |
| void kronSubFq | ( | fq_nmod_poly_t | result, |
| const CanonicalForm & | A, | ||
| int | d, | ||
| const fq_nmod_ctx_t | fq_con | ||
| ) |
Definition at line 1138 of file facMul.cc.
| void kronSubQa | ( | fmpz_poly_t | result, |
| const CanonicalForm & | A, | ||
| int | d | ||
| ) |
Definition at line 42 of file facMul.cc.
| void kronSubQa | ( | fmpz_poly_t | result, |
| const CanonicalForm & | A, | ||
| int | d1, | ||
| int | d2 | ||
| ) |
Definition at line 1220 of file facMul.cc.
| void kronSubReciproFp | ( | nmod_poly_t | subA1, |
| nmod_poly_t | subA2, | ||
| const CanonicalForm & | A, | ||
| int | d | ||
| ) |
| void kronSubReciproFq | ( | fq_nmod_poly_t | subA1, |
| fq_nmod_poly_t | subA2, | ||
| const CanonicalForm & | A, | ||
| int | d, | ||
| const fq_nmod_ctx_t | fq_con | ||
| ) |
Definition at line 1296 of file facMul.cc.
| void kronSubReciproQ | ( | fmpz_poly_t | subA1, |
| fmpz_poly_t | subA2, | ||
| const CanonicalForm & | A, | ||
| int | d | ||
| ) |
Definition at line 1341 of file facMul.cc.
| CanonicalForm mod | ( | const CanonicalForm & | F, |
| const CFList & | M | ||
| ) |
reduce F modulo elements in M.
| [in] | F | compressed polynomial |
| [in] | M | list containing only univariate polynomials |
Definition at line 2939 of file facMul.cc.
| CanonicalForm modFLINTQ | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G | ||
| ) |
Definition at line 188 of file facMul.cc.
| CanonicalForm modNTL | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const modpk & | b = modpk() |
||
| ) |
mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked
| [in] | F | a univariate poly |
| [in] | G | a univariate poly |
| [in] | b | coeff bound |
Definition at line 676 of file facMul.cc.
| CanonicalForm mulFLINTQ | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G | ||
| ) |
Definition at line 129 of file facMul.cc.
| CanonicalForm mulFLINTQa | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const Variable & | alpha | ||
| ) |
Definition at line 99 of file facMul.cc.
| CanonicalForm mulFLINTQaTrunc | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const Variable & | alpha, | ||
| int | m | ||
| ) |
Definition at line 206 of file facMul.cc.
| CanonicalForm mulFLINTQTrunc | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| int | m | ||
| ) |
Definition at line 237 of file facMul.cc.
| CanonicalForm mulMod | ( | const CanonicalForm & | A, |
| const CanonicalForm & | B, | ||
| const CFList & | MOD | ||
| ) |
Karatsuba style modular multiplication for multivariate polynomials.
| [in] | A | multivariate, compressed polynomial |
| [in] | B | multivariate, compressed polynomial |
| [in] | MOD | only contains powers of Variables of level higher than 1 |
Definition at line 2947 of file facMul.cc.
| CanonicalForm mulMod2 | ( | const CanonicalForm & | A, |
| const CanonicalForm & | B, | ||
| const CanonicalForm & | M | ||
| ) |
Karatsuba style modular multiplication for bivariate polynomials.
| [in] | A | bivariate, compressed polynomial |
| [in] | B | bivariate, compressed polynomial |
| [in] | M | power of Variable (2) |
Definition at line 2853 of file facMul.cc.
| CanonicalForm mulMod2FLINTFp | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M | ||
| ) |
Definition at line 1995 of file facMul.cc.
| CanonicalForm mulMod2FLINTFpReci | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M | ||
| ) |
Definition at line 1957 of file facMul.cc.
| CanonicalForm mulMod2FLINTFq | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M, | ||
| const Variable & | alpha, | ||
| const fq_nmod_ctx_t | fq_con | ||
| ) |
Definition at line 2069 of file facMul.cc.
| CanonicalForm mulMod2FLINTFqReci | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M, | ||
| const Variable & | alpha, | ||
| const fq_nmod_ctx_t | fq_con | ||
| ) |
Definition at line 2027 of file facMul.cc.
| CanonicalForm mulMod2FLINTQ | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M | ||
| ) |
Definition at line 2139 of file facMul.cc.
| CanonicalForm mulMod2FLINTQa | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M | ||
| ) |
Definition at line 2199 of file facMul.cc.
| CanonicalForm mulMod2FLINTQReci | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M | ||
| ) |
Definition at line 2102 of file facMul.cc.
| CanonicalForm mulMod2NTLFq | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M | ||
| ) |
Definition at line 2793 of file facMul.cc.
| CanonicalForm mulNTL | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const modpk & | b = modpk() |
||
| ) |
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f).
| [in] | F | a univariate poly |
| [in] | G | a univariate poly |
| [in] | b | coeff bound |
Definition at line 407 of file facMul.cc.
| void newtonDiv | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| CanonicalForm & | Q | ||
| ) |
Definition at line 376 of file facMul.cc.
| CanonicalForm newtonDiv | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| const CanonicalForm & | M | ||
| ) |
division of F by G wrt Variable (1) modulo M using Newton inversion
| [in] | F | bivariate, compressed polynomial |
| [in] | G | bivariate, compressed polynomial which is monic in Variable (1) |
| [in] | M | power of Variable (2) |
Definition at line 3180 of file facMul.cc.
| void newtonDivrem | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| CanonicalForm & | Q, | ||
| CanonicalForm & | R | ||
| ) |
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)
| [in] | F | univariate poly |
| [in] | G | univariate poly |
| [in,out] | Q | quotient |
| [in,out] | R | remainder |
Definition at line 342 of file facMul.cc.
| void newtonDivrem | ( | const CanonicalForm & | F, |
| const CanonicalForm & | G, | ||
| CanonicalForm & | Q, | ||
| CanonicalForm & | R, | ||
| const CanonicalForm & | M | ||
| ) |
division with remainder of F by G wrt Variable (1) modulo M using Newton inversion
| [in] | F | bivariate, compressed polynomial |
| [in] | G | bivariate, compressed polynomial which is monic in Variable (1) |
| [in,out] | Q | dividend |
| [in,out] | R | remainder, degree (R, 1) < degree (G, 1) |
| [in] | M | power of Variable (2) |
Definition at line 3259 of file facMul.cc.
| CanonicalForm newtonInverse | ( | const CanonicalForm & | F, |
| const int | n, | ||
| const Variable & | x | ||
| ) |
Definition at line 287 of file facMul.cc.
| CanonicalForm newtonInverse | ( | const CanonicalForm & | F, |
| const int | n, | ||
| const CanonicalForm & | M | ||
| ) |
Definition at line 3125 of file facMul.cc.
| CanonicalForm prodMod | ( | const CFList & | L, |
| const CanonicalForm & | M | ||
| ) |
product of all elements in L modulo M via divide-and-conquer.
| [in] | L | contains only bivariate, compressed polynomials |
| [in] | M | power of Variable (2) |
Definition at line 3047 of file facMul.cc.
| CanonicalForm prodMod | ( | const CFList & | L, |
| const CFList & | M | ||
| ) |
product of all elements in L modulo M via divide-and-conquer.
| [in] | L | contains multivariate, compressed polynomials |
| [in] | M | contains only powers of Variables |
Definition at line 3074 of file facMul.cc.
| CanonicalForm reverse | ( | const CanonicalForm & | F, |
| int | d | ||
| ) |
Definition at line 3101 of file facMul.cc.
| CanonicalForm reverseSubstFp | ( | const nmod_poly_t | F, |
| int | d | ||
| ) |
Definition at line 1921 of file facMul.cc.
| CanonicalForm reverseSubstFq | ( | const fq_nmod_poly_t | F, |
| int | d, | ||
| const Variable & | alpha, | ||
| const fq_nmod_ctx_t | fq_con | ||
| ) |
Definition at line 1886 of file facMul.cc.
| CanonicalForm reverseSubstQ | ( | const fmpz_poly_t | F, |
| int | d | ||
| ) |
Definition at line 1366 of file facMul.cc.
| CanonicalForm reverseSubstQa | ( | const fmpz_poly_t | F, |
| int | d, | ||
| const Variable & | x, | ||
| const Variable & | alpha, | ||
| const CanonicalForm & | den | ||
| ) |
Definition at line 62 of file facMul.cc.
| CanonicalForm reverseSubstQa | ( | const fmpz_poly_t | F, |
| int | d1, | ||
| int | d2, | ||
| const Variable & | alpha, | ||
| const fmpq_poly_t | mipo | ||
| ) |
Definition at line 1472 of file facMul.cc.
| CanonicalForm reverseSubstReciproFp | ( | const nmod_poly_t | F, |
| const nmod_poly_t | G, | ||
| int | d, | ||
| int | k | ||
| ) |
Definition at line 1529 of file facMul.cc.
| CanonicalForm reverseSubstReciproFq | ( | const fq_nmod_poly_t | F, |
| const fq_nmod_poly_t | G, | ||
| int | d, | ||
| int | k, | ||
| const Variable & | alpha, | ||
| const fq_nmod_ctx_t | fq_con | ||
| ) |
Definition at line 1648 of file facMul.cc.
| CanonicalForm reverseSubstReciproQ | ( | const fmpz_poly_t | F, |
| const fmpz_poly_t | G, | ||
| int | d, | ||
| int | k | ||
| ) |
Definition at line 1752 of file facMul.cc.
Definition at line 3336 of file facMul.cc.
| bool uniFdivides | ( | const CanonicalForm & | A, |
| const CanonicalForm & | B | ||
| ) |
divisibility test for univariate polys
| [in] | A | univariate poly |
| [in] | B | univariate poly |
Definition at line 3626 of file facMul.cc.
| CanonicalForm uniReverse | ( | const CanonicalForm & | F, |
| int | d, | ||
| const Variable & | x | ||
| ) |
Definition at line 270 of file facMul.cc.