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 
21 static inline
22 void 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 
47 void 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 
69 void appendSwapDecompress (CFList& factors1, const CFList& factors2,
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 
87 void appendSwapDecompress (CFList& factors1, const CFList& factors2,
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 
118 int* 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 
180 int compareByNumberOfVars (const CFFactor& F, const CFFactor& G)
181 {
182  return getNumVars (F.factor()) < getNumVars (G.factor());
183 }
184 
185 CFFList
187 {
189  CFFList result= F;
190  return result;
191 }
192 
194 {
195  CFList result;
196  CanonicalForm buf= F;
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 {
208  CFList result;
209  CanonicalForm buf= F;
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 {
222  CFList result;
223  CanonicalForm buf= F;
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 
238 CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
239 {
240  CFList result;
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 
257 CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
258  const CFList& evaluation)
259 {
260  CFList result;
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 
278 CFList recoverFactors (CanonicalForm& F, const CFList& factors, int* index)
279 {
280  CFList result;
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 }
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
int j
Definition: facHensel.cc:105
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
int compareByNumberOfVars(const CFFactor &F, const CFFactor &G)
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the 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
factory&#39;s class for variables
Definition: factory.h:117
T factor() const
Definition: ftmpl_factor.h:30
factory&#39;s main class
Definition: canonicalform.h:77
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
int k
Definition: cfEzgcd.cc:92
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
void insert(const T &)
Definition: ftmpl_list.cc:193
const CFList & factors2
static TreeM * G
Definition: janet.cc:31
map polynomials
int size() const
Definition: ftmpl_array.cc:92
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
static void appendSwap(CFList &factors1, const CFList &factors2, const int swapLevel1, const int swapLevel2, const Variable &x)
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
int status int void * buf
Definition: si_signals.h:59
T & getItem() const
Definition: ftmpl_list.cc:431
#define A
Definition: sirandom.c:23
CFList & eval
Definition: facFactorize.cc:48
int i
Definition: cfEzgcd.cc:125
CFList tmp2
Definition: facFqBivar.cc:70
declarations of higher level algorithms.
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
class CFMap
Definition: cf_map.h:84
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm Feval
Definition: facAbsFact.cc:64
int length() const
Definition: ftmpl_list.cc:273
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
Variable x
Definition: cfModGcd.cc:4023
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
void swap(CFList &factors, const int swapLevel1, const int swapLevel2, const Variable &x)
swap elements in factors
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:93
Header for factory&#39;s main class CanonicalForm.
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339