source: git/factory/facSparseHensel.h @ 72bfc8

spielwiese
Last change on this file since 72bfc8 was 72bfc8, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: deleted @internal
  • Property mode set to 100644
File size: 12.8 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorize.h
5 *
6 * This file provides functions for sparse heuristic Hensel lifting
7 *
8 * @author Martin Lee
9 *
10 **/
11/*****************************************************************************/
12
13#ifndef FAC_SPARSE_HENSEL_H
14#define FAC_SPARSE_HENSEL_H
15
16#include "canonicalform.h"
17#include "cf_map_ext.h"
18#include "cf_iter.h"
19#include "templates/ftmpl_functions.h"
20
21/// compare polynomials
22inline
23int comp (const CanonicalForm& A, const CanonicalForm& B)
24{
25  if (A.inCoeffDomain() && !B.inCoeffDomain())
26    return -1;
27  else if (!A.inCoeffDomain() && B.inCoeffDomain())
28    return 1;
29  else if (A.inCoeffDomain() && B.inCoeffDomain())
30    return 0;
31  else if (degree (A, 1) > degree (B, 1))
32    return 1;
33  else if (degree (A, 1) < degree (B, 1))
34    return -1;
35  // here A and B are not in CoeffDomain
36  int n= tmax (A.level(), B.level());
37  for (int i= 2; i <= n; i++)
38  {
39    if (degree (A,i) > degree (B,i))
40      return 1;
41    else if (degree (A,i) < degree (B,i))
42      return -1;
43  }
44  return 0;
45}
46
47/// compare two polynomials up to level @a level
48inline
49int comp (const CanonicalForm& A, const CanonicalForm& B, int level)
50{
51  if (A.inCoeffDomain() && !B.inCoeffDomain() && B.level() <= level)
52    return -1;
53  else if (!A.inCoeffDomain() && A.level() <= level && B.inCoeffDomain())
54    return 1;
55  else if (A.inCoeffDomain() && B.inCoeffDomain())
56    return 0;
57  else if (degree (A, 1) > degree (B, 1))
58    return 1;
59  else if (degree (A, 1) < degree (B, 1))
60    return -1;
61  // here A and B are not in coeffdomain
62  for (int i= 2; i <= level; i++)
63  {
64    if (degree (A,i) > degree (B,i))
65      return 1;
66    else if (degree (A,i) < degree (B,i))
67      return -1;
68  }
69  return 0;
70}
71
72/// swap entry @a i and @a j in @a A
73inline
74void swap (CFArray& A, int i, int j)
75{
76  CanonicalForm tmp= A[i];
77  A[i]= A[j];
78  A[j]= tmp;
79}
80
81/// quick sort helper function
82inline
83void quickSort (int lo, int hi, CFArray& A)
84{
85  int i= lo, j= hi;
86  CanonicalForm tmp= A[(lo+hi)/2];
87  while (i <= j)
88  {
89    while (comp (A [i], tmp) < 0 && i < hi) i++;
90    while (comp (tmp, A[j]) < 0 && j > lo) j--;
91    if (i <= j)
92    {
93      swap (A, i, j);
94      i++;
95      j--;
96    }
97  }
98  if (lo < j) quickSort (lo, j, A);
99  if (i < hi) quickSort (i, hi, A);
100}
101
102/// quick sort @a A
103inline
104void sort (CFArray& A)
105{
106  quickSort (0, A.size() - 1, A);
107}
108
109/// find normalizing factors for @a biFactors and build monic univariate factors
110/// from @a biFactors
111inline CFList
112findNormalizingFactor1 (const CFList& biFactors, const CanonicalForm& evalPoint,
113                        CFList& uniFactors)
114{
115  CFList result;
116  CanonicalForm tmp;
117  for (CFListIterator i= biFactors; i.hasItem(); i++)
118  {
119    tmp= i.getItem() (evalPoint);
120    uniFactors.append (tmp /Lc (tmp));
121    result.append (Lc (tmp));
122  }
123  return result;
124}
125
126/// find normalizing factors for @a biFactors and sort @a biFactors s.t.
127/// the returned @a biFactors evaluated at evalPoint coincide with @a uniFactors
128inline CFList
129findNormalizingFactor2 (CFList& biFactors, const CanonicalForm& evalPoint,
130                        const CFList& uniFactors)
131{
132  CFList result;
133  CFList uniBiFactors= biFactors;
134  CFList newBiFactors;
135  CFList l;
136  int pos;
137  CFListIterator iter;
138  for (iter= uniBiFactors; iter.hasItem(); iter++)
139  {
140    iter.getItem()= iter.getItem() (evalPoint);
141    l.append (Lc (iter.getItem()));
142    iter.getItem() /= Lc (iter.getItem());
143  }
144  for (CFListIterator i= uniFactors; i.hasItem(); i++)
145  {
146    pos= findItem (uniBiFactors, i.getItem());
147    newBiFactors.append (getItem (biFactors, pos));
148    result.append (getItem (l, pos));
149  }
150  biFactors= newBiFactors;
151  return result;
152}
153
154/// get terms of @a F
155inline CFArray
156getTerms (const CanonicalForm& F)
157{
158  if (F.inCoeffDomain())
159  {
160    CFArray result= CFArray (1);
161    result [0]= F;
162    return result;
163  }
164  if (F.isUnivariate())
165  {
166    CFArray result= CFArray (size(F));
167    int j= 0;
168    for (CFIterator i= F; i.hasTerms(); i++, j++)
169      result[j]= i.coeff()*power (F.mvar(), i.exp());
170    return result;
171  }
172  int numMon= size (F);
173  CFArray result= CFArray (numMon);
174  int j= 0;
175  CFArray recResult;
176  Variable x= F.mvar();
177  CanonicalForm powX;
178  for (CFIterator i= F; i.hasTerms(); i++)
179  {
180    powX= power (x, i.exp());
181    recResult= getTerms (i.coeff());
182    for (int k= 0; k < recResult.size(); k++)
183      result[j+k]= powX*recResult[k];
184    j += recResult.size();
185  }
186  return result;
187}
188
189/// build a poly from entries in @a A
190inline CanonicalForm
191buildPolyFromArray (const CFArray& A)
192{
193  CanonicalForm result= 0;
194  for (int i= A.size() - 1; i > -1; i--)
195    result += A[i];
196  return result;
197}
198
199/// group together elements in @a A, where entries in @a A are put put together
200/// if they coincide up to level @a level
201inline void
202groupTogether (CFArray& A, int level)
203{
204  int n= A.size() - 1;
205  int k= A.size();
206  for (int i= 0; i < n; i++)
207  {
208    if (comp (A[i],A[i+1], level) == 0)
209    {
210      A[i+1] += A[i];
211      A[i]= 0;
212      k--;
213    }
214  }
215  CFArray B= CFArray (k);
216  n++;
217  k= 0;
218  for (int i= 0; i < n; i++)
219  {
220    if (!A[i].isZero())
221    {
222      B[k]= A[i];
223      k++;
224    }
225  }
226  A= B;
227}
228
229/// strip off those parts of entries in @a F whose level is less than or equal
230/// than @a level and store the stripped off parts in @a G
231inline void
232strip (CFArray& F, CFArray& G, int level)
233{
234  int n, m, i, j;
235  CanonicalForm g;
236  m= F.size();
237  G= CFArray (m);
238  for (j= 0; j < m; j++)
239  {
240    g= 1;
241    for (i= 1; i <= level; i++)
242    {
243      if ((n= degree (F[j],i)) > 0)
244        g *= power (Variable (i), n);
245    }
246    F[j] /= g;
247    G[j]= g;
248  }
249}
250
251/// s.a. stripped off parts are not returned
252inline void
253strip (CFArray& F, int level)
254{
255  int n, m, i;
256  CanonicalForm g;
257  m= F.size();
258  for (int j= 0; j < m; j++)
259  {
260    g= 1;
261    for (i= 1; i <= level; i++)
262    {
263      if ((n= degree (F[j],i)) > 0)
264        g *= power (Variable (i), n);
265    }
266    F[j] /= g;
267  }
268}
269
270/// get equations for LucksWangSparseHeuristic
271inline
272CFArray getEquations (const CFArray& A, const CFArray& B)
273{
274  ASSERT (A.size() == B.size(), "size of A and B has to coincide");
275  CFArray result= CFArray (A.size());
276  int n= A.size();
277  for (int i= 0; i < n; i++)
278    result[i]= A[i]-B[i];
279  return result;
280}
281
282/// evaluate every entry of @a A at @a B and level @a level
283inline void
284evaluate (CFArray& A, const CanonicalForm& B, int level)
285{
286  int n= A.size();
287  for (int i= 0; i < n; i++)
288  {
289    if (A[i].level() < level)
290      continue;
291    else
292      A[i]= A[i] (B, level);
293  }
294}
295
296/// evaluate every entry of @a A at every entry of @a B starting at level @a
297/// level
298inline void
299evaluate (CFArray& A, const CFArray& B, int level)
300{
301  int n= B.size();
302  for (int i= 0; i < n; i++)
303  {
304    if (!B[i].isZero())
305      evaluate (A, B[i], level + i);
306  }
307}
308
309/// simplify @a A if possible, i.e. @a A consists of 2 terms and contains only
310/// one variable of level greater or equal than @a level
311inline CanonicalForm
312simplify (const CanonicalForm& A, int level)
313{
314  CanonicalForm F= 0;
315  if (size (A, A.level()) == 2)
316  {
317    CanonicalForm C= getVars (A);
318    if ((C/C.mvar()).level() < level)
319    {
320      CanonicalForm B= LC (A);
321      if (B.level() < level)
322        F= -tailcoeff (A/B);
323    }
324  }
325  return F;
326}
327
328///  if possible simplify @a A as described above and store result in @a B
329inline bool
330simplify (CFArray& A, CFArray& B, int level)
331{
332  int n= A.size();
333  CanonicalForm f;
334  int index;
335  for (int i= 0; i < n; i++)
336  {
337    if (!A[i].isZero())
338    {
339      f= simplify (A[i], level);
340      if (!f.isZero())
341      {
342        index= A[i].level() - level;
343        if (index < 0 || index >= B.size())
344          return false;
345        if (!B[index].isZero() && B[index] != f)
346          return false;
347        else if (B[index].isZero())
348        {
349          B[index]= f;
350          A[i]= 0;
351        }
352      }
353    }
354  }
355  return true;
356}
357
358/// merge @a B into @a A if possible, i.e. every non-zero entry in @a A should
359/// be zero in @a B
360inline bool
361merge (CFArray& A, CFArray& B)
362{
363  if (A.size() != B.size())
364    return false;
365  int n= A.size();
366  for (int i= 0; i < n; i++)
367  {
368    if (!B[i].isZero())
369    {
370      if (A[i].isZero())
371      {
372        A[i]= B[i];
373        B[i]= 0;
374      }
375      else if (A[i] == B[i])
376        B[i]= 0;
377      else
378        return false;
379    }
380  }
381  return true;
382}
383
384/// checks if entries of @a A are zero
385inline bool
386isZero (const CFArray& A)
387{
388  int n= A.size();
389  for (int i= 0; i < n; i++)
390    if (!A[i].isZero())
391      return false;
392  return true;
393}
394
395/// checks if @a A equals @a B
396inline bool
397isEqual (const CFArray& A, const CFArray& B)
398{
399  if (A.size() != B.size())
400    return false;
401  int i, n= B.size();
402  for (i= 0; i < n; i++)
403    if (A[i] != B[i])
404      return false;
405  return true;
406}
407
408/// get terms of @a F wrt. Variable (1)
409inline CFArray
410getTerms2 (const CanonicalForm& F)
411{
412  if (F.inCoeffDomain())
413  {
414    CFArray result= CFArray (1);
415    result[0]= F;
416    return result;
417  }
418  CFArray result= CFArray (size (F));
419  int j= 0;
420  Variable x= F.mvar();
421  Variable y= Variable (1);
422  CFIterator k;
423  for (CFIterator i= F; i.hasTerms(); i++)
424  {
425    if (i.coeff().inCoeffDomain())
426    {
427      result[j]= i.coeff()*power (x,i.exp());
428      j++;
429    }
430    else
431    {
432      for (k= i.coeff(); k.hasTerms(); k++, j++)
433        result[j]= k.coeff()*power (x,i.exp())*power (y,k.exp());
434    }
435  }
436  sort (result);
437  return result;
438}
439
440/// get terms of entries in @a F and put them in @a result
441inline
442void getTerms2 (const CFList& F, CFArray* result)
443{
444  int j= 0;
445  for (CFListIterator i= F; i.hasItem(); i++, j++)
446    result[j]= getTerms2 (i.getItem());
447}
448
449/// evaluate entries in @a A at @a eval and @a y
450inline CFArray
451evaluate (const CFArray& A, const CanonicalForm& eval, const Variable& y)
452{
453  int j= A.size();
454  CFArray result= CFArray (j);
455  for (int i= 0; i < j; i++)
456    result [i]= A[i] (eval, y);
457  return result;
458}
459
460/// s.a.
461inline CFArray*
462evaluate (CFArray* const& A, int sizeA, const CanonicalForm& eval,
463          const Variable& y)
464{
465  CFArray* result= new CFArray [sizeA];
466  for (int i= 0; i < sizeA; i++)
467    result[i]= evaluate (A[i], eval, y);
468  return result;
469}
470
471/// normalize entries in @a L with @a normalizingFactor
472inline
473CFList normalize (const CFList& L, const CFList& normalizingFactor)
474{
475  CFList result;
476  CFListIterator j= normalizingFactor;
477  for (CFListIterator i= L; i.hasItem(); i++, j++)
478    result.append (i.getItem() / j.getItem());
479  return result;
480}
481
482/// search for @a F in @a A between index @a i and @a j
483inline
484int search (const CFArray& A, const CanonicalForm& F, int i, int j)
485{
486  for (; i < j; i++)
487    if (A[i] == F)
488      return i;
489  return -1;
490}
491
492/// patch together @a F1 and @a F2 and normalize by a power of @a eval
493/// @a F1 and @a F2 are assumed to be bivariate with one variable having level 1
494inline
495CanonicalForm patch (const CanonicalForm& F1, const CanonicalForm& F2,
496                     const CanonicalForm& eval)
497{
498  CanonicalForm result= F1;
499  if (F2.level() != 1 && !F2.inCoeffDomain())
500  {
501    int d= degree (F2);
502    result *= power (F2.mvar(), d);
503    result /= power (eval, d);
504  }
505  return result;
506}
507
508/// sparse heuristic lifting by Wang and Lucks
509///
510/// @return @a LucksWangSparseHeuristic returns true if it was successful
511bool
512LucksWangSparseHeuristic (const CanonicalForm& F,     ///<[in] polynomial to be
513                                                      ///< factored
514                          const CFList& factors,      ///<[in] factors of F
515                                                      ///< lifted to level
516                          int level,                  ///<[in] level of lifted
517                                                      ///< factors
518                          const CFList& leadingCoeffs,///<[in] leading
519                                                      ///< coefficients of
520                                                      ///< factors
521                          CFList& result              ///<[in,out] result
522                         );
523
524/// sparse heuristic which patches together bivariate factors of @a A wrt.
525/// different second variables by their univariate images
526///
527/// @return @a sparseHeuristic returns a list of found factors of A
528CFList
529sparseHeuristic (const CanonicalForm& A,  ///<[in] polynomial to be factored
530                 const CFList& biFactors, ///<[in] bivariate factors of A where
531                                          ///< the second variable has level 2
532                 CFList*& moreBiFactors,  ///<[in] more bivariate factorizations
533                                          ///< wrt. different second variables
534                 const CFList& evaluation,///<[in] evaluation point
535                 int minFactorsLength     ///<[in] minimal length of bivariate
536                                          ///< factorizations
537                );
538
539#endif
Note: See TracBrowser for help on using the repository browser.