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" |
---|
19 | #include "templates/ftmpl_functions.h" |
---|
20 | #include "cf_algorithm.h" |
---|
21 | #include "cf_map.h" |
---|
22 | |
---|
23 | /// compare polynomials |
---|
24 | inline |
---|
25 | int 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 |
---|
50 | inline |
---|
51 | int 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 |
---|
75 | inline |
---|
76 | void 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 |
---|
84 | inline |
---|
85 | void 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 |
---|
113 | inline |
---|
114 | void 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 |
---|
122 | inline CFList |
---|
123 | findNormalizingFactor1 (const CFList& biFactors, const CanonicalForm& evalPoint, |
---|
124 | CFList& uniFactors) |
---|
125 | { |
---|
126 | CFList result; |
---|
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 |
---|
139 | inline CFList |
---|
140 | findNormalizingFactor2 (CFList& biFactors, const CanonicalForm& evalPoint, |
---|
141 | const CFList& uniFactors) |
---|
142 | { |
---|
143 | CFList result; |
---|
144 | CFList uniBiFactors= biFactors; |
---|
145 | CFList newBiFactors; |
---|
146 | CFList l; |
---|
147 | int pos; |
---|
148 | CFListIterator iter; |
---|
149 | for (iter= uniBiFactors; iter.hasItem(); iter++) |
---|
150 | { |
---|
151 | iter.getItem()= iter.getItem() (evalPoint); |
---|
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 |
---|
166 | inline CFArray |
---|
167 | getTerms (const CanonicalForm& F) |
---|
168 | { |
---|
169 | if (F.inCoeffDomain()) |
---|
170 | { |
---|
171 | CFArray result= CFArray (1); |
---|
172 | result [0]= F; |
---|
173 | return result; |
---|
174 | } |
---|
175 | if (F.isUnivariate()) |
---|
176 | { |
---|
177 | CFArray result= CFArray (size(F)); |
---|
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 |
---|
201 | inline CFArray |
---|
202 | getBiTerms_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); |
---|
210 | CFIterator j; |
---|
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 | } |
---|
227 | CFArray result= CFArray (k); |
---|
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) |
---|
235 | inline CFArray |
---|
236 | getBiTerms (const CanonicalForm& F, int threshold) |
---|
237 | { |
---|
238 | if (F.inCoeffDomain()) |
---|
239 | { |
---|
240 | CFArray result= CFArray (1); |
---|
241 | result [0]= F; |
---|
242 | return result; |
---|
243 | } |
---|
244 | if (F.isUnivariate()) |
---|
245 | { |
---|
246 | CFArray result= CFArray (size(F)); |
---|
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 |
---|
266 | inline CanonicalForm |
---|
267 | buildPolyFromArray (const CFArray& A) |
---|
268 | { |
---|
269 | CanonicalForm result= 0; |
---|
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 |
---|
277 | inline void |
---|
278 | groupTogether (CFArray& A, int level) |
---|
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 |
---|
309 | inline void |
---|
310 | strip (CFArray& F, CFArray& G, int level) |
---|
311 | { |
---|
312 | int n, m, i, j; |
---|
313 | CanonicalForm g; |
---|
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 |
---|
330 | inline void |
---|
331 | strip (CFArray& F, int level) |
---|
332 | { |
---|
333 | int n, m, i; |
---|
334 | CanonicalForm g; |
---|
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 |
---|
349 | inline |
---|
350 | CFArray getEquations (const CFArray& A, const CFArray& B) |
---|
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 |
---|
361 | inline void |
---|
362 | evaluate (CFArray& A, const CanonicalForm& B, int level) |
---|
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 |
---|
376 | inline void |
---|
377 | evaluate (CFArray& A, const CFArray& B, int level) |
---|
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 |
---|
389 | inline CanonicalForm |
---|
390 | simplify (const CanonicalForm& A, int level) |
---|
391 | { |
---|
392 | CanonicalForm F= 0; |
---|
393 | if (size (A, A.level()) == 2) |
---|
394 | { |
---|
395 | CanonicalForm C= getVars (A); |
---|
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 |
---|
411 | inline bool |
---|
412 | simplify (CFArray& A, CFArray& B, int level) |
---|
413 | { |
---|
414 | int n= A.size(); |
---|
415 | CanonicalForm f; |
---|
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 |
---|
442 | inline bool |
---|
443 | merge (CFArray& A, CFArray& B) |
---|
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 |
---|
467 | inline bool |
---|
468 | isZero (const CFArray& A) |
---|
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 |
---|
478 | inline bool |
---|
479 | isEqual (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) |
---|
491 | inline CFArray |
---|
492 | getTerms2 (const CanonicalForm& F) |
---|
493 | { |
---|
494 | if (F.inCoeffDomain()) |
---|
495 | { |
---|
496 | CFArray result= CFArray (1); |
---|
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); |
---|
504 | CFIterator k; |
---|
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 |
---|
523 | inline |
---|
524 | void getTerms2 (const CFList& F, CFArray* result) |
---|
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 |
---|
532 | inline CFArray |
---|
533 | evaluate (const CFArray& A, const CanonicalForm& eval, const Variable& y) |
---|
534 | { |
---|
535 | int j= A.size(); |
---|
536 | CFArray result= CFArray (j); |
---|
537 | for (int i= 0; i < j; i++) |
---|
538 | result [i]= A[i] (eval, y); |
---|
539 | return result; |
---|
540 | } |
---|
541 | |
---|
542 | /// s.a. |
---|
543 | inline CFArray* |
---|
544 | evaluate (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 |
---|
554 | inline |
---|
555 | CFList normalize (const CFList& L, const CFList& normalizingFactor) |
---|
556 | { |
---|
557 | CFList result; |
---|
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 |
---|
565 | inline |
---|
566 | int 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 |
---|
576 | inline |
---|
577 | CanonicalForm patch (const CanonicalForm& F1, const CanonicalForm& F2, |
---|
578 | const CanonicalForm& eval) |
---|
579 | { |
---|
580 | CanonicalForm result= F1; |
---|
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 |
---|
593 | int |
---|
594 | LucksWangSparseHeuristic (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 |
---|
610 | CFList |
---|
611 | sparseHeuristic (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 |
---|