# source:git/factory/facMul.h@3edea1

spielwiese
Last change on this file since 3edea1 was 3edea1, checked in by Hans Schoenemann <hannes@…>, 3 years ago
cygwin port: shared lib libfactory
• Property mode set to `100644`
File size: 7.2 KB
Line
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facMul.h
5 *
6 * This file defines functions for fast multiplication and division with
7 * remainder
8 *
9 * @author Martin Lee
10 *
11 **/
12/*****************************************************************************/
13
14#ifndef FAC_MUL_H
15#define FAC_MUL_H
16
17#include "canonicalform.h"
18#include "fac_util.h"
19
20/// multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
21/// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
22/// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
23/// considered as elements over Z/p^k or Z/p^k[t]/(f).
24///
25/// @return @a mulNTL returns F*G
26CanonicalForm
27mulNTL (const CanonicalForm& F, ///< [in] a univariate poly
28        const CanonicalForm& G, ///< [in] a univariate poly
29        const modpk& b= modpk() ///< [in] coeff bound
30       );
31
32/// mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
33/// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
34/// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
35/// considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity
36/// of Lc(G) is not checked
37///
38/// @return @a modNTL returns F mod G
39CanonicalForm
40modNTL (const CanonicalForm& F, ///< [in] a univariate poly
41        const CanonicalForm& G, ///< [in] a univariate poly
42        const modpk& b= modpk() ///< [in] coeff bound
43       );
44
45/// division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k,
46/// Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory's default multiplication
47/// is used. If @a b!= 0 and getCharacteristic() == 0 the input will be
48/// considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity
49/// of Lc(G) is not checked
50///
51/// @return @a divNTL returns F/G
52CanonicalForm
53divNTL (const CanonicalForm& F, ///< [in] a univariate poly
54        const CanonicalForm& G, ///< [in] a univariate poly
55        const modpk& b= modpk() ///< [in] coeff bound
56       );
57
58/// division with remainder of @a F by @a G wrt Variable (1) modulo @a M.
59/// Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
60///
61/// @return @a Q returns the dividend, @a R returns the remainder.
62/// @sa divrem()
63void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
64              const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
65              CanonicalForm& Q,       ///< [in,out] dividend
66              CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
67                                      ///< degree (G, 1)
68              const CanonicalForm& M  ///< [in] power of Variable (2)
69             );
70
71/// division with remainder of @a F by @a G wrt Variable (1) modulo @a MOD.
72/// Uses an algorithm based on Burnikel, Ziegler "Fast recursive division".
73///
74/// @sa divrem2()
75void FACTORY_PUBLIC divrem (
76           const CanonicalForm& F, ///< [in] multivariate, compressed polynomial
77           const CanonicalForm& G, ///< [in] multivariate, compressed polynomial
78           CanonicalForm& Q,       ///< [in,out] dividend
79           CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
80                                   ///< degree (G, 1)
81           const CFList& MOD       ///< [in] only contains powers of
82                                   ///< Variables of level higher than 1
83            );
84
85
86/// division with remainder of @a F by
87/// @a G wrt Variable (1) modulo @a M using Newton inversion
88///
89/// @return @a Q returns the dividend, @a R returns the remainder.
90/// @sa divrem2(), newtonDiv()
91void
92newtonDivrem (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
93              const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
94                                      ///< which is monic in Variable (1)
95              CanonicalForm& Q,       ///< [in,out] dividend
96              CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
97                                      ///< degree (G, 1)
98              const CanonicalForm& M  ///< [in] power of Variable (2)
99             );
100
101/// division of @a F by
102/// @a G wrt Variable (1) modulo @a M using Newton inversion
103///
104/// @return @a newtonDiv returns the dividend
105/// @sa divrem2(), newtonDivrem()
106CanonicalForm
107newtonDiv (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
108           const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
109                                   ///< which is monic in Variable (1)
110           const CanonicalForm& M  ///< [in] power of Variable (2)
111          );
112
113/// divisibility test for univariate polys
114///
115/// @return @a uniFdivides returns true if A divides B
116bool
117uniFdivides (const CanonicalForm& A, ///< [in] univariate poly
118             const CanonicalForm& B  ///< [in] univariate poly
119            );
120
121/// Karatsuba style modular multiplication for bivariate polynomials.
122///
123/// @return @a mulMod2 returns @a A * @a B mod @a M.
124CanonicalForm
125mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial
126         const CanonicalForm& B, ///< [in] bivariate, compressed polynomial
127         const CanonicalForm& M  ///< [in] power of Variable (2)
128        );
129
130/// Karatsuba style modular multiplication for multivariate polynomials.
131///
132/// @return @a mulMod2 returns @a A * @a B mod @a MOD.
133CanonicalForm
134mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial
135        const CanonicalForm& B, ///< [in] multivariate, compressed polynomial
136        const CFList& MOD       ///< [in] only contains powers of
137                                ///< Variables of level higher than 1
138       );
139
140/// reduce @a F modulo elements in @a M.
141///
142/// @return @a mod returns @a F modulo @a M
143CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial
144                   const CFList& M         ///< [in] list containing only
145                                           ///< univariate polynomials
146                  );
147
148/// product of all elements in @a L modulo @a M via divide-and-conquer.
149///
150/// @return @a prodMod returns product of all elements in @a L modulo @a M.
151CanonicalForm
152prodMod (const CFList& L,       ///< [in] contains only bivariate, compressed
153                                ///< polynomials
154         const CanonicalForm& M ///< [in] power of Variable (2)
155        );
156
157/// product of all elements in @a L modulo @a M via divide-and-conquer.
158///
159/// @return @a prodMod returns product of all elements in @a L modulo @a M.
160CanonicalForm
161prodMod (const CFList& L, ///< [in] contains multivariate, compressed
162                          ///< polynomials
163         const CFList& M  ///< [in] contains only powers of Variables
164        );
165
166#ifdef HAVE_FLINT
167/// division with remainder of univariate polynomials over Q and Q(a) using
168/// Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)
169void
170newtonDivrem (const CanonicalForm& F, ///<[in] univariate poly
171              const CanonicalForm& G, ///<[in] univariate poly
172              CanonicalForm& Q,       ///<[in, out] quotient
173              CanonicalForm& R        ///<[in, out] remainder
174             );
175#endif
176
177#endif
178/* FAC_MUL_H */
179
Note: See TracBrowser for help on using the repository browser.