My Project
Loading...
Searching...
No Matches
facFqFactorizeUtil.cc
Go to the documentation of this file.
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorizeUtil.cc
5 *
6 * This file provides utility functions for multivariate factorization
7 *
8 * @author Martin Lee
9 *
10 **/
11/*****************************************************************************/
12
13
14#include "config.h"
15
16
17#include "canonicalform.h"
18#include "cf_map.h"
19#include "cf_algorithm.h"
20
21static inline
22void appendSwap (CFList& factors1, const CFList& factors2, const int
23 swapLevel1, const int swapLevel2, const Variable& x)
24{
25 for (CFListIterator i= factors2; i.hasItem(); i++)
26 {
27 if (swapLevel1)
28 {
29 if (swapLevel2)
30 factors1.append (swapvar (swapvar (i.getItem(), x,
31 Variable (swapLevel2)), Variable (swapLevel1), x));
32 else
33 factors1.append (swapvar (i.getItem(), Variable (swapLevel1), x));
34 }
35 else
36 {
37 if (swapLevel2)
38 factors1.append (swapvar (i.getItem(), x, Variable (swapLevel2)));
39 else
40 factors1.append (i.getItem());
41 }
42 }
43 return;
44}
45
46
47void swap (CFList& factors, const int swapLevel1, const int swapLevel2, const
48 Variable& x)
49{
50 for (CFListIterator i= factors; i.hasItem(); i++)
51 {
52 if (swapLevel1)
53 {
54 if (swapLevel2)
55 i.getItem()= swapvar (swapvar (i.getItem(), x, Variable (swapLevel2)),
56 Variable (swapLevel1), x);
57 else
58 i.getItem()= swapvar (i.getItem(), Variable (swapLevel1), x);
59 }
60 else
61 {
62 if (swapLevel2)
63 i.getItem()= swapvar (i.getItem(), x, Variable (swapLevel2));
64 }
65 }
66 return;
67}
68
70 const CFMap& N, const int swapLevel, const
71 Variable& x)
72{
73 for (CFListIterator i= factors1; i.hasItem(); i++)
74 {
75 if (swapLevel)
76 i.getItem()= swapvar (i.getItem(), Variable (swapLevel), x);
77 i.getItem()= N(i.getItem());
78 }
79 for (CFListIterator i= factors2; i.hasItem(); i++)
80 {
81 if (!i.getItem().inCoeffDomain())
82 factors1.append (N (i.getItem()));
83 }
84 return;
85}
86
88 const CFMap& N, const int swapLevel1,
89 const int swapLevel2, const Variable& x)
90{
91 for (CFListIterator i= factors1; i.hasItem(); i++)
92 {
93 if (swapLevel1)
94 {
95 if (swapLevel2)
96 i.getItem()=
97 N (swapvar (swapvar (i.getItem(), Variable (swapLevel2), x), x,
98 Variable (swapLevel1)));
99 else
100 i.getItem()= N (swapvar (i.getItem(), x, Variable (swapLevel1)));
101 }
102 else
103 {
104 if (swapLevel2)
105 i.getItem()= N (swapvar (i.getItem(), Variable (swapLevel2), x));
106 else
107 i.getItem()= N (i.getItem());
108 }
109 }
110 for (CFListIterator i= factors2; i.hasItem(); i++)
111 {
112 if (!i.getItem().inCoeffDomain())
113 factors1.append (N (i.getItem()));
114 }
115 return;
116}
117
118int* liftingBounds (const CanonicalForm& A, const int& bivarLiftBound)
119{
120 int j= A.level() - 1;
121 int* liftBounds= new int [j];
122 liftBounds[0]= bivarLiftBound;
123 for (int i= 1; i < j; i++)
124 {
125 liftBounds[i]= degree (A, Variable (i + 2)) + 1 +
126 degree (LC (A, 1), Variable (i + 2));
127 }
128 return liftBounds;
129}
130
132{
133 CanonicalForm A= F;
134 int k= evaluation.length() + l - 1;
135 for (CFListIterator i= evaluation; i.hasItem(); i++, k--)
136 A= A (Variable (k) + i.getItem(), k);
138 Feval= CFList();
139 Feval.append (buf);
140 for (k= A.level(); k > 2; k--)
141 {
142 buf= mod (buf, Variable (k));
143 Feval.insert (buf);
144 }
145 return A;
146}
147
149{
150 int k= evaluation.length() + l - 1;
153 for (int i= k; j.hasItem() && (i > l - 1); i--, j++)
154 {
155 if (F.level() < i)
156 continue;
157 result= result (Variable (i) - j.getItem(), i);
158 }
159 return result;
160}
161
163{
164 return (F-LC (F,1)*power (Variable(1),degree (F,1))).isZero();
165}
166
167/// like getVars but including multiplicities
169{
171 int deg;
172 for (int i= 1; i <= F.level(); i++)
173 {
174 if ((deg= degree (F, i)) > 0)
175 result *= power (Variable (i), deg);
176 }
177 return result;
178}
179
181{
182 return getNumVars (F.factor()) < getNumVars (G.factor());
183}
184
187{
189 CFFList result= F;
190 return result;
191}
192
194{
197 result.insert (buf);
198 for (int i= F.level(); i > 2; i--)
199 {
200 buf= buf (0, i);
201 result.insert (buf);
202 }
203 return result;
204}
205
207{
210 result.insert (buf);
211 int k= eval.size();
212 for (int i= 1; i < k; i++)
213 {
214 buf= buf (eval[i], i + 2);
215 result.insert (buf);
216 }
217 return result;
218}
219
221{
224 result.insert (buf);
225 int k= evaluation.length() + l - 1;
227 for (int i= k; j.hasItem() && i > l; i--, j++)
228 {
229 if (F.level() < i)
230 continue;
231 buf= buf (j.getItem(), i);
232 result.insert (buf);
233 }
234 return result;
235}
236
237
238CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
239{
241 CanonicalForm tmp, tmp2;
242 CanonicalForm G= F;
243 for (CFListIterator i= factors; i.hasItem(); i++)
244 {
245 tmp= i.getItem()/content (i.getItem(), 1);
246 if (fdivides (tmp, G, tmp2))
247 {
248 G= tmp2;
249 result.append (tmp);
250 }
251 }
252 if (result.length() + 1 == factors.length())
253 result.append (G/content (G,1));
254 return result;
255}
256
257CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
258 const CFList& evaluation)
259{
261 CanonicalForm tmp, tmp2;
262 CanonicalForm G= F;
263 for (CFListIterator i= factors; i.hasItem(); i++)
264 {
265 tmp= reverseShift (i.getItem(), evaluation, 2);
266 tmp /= content (tmp, 1);
267 if (fdivides (tmp, G, tmp2))
268 {
269 G= tmp2;
270 result.append (tmp);
271 }
272 }
273 if (result.length() + 1 == factors.length())
274 result.append (G/content (G,1));
275 return result;
276}
277
279{
281 CanonicalForm tmp, tmp2;
282 CanonicalForm G= F;
283 int j= 0;
284 for (CFListIterator i= factors; i.hasItem(); i++, j++)
285 {
286 if (i.getItem().isZero())
287 {
288 index[j]= 0;
289 continue;
290 }
291 tmp= i.getItem();
292 if (fdivides (tmp, G, tmp2))
293 {
294 G= tmp2;
295 tmp /=content (tmp, 1);
296 result.append (tmp);
297 index[j]= 1;
298 }
299 else
300 index[j]= 0;
301 }
302 if (result.length() + 1 == factors.length())
303 {
304 result.append (G/content (G,1));
305 F= G/content (G,1);
306 }
307 else
308 F= G;
309 return result;
310}
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
map polynomials
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
int level() const
level() returns the level of CO.
T factor() const
Definition: ftmpl_factor.h:30
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: variable.h:33
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
CanonicalForm Feval
Definition: facAbsFact.cc:60
CFList & eval
Definition: facFactorize.cc:47
const CFList & factors2
CFList tmp2
Definition: facFqBivar.cc:72
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFMap &N, const int swapLevel, const Variable &x)
swap elements of factors2, append them to factors1 and decompress
static void appendSwap(CFList &factors1, const CFList &factors2, const int swapLevel1, const int swapLevel2, const Variable &x)
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
int compareByNumberOfVars(const CFFactor &F, const CFFactor &G)
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
int j
Definition: facHensel.cc:110
STATIC_VAR TreeM * G
Definition: janet.cc:31
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24