[91788c0] | 1 | /*****************************************************************************\ |
---|
| 2 | * Computer Algebra System SINGULAR |
---|
| 3 | \*****************************************************************************/ |
---|
[abddbe] | 4 | /** @file facSparseHensel.h |
---|
[91788c0] | 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" |
---|
[7b5cb2] | 20 | #include "cf_algorithm.h" |
---|
| 21 | #include "cf_map.h" |
---|
[91788c0] | 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 |
---|
[7b5cb2] | 85 | void quickSort (int lo, int hi, CFArray& A, int l) |
---|
[91788c0] | 86 | { |
---|
| 87 | int i= lo, j= hi; |
---|
| 88 | CanonicalForm tmp= A[(lo+hi)/2]; |
---|
| 89 | while (i <= j) |
---|
| 90 | { |
---|
[7b5cb2] | 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 | } |
---|
[91788c0] | 101 | if (i <= j) |
---|
| 102 | { |
---|
| 103 | swap (A, i, j); |
---|
| 104 | i++; |
---|
| 105 | j--; |
---|
| 106 | } |
---|
| 107 | } |
---|
[7b5cb2] | 108 | if (lo < j) quickSort (lo, j, A, l); |
---|
| 109 | if (i < hi) quickSort (i, hi, A, l); |
---|
[91788c0] | 110 | } |
---|
| 111 | |
---|
| 112 | /// quick sort @a A |
---|
| 113 | inline |
---|
[7b5cb2] | 114 | void sort (CFArray& A, int l= 0) |
---|
[91788c0] | 115 | { |
---|
[7b5cb2] | 116 | quickSort (0, A.size() - 1, A, l); |
---|
[91788c0] | 117 | } |
---|
| 118 | |
---|
[7b5cb2] | 119 | |
---|
[91788c0] | 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 | |
---|
[7b5cb2] | 200 | /// helper function for getBiTerms |
---|
| 201 | inline CFArray |
---|
[f377d6] | 202 | getBiTerms_helper (const CanonicalForm& F, const CFMap& M, int threshold) |
---|
[7b5cb2] | 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++; |
---|
[f377d6] | 217 | if (k > threshold) |
---|
| 218 | break; |
---|
[7b5cb2] | 219 | continue; |
---|
| 220 | } |
---|
| 221 | j= i.coeff(); |
---|
[f377d6] | 222 | for (;j.hasTerms() && k <= threshold; j++, k++) |
---|
[7b5cb2] | 223 | buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff()); |
---|
[f377d6] | 224 | if (k > threshold) |
---|
| 225 | break; |
---|
[7b5cb2] | 226 | } |
---|
| 227 | CFArray result= CFArray (k); |
---|
[f377d6] | 228 | for (int i= 0; i < k && k <= threshold; i++) |
---|
[7b5cb2] | 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 |
---|
[f377d6] | 236 | getBiTerms (const CanonicalForm& F, int threshold) |
---|
[7b5cb2] | 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 | |
---|
[f377d6] | 261 | CFArray result= getBiTerms_helper (G, M, threshold); |
---|
[7b5cb2] | 262 | return result; |
---|
| 263 | } |
---|
| 264 | |
---|
[91788c0] | 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 | |
---|
[7b5cb2] | 275 | /// group together elements in @a A, where entries in @a A are put together |
---|
[91788c0] | 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 | } |
---|
[7b5cb2] | 291 | if (A[n].isZero()) |
---|
| 292 | k--; |
---|
[91788c0] | 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) |
---|
[b0734f1] | 400 | { |
---|
| 401 | CanonicalForm quot; |
---|
| 402 | if (fdivides (B, A, quot)) |
---|
| 403 | F= -tailcoeff (quot); |
---|
| 404 | } |
---|
[91788c0] | 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 | { |
---|
[2f6b737] | 494 | if (F.inCoeffDomain()) |
---|
| 495 | { |
---|
| 496 | CFArray result= CFArray (1); |
---|
| 497 | result[0]= F; |
---|
| 498 | return result; |
---|
| 499 | } |
---|
[91788c0] | 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 | { |
---|
[2f6b737] | 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 | } |
---|
[91788c0] | 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; |
---|
[2f6b737] | 581 | if (F2.level() != 1 && !F2.inCoeffDomain()) |
---|
[91788c0] | 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 |
---|
[7b5cb2] | 593 | int |
---|
[91788c0] | 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 |
---|