My Project
Loading...
Searching...
No Matches
facSparseHensel.h
Go to the documentation of this file.
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facSparseHensel.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"
20#include "cf_algorithm.h"
21#include "cf_map.h"
22
23/// compare polynomials
24inline
25int comp (const CanonicalForm& A, const CanonicalForm& B)
26{
27 if (A.inCoeffDomain() && !B.inCoeffDomain())
28 return -1;
29 else if (!A.inCoeffDomain() && B.inCoeffDomain())
30 return 1;
31 else if (A.inCoeffDomain() && B.inCoeffDomain())
32 return 0;
33 else if (degree (A, 1) > degree (B, 1))
34 return 1;
35 else if (degree (A, 1) < degree (B, 1))
36 return -1;
37 // here A and B are not in CoeffDomain
38 int n= tmax (A.level(), B.level());
39 for (int i= 2; i <= n; i++)
40 {
41 if (degree (A,i) > degree (B,i))
42 return 1;
43 else if (degree (A,i) < degree (B,i))
44 return -1;
45 }
46 return 0;
47}
48
49/// compare two polynomials up to level @a level
50inline
51int comp (const CanonicalForm& A, const CanonicalForm& B, int level)
52{
53 if (A.inCoeffDomain() && !B.inCoeffDomain() && B.level() <= level)
54 return -1;
55 else if (!A.inCoeffDomain() && A.level() <= level && B.inCoeffDomain())
56 return 1;
57 else if (A.inCoeffDomain() && B.inCoeffDomain())
58 return 0;
59 else if (degree (A, 1) > degree (B, 1))
60 return 1;
61 else if (degree (A, 1) < degree (B, 1))
62 return -1;
63 // here A and B are not in coeffdomain
64 for (int i= 2; i <= level; i++)
65 {
66 if (degree (A,i) > degree (B,i))
67 return 1;
68 else if (degree (A,i) < degree (B,i))
69 return -1;
70 }
71 return 0;
72}
73
74/// swap entry @a i and @a j in @a A
75inline
76void swap (CFArray& A, int i, int j)
77{
78 CanonicalForm tmp= A[i];
79 A[i]= A[j];
80 A[j]= tmp;
81}
82
83/// quick sort helper function
84inline
85void quickSort (int lo, int hi, CFArray& A, int l)
86{
87 int i= lo, j= hi;
88 CanonicalForm tmp= A[(lo+hi)/2];
89 while (i <= j)
90 {
91 if (l > 0)
92 {
93 while (comp (A [i], tmp, l) < 0 && i < hi) i++;
94 while (comp (tmp, A[j], l) < 0 && j > lo) j--;
95 }
96 else
97 {
98 while (comp (A [i], tmp) < 0 && i < hi) i++;
99 while (comp (tmp, A[j]) < 0 && j > lo) j--;
100 }
101 if (i <= j)
102 {
103 swap (A, i, j);
104 i++;
105 j--;
106 }
107 }
108 if (lo < j) quickSort (lo, j, A, l);
109 if (i < hi) quickSort (i, hi, A, l);
110}
111
112/// quick sort @a A
113inline
114void sort (CFArray& A, int l= 0)
115{
116 quickSort (0, A.size() - 1, A, l);
117}
118
119
120/// find normalizing factors for @a biFactors and build monic univariate factors
121/// from @a biFactors
122inline CFList
124 CFList& uniFactors)
125{
127 CanonicalForm tmp;
128 for (CFListIterator i= biFactors; i.hasItem(); i++)
129 {
130 tmp= i.getItem() (evalPoint);
131 uniFactors.append (tmp /Lc (tmp));
132 result.append (Lc (tmp));
133 }
134 return result;
135}
136
137/// find normalizing factors for @a biFactors and sort @a biFactors s.t.
138/// the returned @a biFactors evaluated at evalPoint coincide with @a uniFactors
139inline CFList
141 const CFList& uniFactors)
142{
144 CFList uniBiFactors= biFactors;
145 CFList newBiFactors;
146 CFList l;
147 int pos;
149 for (iter= uniBiFactors; iter.hasItem(); iter++)
150 {
152 l.append (Lc (iter.getItem()));
153 iter.getItem() /= Lc (iter.getItem());
154 }
155 for (CFListIterator i= uniFactors; i.hasItem(); i++)
156 {
157 pos= findItem (uniBiFactors, i.getItem());
158 newBiFactors.append (getItem (biFactors, pos));
159 result.append (getItem (l, pos));
160 }
161 biFactors= newBiFactors;
162 return result;
163}
164
165/// get terms of @a F
166inline CFArray
168{
169 if (F.inCoeffDomain())
170 {
172 result [0]= F;
173 return result;
174 }
175 if (F.isUnivariate())
176 {
178 int j= 0;
179 for (CFIterator i= F; i.hasTerms(); i++, j++)
180 result[j]= i.coeff()*power (F.mvar(), i.exp());
181 return result;
182 }
183 int numMon= size (F);
184 CFArray result= CFArray (numMon);
185 int j= 0;
186 CFArray recResult;
187 Variable x= F.mvar();
188 CanonicalForm powX;
189 for (CFIterator i= F; i.hasTerms(); i++)
190 {
191 powX= power (x, i.exp());
192 recResult= getTerms (i.coeff());
193 for (int k= 0; k < recResult.size(); k++)
194 result[j+k]= powX*recResult[k];
195 j += recResult.size();
196 }
197 return result;
198}
199
200/// helper function for getBiTerms
201inline CFArray
202getBiTerms_helper (const CanonicalForm& F, const CFMap& M, int threshold)
203{
204 CFArray buf= CFArray (size (F));
205 int k= 0, level= F.level() - 1;
206 Variable x= F.mvar();
207 Variable y= Variable (F.level() - 1);
208 Variable one= Variable (1);
209 Variable two= Variable (2);
211 for (CFIterator i= F; i.hasTerms(); i++)
212 {
213 if (i.coeff().level() < level)
214 {
215 buf[k]= M (i.coeff())*power (one,i.exp());
216 k++;
217 if (k > threshold)
218 break;
219 continue;
220 }
221 j= i.coeff();
222 for (;j.hasTerms() && k <= threshold; j++, k++)
223 buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff());
224 if (k > threshold)
225 break;
226 }
228 for (int i= 0; i < k && k <= threshold; i++)
229 result[i]= buf[i];
230 return result;
231}
232
233/// get terms of @a F where F is considered a bivariate poly in Variable(1),
234/// Variable (2)
235inline CFArray
236getBiTerms (const CanonicalForm& F, int threshold)
237{
238 if (F.inCoeffDomain())
239 {
241 result [0]= F;
242 return result;
243 }
244 if (F.isUnivariate())
245 {
247 int j= 0;
248 for (CFIterator i= F; i.hasTerms(); i++, j++)
249 result[j]= i.coeff()*power (F.mvar(), i.exp());
250 return result;
251 }
252
253 CanonicalForm G= F;
254
255 CFMap M;
256 M.newpair (Variable (1), F.mvar());
257 M.newpair (Variable (2), Variable (F.level() - 1));
258 G= swapvar (F, Variable (1), F.mvar());
259 G= swapvar (G, Variable (2), Variable (F.level() - 1));
260
261 CFArray result= getBiTerms_helper (G, M, threshold);
262 return result;
263}
264
265/// build a poly from entries in @a A
266inline CanonicalForm
268{
270 for (int i= A.size() - 1; i > -1; i--)
271 result += A[i];
272 return result;
273}
274
275/// group together elements in @a A, where entries in @a A are put together
276/// if they coincide up to level @a level
277inline void
279{
280 int n= A.size() - 1;
281 int k= A.size();
282 for (int i= 0; i < n; i++)
283 {
284 if (comp (A[i],A[i+1], level) == 0)
285 {
286 A[i+1] += A[i];
287 A[i]= 0;
288 k--;
289 }
290 }
291 if (A[n].isZero())
292 k--;
293 CFArray B= CFArray (k);
294 n++;
295 k= 0;
296 for (int i= 0; i < n; i++)
297 {
298 if (!A[i].isZero())
299 {
300 B[k]= A[i];
301 k++;
302 }
303 }
304 A= B;
305}
306
307/// strip off those parts of entries in @a F whose level is less than or equal
308/// than @a level and store the stripped off parts in @a G
309inline void
311{
312 int n, m, i, j;
314 m= F.size();
315 G= CFArray (m);
316 for (j= 0; j < m; j++)
317 {
318 g= 1;
319 for (i= 1; i <= level; i++)
320 {
321 if ((n= degree (F[j],i)) > 0)
322 g *= power (Variable (i), n);
323 }
324 F[j] /= g;
325 G[j]= g;
326 }
327}
328
329/// s.a. stripped off parts are not returned
330inline void
332{
333 int n, m, i;
335 m= F.size();
336 for (int j= 0; j < m; j++)
337 {
338 g= 1;
339 for (i= 1; i <= level; i++)
340 {
341 if ((n= degree (F[j],i)) > 0)
342 g *= power (Variable (i), n);
343 }
344 F[j] /= g;
345 }
346}
347
348/// get equations for LucksWangSparseHeuristic
349inline
351{
352 ASSERT (A.size() == B.size(), "size of A and B has to coincide");
353 CFArray result= CFArray (A.size());
354 int n= A.size();
355 for (int i= 0; i < n; i++)
356 result[i]= A[i]-B[i];
357 return result;
358}
359
360/// evaluate every entry of @a A at @a B and level @a level
361inline void
363{
364 int n= A.size();
365 for (int i= 0; i < n; i++)
366 {
367 if (A[i].level() < level)
368 continue;
369 else
370 A[i]= A[i] (B, level);
371 }
372}
373
374/// evaluate every entry of @a A at every entry of @a B starting at level @a
375/// level
376inline void
378{
379 int n= B.size();
380 for (int i= 0; i < n; i++)
381 {
382 if (!B[i].isZero())
383 evaluate (A, B[i], level + i);
384 }
385}
386
387/// simplify @a A if possible, i.e. @a A consists of 2 terms and contains only
388/// one variable of level greater or equal than @a level
389inline CanonicalForm
391{
392 CanonicalForm F= 0;
393 if (size (A, A.level()) == 2)
394 {
396 if ((C/C.mvar()).level() < level)
397 {
398 CanonicalForm B= LC (A);
399 if (B.level() < level)
400 {
401 CanonicalForm quot;
402 if (fdivides (B, A, quot))
403 F= -tailcoeff (quot);
404 }
405 }
406 }
407 return F;
408}
409
410/// if possible simplify @a A as described above and store result in @a B
411inline bool
413{
414 int n= A.size();
416 int index;
417 for (int i= 0; i < n; i++)
418 {
419 if (!A[i].isZero())
420 {
421 f= simplify (A[i], level);
422 if (!f.isZero())
423 {
424 index= A[i].level() - level;
425 if (index < 0 || index >= B.size())
426 return false;
427 if (!B[index].isZero() && B[index] != f)
428 return false;
429 else if (B[index].isZero())
430 {
431 B[index]= f;
432 A[i]= 0;
433 }
434 }
435 }
436 }
437 return true;
438}
439
440/// merge @a B into @a A if possible, i.e. every non-zero entry in @a A should
441/// be zero in @a B
442inline bool
444{
445 if (A.size() != B.size())
446 return false;
447 int n= A.size();
448 for (int i= 0; i < n; i++)
449 {
450 if (!B[i].isZero())
451 {
452 if (A[i].isZero())
453 {
454 A[i]= B[i];
455 B[i]= 0;
456 }
457 else if (A[i] == B[i])
458 B[i]= 0;
459 else
460 return false;
461 }
462 }
463 return true;
464}
465
466/// checks if entries of @a A are zero
467inline bool
469{
470 int n= A.size();
471 for (int i= 0; i < n; i++)
472 if (!A[i].isZero())
473 return false;
474 return true;
475}
476
477/// checks if @a A equals @a B
478inline bool
479isEqual (const CFArray& A, const CFArray& B)
480{
481 if (A.size() != B.size())
482 return false;
483 int i, n= B.size();
484 for (i= 0; i < n; i++)
485 if (A[i] != B[i])
486 return false;
487 return true;
488}
489
490/// get terms of @a F wrt. Variable (1)
491inline CFArray
493{
494 if (F.inCoeffDomain())
495 {
497 result[0]= F;
498 return result;
499 }
500 CFArray result= CFArray (size (F));
501 int j= 0;
502 Variable x= F.mvar();
503 Variable y= Variable (1);
505 for (CFIterator i= F; i.hasTerms(); i++)
506 {
507 if (i.coeff().inCoeffDomain())
508 {
509 result[j]= i.coeff()*power (x,i.exp());
510 j++;
511 }
512 else
513 {
514 for (k= i.coeff(); k.hasTerms(); k++, j++)
515 result[j]= k.coeff()*power (x,i.exp())*power (y,k.exp());
516 }
517 }
518 sort (result);
519 return result;
520}
521
522/// get terms of entries in @a F and put them in @a result
523inline
525{
526 int j= 0;
527 for (CFListIterator i= F; i.hasItem(); i++, j++)
528 result[j]= getTerms2 (i.getItem());
529}
530
531/// evaluate entries in @a A at @a eval and @a y
532inline CFArray
533evaluate (const CFArray& A, const CanonicalForm& eval, const Variable& y)
534{
535 int j= A.size();
537 for (int i= 0; i < j; i++)
538 result [i]= A[i] (eval, y);
539 return result;
540}
541
542/// s.a.
543inline CFArray*
544evaluate (CFArray* const& A, int sizeA, const CanonicalForm& eval,
545 const Variable& y)
546{
547 CFArray* result= new CFArray [sizeA];
548 for (int i= 0; i < sizeA; i++)
549 result[i]= evaluate (A[i], eval, y);
550 return result;
551}
552
553/// normalize entries in @a L with @a normalizingFactor
554inline
555CFList normalize (const CFList& L, const CFList& normalizingFactor)
556{
558 CFListIterator j= normalizingFactor;
559 for (CFListIterator i= L; i.hasItem(); i++, j++)
560 result.append (i.getItem() / j.getItem());
561 return result;
562}
563
564/// search for @a F in @a A between index @a i and @a j
565inline
566int search (const CFArray& A, const CanonicalForm& F, int i, int j)
567{
568 for (; i < j; i++)
569 if (A[i] == F)
570 return i;
571 return -1;
572}
573
574/// patch together @a F1 and @a F2 and normalize by a power of @a eval
575/// @a F1 and @a F2 are assumed to be bivariate with one variable having level 1
576inline
578 const CanonicalForm& eval)
579{
581 if (F2.level() != 1 && !F2.inCoeffDomain())
582 {
583 int d= degree (F2);
584 result *= power (F2.mvar(), d);
585 result /= power (eval, d);
586 }
587 return result;
588}
589
590/// sparse heuristic lifting by Wang and Lucks
591///
592/// @return @a LucksWangSparseHeuristic returns true if it was successful
593int
594LucksWangSparseHeuristic (const CanonicalForm& F, ///<[in] polynomial to be
595 ///< factored
596 const CFList& factors, ///<[in] factors of F
597 ///< lifted to level
598 int level, ///<[in] level of lifted
599 ///< factors
600 const CFList& leadingCoeffs,///<[in] leading
601 ///< coefficients of
602 ///< factors
603 CFList& result ///<[in,out] result
604 );
605
606/// sparse heuristic which patches together bivariate factors of @a A wrt.
607/// different second variables by their univariate images
608///
609/// @return @a sparseHeuristic returns a list of found factors of A
610CFList
611sparseHeuristic (const CanonicalForm& A, ///<[in] polynomial to be factored
612 const CFList& biFactors, ///<[in] bivariate factors of A where
613 ///< the second variable has level 2
614 CFList*& moreBiFactors, ///<[in] more bivariate factorizations
615 ///< wrt. different second variables
616 const CFList& evaluation,///<[in] evaluation point
617 int minFactorsLength ///<[in] minimal length of bivariate
618 ///< factorizations
619 );
620
621#endif
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm tailcoeff(const CanonicalForm &f)
int degree(const CanonicalForm &f)
Array< CanonicalForm > CFArray
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm Lc(const CanonicalForm &f)
int level(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
Iterators for CanonicalForm's.
map polynomials
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:41
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
This file implements functions to map between extensions of finite fields.
FILE * f
Definition: checklibs.c:9
int size() const
Definition: ftmpl_array.cc:92
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: variable.h:33
CFFListIterator iter
Definition: facAbsBiFact.cc:53
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
b *CanonicalForm B
Definition: facBivar.cc:52
CFList & eval
Definition: facFactorize.cc:47
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
int j
Definition: facHensel.cc:110
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
bool isEqual(const CFArray &A, const CFArray &B)
checks if A equals B
void groupTogether(CFArray &A, int level)
group together elements in A, where entries in A are put together if they coincide up to level level
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)
CanonicalForm simplify(const CanonicalForm &A, int level)
simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
bool isZero(const CFArray &A)
checks if entries of A are zero
void evaluate(CFArray &A, const CanonicalForm &B, int level)
evaluate every entry of A at B and level level
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors
CFList normalize(const CFList &L, const CFList &normalizingFactor)
normalize entries in L with normalizingFactor
CFList findNormalizingFactor2(CFList &biFactors, const CanonicalForm &evalPoint, const CFList &uniFactors)
find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at ev...
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
int search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
CanonicalForm patch(const CanonicalForm &F1, const CanonicalForm &F2, const CanonicalForm &eval)
patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with ...
CFArray getTerms(const CanonicalForm &F)
get terms of F
void strip(CFArray &F, CFArray &G, int level)
strip off those parts of entries in F whose level is less than or equal than level and store the stri...
void sort(CFArray &A, int l=0)
quick sort A
bool merge(CFArray &A, CFArray &B)
merge B into A if possible, i.e. every non-zero entry in A should be zero in B
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
CFArray getEquations(const CFArray &A, const CFArray &B)
get equations for LucksWangSparseHeuristic
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
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
#define M
Definition: sirandom.c:25
int F1(int a1, int &r1)
F1.
void F2(int a2, int &r2)
F2.