source: git/factory/facFqFactorizeUtil.cc @ 5b390e

jengelh-datetimespielwiese
Last change on this file since 5b390e was 5b390e, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: improved recoverFactors
  • Property mode set to 100644
File size: 7.2 KB
Line 
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#include "config.h"
14
15#include "canonicalform.h"
16#include "cf_map.h"
17#include "cf_algorithm.h"
18
19static inline
20void appendSwap (CFList& factors1, const CFList& factors2, const int
21                  swapLevel1, const int swapLevel2, const Variable& x)
22{
23  for (CFListIterator i= factors2; i.hasItem(); i++)
24  {
25    if (swapLevel1)
26    {
27      if (swapLevel2)
28        factors1.append (swapvar (swapvar (i.getItem(), x,
29                         Variable (swapLevel2)), Variable (swapLevel1), x));
30      else
31        factors1.append (swapvar (i.getItem(), Variable (swapLevel1), x));
32    }
33    else
34    {
35      if (swapLevel2)
36        factors1.append (swapvar (i.getItem(), x, Variable (swapLevel2)));
37      else
38        factors1.append (i.getItem());
39    }
40  }
41  return;
42}
43
44
45void swap (CFList& factors, const int swapLevel1, const int swapLevel2, const
46           Variable& x)
47{
48  for (CFListIterator i= factors; i.hasItem(); i++)
49  {
50    if (swapLevel1)
51    {
52      if (swapLevel2)
53        i.getItem()= swapvar (swapvar (i.getItem(), x, Variable (swapLevel2)),
54                              Variable (swapLevel1), x);
55      else
56        i.getItem()= swapvar (i.getItem(), Variable (swapLevel1), x);
57    }
58    else
59    {
60      if (swapLevel2)
61        i.getItem()= swapvar (i.getItem(), x, Variable (swapLevel2));
62    }
63  }
64  return;
65}
66
67void appendSwapDecompress (CFList& factors1, const CFList& factors2,
68                             const CFMap& N, const int swapLevel, const
69                             Variable& x)
70{
71  for (CFListIterator i= factors1; i.hasItem(); i++)
72  {
73    if (swapLevel)
74      i.getItem()= swapvar (i.getItem(), Variable (swapLevel), x);
75    i.getItem()= N(i.getItem());
76  }
77  for (CFListIterator i= factors2; i.hasItem(); i++)
78  {
79    if (!i.getItem().inCoeffDomain())
80      factors1.append (N (i.getItem()));
81  }
82  return;
83}
84
85void appendSwapDecompress (CFList& factors1, const CFList& factors2,
86                             const CFMap& N, const int swapLevel1,
87                             const int swapLevel2, const Variable& x)
88{
89  for (CFListIterator i= factors1; i.hasItem(); i++)
90  {
91    if (swapLevel1)
92    {
93      if (swapLevel2)
94        i.getItem()=
95        N (swapvar (swapvar (i.getItem(), Variable (swapLevel2), x), x,
96                    Variable (swapLevel1)));
97      else
98        i.getItem()= N (swapvar (i.getItem(), x, Variable (swapLevel1)));
99    }
100    else
101    {
102      if (swapLevel2)
103        i.getItem()= N (swapvar (i.getItem(), Variable (swapLevel2), x));
104      else
105        i.getItem()= N (i.getItem());
106    }
107  }
108  for (CFListIterator i= factors2; i.hasItem(); i++)
109  {
110    if (!i.getItem().inCoeffDomain())
111      factors1.append (N (i.getItem()));
112  }
113  return;
114}
115
116int* liftingBounds (const CanonicalForm& A, const int& bivarLiftBound)
117{
118  int j= A.level() - 1;
119  int* liftBounds= new int [j];
120  liftBounds[0]= bivarLiftBound;
121  for (int i= 1; i < j; i++)
122  {
123    liftBounds[i]= degree (A, Variable (i + 2)) + 1 +
124                            degree (LC (A, 1), Variable (i + 2));
125  }
126  return liftBounds;
127}
128
129CanonicalForm shift2Zero (const CanonicalForm& F, CFList& Feval, const CFList& evaluation, int l)
130{
131  CanonicalForm A= F;
132  int k= evaluation.length() + l - 1;
133  for (CFListIterator i= evaluation; i.hasItem(); i++, k--)
134    A= A (Variable (k) + i.getItem(), k);
135  CanonicalForm buf= A;
136  Feval= CFList();
137  Feval.append (buf);
138  for (k= A.level(); k > 2; k--)
139  {
140    buf= mod (buf, Variable (k));
141    Feval.insert (buf);
142  }
143  return A;
144}
145
146CanonicalForm reverseShift (const CanonicalForm& F, const CFList& evaluation, int l)
147{
148  int k= evaluation.length() + l - 1;
149  CanonicalForm result= F;
150  CFListIterator j= evaluation;
151  for (int i= k; j.hasItem() && (i > l - 1); i--, j++)
152  {
153    if (F.level() < i)
154      continue;
155    result= result (Variable (i) - j.getItem(), i);
156  }
157  return result;
158}
159
160bool isOnlyLeadingCoeff (const CanonicalForm& F)
161{
162  return (F-LC (F,1)*power (Variable(1),degree (F,1))).isZero();
163}
164
165/// like getVars but including multiplicities
166CanonicalForm myGetVars (const CanonicalForm& F)
167{
168  CanonicalForm result= 1;
169  int deg;
170  for (int i= 1; i <= F.level(); i++)
171  {
172    if ((deg= degree (F, i)) > 0)
173      result *= power (Variable (i), deg);
174  }
175  return result;
176}
177
178int compareByNumberOfVars (const CFFactor& F, const CFFactor& G)
179{
180  return getNumVars (F.factor()) < getNumVars (G.factor());
181}
182
183CFFList
184sortCFFListByNumOfVars (CFFList& F)
185{
186    F.sort (compareByNumberOfVars);
187    CFFList result= F;
188    return result;
189}
190
191CFList evaluateAtZero (const CanonicalForm& F)
192{
193  CFList result;
194  CanonicalForm buf= F;
195  result.insert (buf);
196  for (int i= F.level(); i > 2; i--)
197  {
198    buf= buf (0, i);
199    result.insert (buf);
200  }
201  return result;
202}
203
204CFList evaluateAtEval (const CanonicalForm& F, const CFArray& eval)
205{
206  CFList result;
207  CanonicalForm buf= F;
208  result.insert (buf);
209  int k= eval.size();
210  for (int i= 1; i < k; i++)
211  {
212    buf= buf (eval[i], i + 2);
213    result.insert (buf);
214  }
215  return result;
216}
217
218CFList evaluateAtEval (const CanonicalForm& F, const CFList& evaluation, int l)
219{
220  CFList result;
221  CanonicalForm buf= F;
222  result.insert (buf);
223  int k= evaluation.length() + l - 1;
224  CFListIterator j= evaluation;
225  for (int i= k; j.hasItem() && i > l; i--, j++)
226  {
227    if (F.level() < i)
228      continue;
229    buf= buf (j.getItem(), i);
230    result.insert (buf);
231  }
232  return result;
233}
234
235
236CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
237{
238  CFList result;
239  CanonicalForm tmp, tmp2;
240  CanonicalForm G= F;
241  for (CFListIterator i= factors; i.hasItem(); i++)
242  {
243    tmp= i.getItem()/content (i.getItem(), 1);
244    if (fdivides (tmp, G, tmp2))
245    {
246      G= tmp2;
247      result.append (tmp);
248    }
249  }
250  if (result.length() + 1 == factors.length())
251    result.append (G/content (G,1));
252  return result;
253}
254
255CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
256                       const CFList& evaluation)
257{
258  CFList result;
259  CanonicalForm tmp, tmp2;
260  CanonicalForm G= F;
261  for (CFListIterator i= factors; i.hasItem(); i++)
262  {
263    tmp= reverseShift (i.getItem(), evaluation, 2);
264    tmp /= content (tmp, 1);
265    if (fdivides (tmp, G, tmp2))
266    {
267      G= tmp2;
268      result.append (tmp);
269    }
270  }
271  if (result.length() + 1 == factors.length())
272    result.append (G/content (G,1));
273  return result;
274}
275
276CFList recoverFactors (CanonicalForm& F, const CFList& factors, int* index)
277{
278  CFList result;
279  CanonicalForm tmp, tmp2;
280  CanonicalForm G= F;
281  int j= 0;
282  for (CFListIterator i= factors; i.hasItem(); i++, j++)
283  {
284    if (i.getItem().isZero())
285    {
286      index[j]= 0;
287      continue;
288    }
289    tmp= i.getItem();
290    if (fdivides (tmp, G, tmp2))
291    {
292      G= tmp2;
293      tmp /=content (tmp, 1);
294      result.append (tmp);
295      index[j]= 1;
296    }
297    else
298      index[j]= 0;
299  }
300  if (result.length() + 1 == factors.length())
301  {
302    result.append (G/content (G,1));
303    F= G/content (G,1);
304  }
305  else
306    F= G;
307  return result;
308}
Note: See TracBrowser for help on using the repository browser.