[1a80b4] | 1 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 2 | // emacs edit mode for this file is -*- C++ -*- |
---|
[91b36d] | 3 | // $Id: MVMultiHensel.cc,v 1.19 2008-06-10 14:49:15 Singular Exp $ |
---|
[1a80b4] | 4 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 5 | // FACTORY - Includes |
---|
| 6 | #include <factory.h> |
---|
[14b1e65] | 7 | #ifndef NOSTREAMIO |
---|
[e2ca88] | 8 | #ifdef HAVE_IOSTREAM |
---|
| 9 | #include <iostream> |
---|
| 10 | #define OSTREAM std::ostream |
---|
| 11 | #define ISTREAM std::istream |
---|
| 12 | #define CERR std::cerr |
---|
| 13 | #define CIN std::cin |
---|
| 14 | #elif defined(HAVE_IOSTREAM_H) |
---|
[14b1e65] | 15 | #include <iostream.h> |
---|
[e2ca88] | 16 | #define OSTREAM ostream |
---|
| 17 | #define ISTREAM istream |
---|
| 18 | #define CERR cerr |
---|
| 19 | #define CIN cin |
---|
| 20 | #endif |
---|
[14b1e65] | 21 | #endif |
---|
[1a80b4] | 22 | // Factor - Includes |
---|
| 23 | #include "tmpl_inst.h" |
---|
| 24 | #include "helpstuff.h" |
---|
[4a81ec] | 25 | // some CC's need this: |
---|
| 26 | #include "MVMultiHensel.h" |
---|
| 27 | |
---|
| 28 | #ifdef SINGULAR |
---|
[456842] | 29 | #define HAVE_SINGULAR_ERROR |
---|
[38e7b3] | 30 | #ifndef NOSTREAMIO |
---|
| 31 | void out_cf(char *s1,const CanonicalForm &f,char *s2); |
---|
| 32 | #endif |
---|
[456842] | 33 | #endif |
---|
| 34 | |
---|
| 35 | #ifdef HAVE_SINGULAR_ERROR |
---|
[927b7e] | 36 | extern int libfac_interruptflag; |
---|
[38e7b3] | 37 | extern "C" |
---|
| 38 | { |
---|
[36b7a3] | 39 | void WerrorS(const char *); |
---|
[38e7b3] | 40 | void Werror(const char *fmt, ...); |
---|
| 41 | } |
---|
[4a81ec] | 42 | #endif |
---|
[1a80b4] | 43 | |
---|
| 44 | #ifdef HENSELDEBUG |
---|
| 45 | # define DEBUGOUTPUT |
---|
| 46 | #else |
---|
| 47 | # undef DEBUGOUTPUT |
---|
| 48 | #endif |
---|
| 49 | |
---|
| 50 | #include "debug.h" |
---|
[927b7e] | 51 | #include "interrupt.h" |
---|
[1a80b4] | 52 | #include "timing.h" |
---|
| 53 | |
---|
| 54 | /////////////////////////////////////////////////////////////// |
---|
| 55 | // some class definition needed in MVMultiHensel |
---|
| 56 | /////////////////////////////////////////////////////////////// |
---|
| 57 | typedef bool Boolean; |
---|
| 58 | |
---|
[17b2e2] | 59 | class DiophantForm |
---|
| 60 | { |
---|
[1a80b4] | 61 | public: |
---|
| 62 | CanonicalForm One; |
---|
| 63 | CanonicalForm Two; |
---|
[17b2e2] | 64 | inline DiophantForm& operator=( const DiophantForm& value ) |
---|
| 65 | { |
---|
| 66 | if ( this != &value ) |
---|
| 67 | { |
---|
[1a80b4] | 68 | One = value.One; |
---|
| 69 | Two = value.Two; |
---|
| 70 | } |
---|
| 71 | return *this; |
---|
| 72 | } |
---|
[17b2e2] | 73 | }; |
---|
[1a80b4] | 74 | |
---|
| 75 | // We remember an already calculated value; simple class for RememberArray |
---|
[17b2e2] | 76 | class RememberForm |
---|
| 77 | { |
---|
[1a80b4] | 78 | public: |
---|
[17b2e2] | 79 | inline RememberForm operator=( CanonicalForm & value ) |
---|
| 80 | { |
---|
[14b1e65] | 81 | this->calculated = true; |
---|
[1a80b4] | 82 | this->poly = value; |
---|
| 83 | return *this; |
---|
| 84 | } |
---|
[184d6d] | 85 | RememberForm() : poly(0), calculated(false) {} |
---|
[1a80b4] | 86 | Boolean calculated; |
---|
| 87 | CanonicalForm poly; |
---|
| 88 | }; |
---|
| 89 | |
---|
[14b1e65] | 90 | // Array to remember already calculated values; used for the diophantine |
---|
| 91 | // equation s*f + t*g = x^i |
---|
[17b2e2] | 92 | class RememberArray |
---|
| 93 | { |
---|
[1a80b4] | 94 | public: |
---|
| 95 | // operations performed on arrays |
---|
[17b2e2] | 96 | RememberArray( int sz ) |
---|
| 97 | { |
---|
[1a80b4] | 98 | size = sz; |
---|
| 99 | ia = new RememberForm[size]; |
---|
| 100 | // assert( ia != 0 ); // test if we got the memory |
---|
| 101 | init( sz ); |
---|
| 102 | } |
---|
| 103 | ~RememberArray(){ delete [] ia; } |
---|
[17b2e2] | 104 | inline RememberForm& operator[]( int index ) |
---|
| 105 | { |
---|
[1a80b4] | 106 | return ia[index]; |
---|
| 107 | } |
---|
[184d6d] | 108 | bool checksize(int i) {return i<size;} |
---|
[1a80b4] | 109 | protected: |
---|
[17b2e2] | 110 | void init( int ) |
---|
| 111 | { |
---|
[1a80b4] | 112 | for ( int ix=0; ix < size; ++ix) |
---|
[184d6d] | 113 | { |
---|
[1a80b4] | 114 | ia[ix].calculated=false; |
---|
[184d6d] | 115 | ia[ix].poly=0; |
---|
[38e7b3] | 116 | } |
---|
[1a80b4] | 117 | } |
---|
| 118 | // internal data representation |
---|
| 119 | int size; |
---|
| 120 | RememberForm *ia; |
---|
| 121 | }; |
---|
| 122 | |
---|
| 123 | /////////////////////////////////////////////////////////////// |
---|
| 124 | // Solve the Diophantine equation: ( levelU == mainvar ) // |
---|
| 125 | // s*F1 + t*F2 = (mainvar)^i // |
---|
| 126 | // Returns s and t. // |
---|
| 127 | /////////////////////////////////////////////////////////////// |
---|
[14b1e65] | 128 | static DiophantForm |
---|
[8de151] | 129 | diophant( int levelU , const CanonicalForm & F1 , const CanonicalForm & F2 , |
---|
| 130 | int i , RememberArray & A, RememberArray & B, |
---|
| 131 | const CanonicalForm &alpha ) |
---|
[38e7b3] | 132 | { |
---|
[1a80b4] | 133 | DiophantForm Retvalue; |
---|
| 134 | CanonicalForm s,t,q,r; |
---|
| 135 | Variable x(levelU); |
---|
| 136 | |
---|
[e2ca88] | 137 | DEBOUT(CERR, "diophant: called with: ", F1); |
---|
| 138 | DEBOUT(CERR, " ", F2); DEBOUTLN(CERR, " ", i); |
---|
[1a80b4] | 139 | |
---|
[14b1e65] | 140 | // Did we solve the diophantine equation yet? |
---|
[1a80b4] | 141 | // If so, return the calculated values |
---|
[38e7b3] | 142 | if (A.checksize(i) && A[i].calculated && B[i].calculated ) |
---|
| 143 | { |
---|
[14b1e65] | 144 | Retvalue.One=A[i].poly; |
---|
[1a80b4] | 145 | Retvalue.Two=B[i].poly; |
---|
| 146 | return Retvalue; |
---|
| 147 | } |
---|
| 148 | |
---|
| 149 | // Degrees ok? degree(F1,mainvar) + degree(F2,mainvar) <= i ? |
---|
[38e7b3] | 150 | if ( (degree(F1,levelU) + degree(F2,levelU) ) <= i ) |
---|
| 151 | { |
---|
[b6249e] | 152 | #ifdef HAVE_SINGULAR_ERROR |
---|
[927b7e] | 153 | if (!interrupt_handle()) Werror("libfac: diophant ERROR: degree too large! (%d + %d <= %d)",degree(F1,levelU), degree(F2,levelU), i); |
---|
[38e7b3] | 154 | //out_cf("F1:",F1,"\n"); |
---|
| 155 | //out_cf("F2:",F2,"\n"); |
---|
[1a80b4] | 156 | #else |
---|
[456842] | 157 | #ifndef NOSTREAMIO |
---|
[e2ca88] | 158 | CERR << "libfac: diophant ERROR: degree too large! " |
---|
| 159 | << (degree(F1,levelU) + degree(F2,levelU) ) <<"\n"; |
---|
[456842] | 160 | #else |
---|
| 161 | ; |
---|
| 162 | #endif |
---|
[1a80b4] | 163 | #endif |
---|
| 164 | Retvalue.One=F1;Retvalue.Two=F2; |
---|
| 165 | return Retvalue; |
---|
| 166 | } |
---|
| 167 | |
---|
[38e7b3] | 168 | if ( i == 0 ) |
---|
| 169 | { // call the extended gcd |
---|
[1a80b4] | 170 | r=extgcd(F1,F2,s,t); |
---|
[14b1e65] | 171 | // check if gcd(F1,F2) <> 1 , i.e. F1 and F2 are not relatively prime |
---|
[38e7b3] | 172 | if ( ! r.isOne() ) |
---|
| 173 | { |
---|
[8de151] | 174 | if (r.degree()<1) // some constant != 1 ? |
---|
| 175 | { |
---|
| 176 | Retvalue.One=s/r;Retvalue.Two=t/r; |
---|
| 177 | return Retvalue; |
---|
| 178 | } |
---|
| 179 | else if (alpha!=0) |
---|
| 180 | { |
---|
| 181 | Variable Alpha=alpha.mvar(); |
---|
| 182 | if (r.mvar()==Alpha) // from field extension ? |
---|
| 183 | { |
---|
| 184 | Variable X=rootOf(alpha); |
---|
| 185 | r=replacevar(r,Alpha,X); |
---|
| 186 | s=replacevar(s,Alpha,X); |
---|
| 187 | t=replacevar(t,Alpha,X); |
---|
| 188 | s/=r; |
---|
| 189 | t/=r; |
---|
| 190 | s=replacevar(s,X,Alpha); |
---|
| 191 | t=replacevar(t,X,Alpha); |
---|
| 192 | Retvalue.One=s; Retvalue.Two=t; |
---|
| 193 | return Retvalue; |
---|
| 194 | } |
---|
| 195 | } |
---|
[456842] | 196 | #ifdef HAVE_SINGULAR_ERROR |
---|
[927b7e] | 197 | if (!interrupt_handle()) WerrorS("libfac: diophant ERROR: F1 and F2 are not relatively prime! "); |
---|
[8de151] | 198 | #ifndef NOSTREAMIO |
---|
| 199 | out_cf("F1:",F1,"\n"); |
---|
| 200 | out_cf("F2:",F2,"\n"); |
---|
| 201 | out_cf("gcd:",r,"\n"); |
---|
| 202 | #endif |
---|
[1a80b4] | 203 | #else |
---|
[14b1e65] | 204 | #ifndef NOSTREAMIO |
---|
[e2ca88] | 205 | CERR << "libfac: diophant ERROR: " << F1 << " and " << F2 |
---|
| 206 | << " are not relatively prime!" << "\n"; |
---|
[14b1e65] | 207 | #else |
---|
[456842] | 208 | ; |
---|
[14b1e65] | 209 | #endif |
---|
[1a80b4] | 210 | #endif |
---|
[8de151] | 211 | Retvalue.One=s/r;Retvalue.Two=t/r; |
---|
[1a80b4] | 212 | return Retvalue; |
---|
| 213 | } |
---|
| 214 | Retvalue.One = s; Retvalue.Two = t; |
---|
| 215 | } |
---|
[38e7b3] | 216 | else |
---|
| 217 | { // recursively call diophant |
---|
[8de151] | 218 | Retvalue=diophant(levelU,F1,F2,i-1,A,B,alpha); |
---|
[1a80b4] | 219 | Retvalue.One *= x; // createVar(levelU,1); |
---|
| 220 | Retvalue.Two *= x; // createVar(levelU,1); |
---|
[927b7e] | 221 | |
---|
| 222 | if (interrupt_handle()) return Retvalue; |
---|
| 223 | |
---|
[1a80b4] | 224 | // Check degrees. |
---|
| 225 | |
---|
[38e7b3] | 226 | if ( degree(Retvalue.One,levelU) > degree(F2,levelU) ) |
---|
| 227 | { |
---|
[1a80b4] | 228 | // Make degree(Retvalue.one,mainvar) < degree(F2,mainvar) |
---|
| 229 | divrem(Retvalue.One,F2,q,r); |
---|
| 230 | Retvalue.One = r; Retvalue.Two += F1*q; |
---|
| 231 | } |
---|
[38e7b3] | 232 | else |
---|
| 233 | { |
---|
| 234 | if ( degree(Retvalue.Two,levelU) >= degree(F1,levelU) ) |
---|
| 235 | { |
---|
[14b1e65] | 236 | // Make degree(Retvalue.Two,mainvar) <= degree(F1,mainvar) |
---|
| 237 | divrem(Retvalue.Two,F1,q,r); |
---|
| 238 | Retvalue.One += F2*q; Retvalue.Two = r; |
---|
[1a80b4] | 239 | } |
---|
| 240 | } |
---|
| 241 | |
---|
| 242 | } |
---|
[184d6d] | 243 | if (A.checksize(i)) |
---|
| 244 | { |
---|
| 245 | A[i].poly = Retvalue.One ; |
---|
| 246 | B[i].poly = Retvalue.Two ; |
---|
| 247 | A[i].calculated = true ; B[i].calculated = true ; |
---|
| 248 | } |
---|
[e2ca88] | 249 | DEBOUT(CERR, "diophant: Returnvalue is: ", Retvalue.One); |
---|
| 250 | DEBOUTLN(CERR, " ", Retvalue.Two); |
---|
[1a80b4] | 251 | |
---|
| 252 | return Retvalue; |
---|
| 253 | } |
---|
| 254 | |
---|
| 255 | /////////////////////////////////////////////////////////////// |
---|
| 256 | // A more efficient way to solve s*F1 + t*F2 = W // |
---|
| 257 | // as in Wang and Rothschild [Wang&Roth75]. // |
---|
| 258 | /////////////////////////////////////////////////////////////// |
---|
[14b1e65] | 259 | static CanonicalForm |
---|
| 260 | make_delta( int levelU, const CanonicalForm & W, |
---|
| 261 | const CanonicalForm & F1, const CanonicalForm & F2, |
---|
[8de151] | 262 | RememberArray & A, RememberArray & B, |
---|
| 263 | const CanonicalForm &alpha) |
---|
| 264 | { |
---|
[1a80b4] | 265 | CanonicalForm Retvalue; |
---|
| 266 | DiophantForm intermediate; |
---|
| 267 | |
---|
[e2ca88] | 268 | DEBOUT(CERR, "make_delta: W= ", W); |
---|
| 269 | DEBOUTLN(CERR, " degree(W,levelU)= ", degree(W,levelU) ); |
---|
[1a80b4] | 270 | |
---|
[8de151] | 271 | if ( levelU == level(W) ) // same level, good |
---|
| 272 | { |
---|
| 273 | for ( CFIterator i=W; i.hasTerms(); i++) |
---|
| 274 | { |
---|
| 275 | intermediate=diophant(levelU,F1,F2,i.exp(),A,B,alpha); |
---|
[184d6d] | 276 | Retvalue += intermediate.One * i.coeff(); |
---|
[927b7e] | 277 | |
---|
| 278 | if (interrupt_handle()) return Retvalue; |
---|
[1a80b4] | 279 | } |
---|
| 280 | } |
---|
[8de151] | 281 | else // level(W) < levelU ; i.e. degree(w,levelU) == 0 |
---|
| 282 | { |
---|
| 283 | intermediate=diophant(levelU,F1,F2,0,A,B,alpha); |
---|
[1a80b4] | 284 | Retvalue = W * intermediate.One; |
---|
| 285 | } |
---|
[e2ca88] | 286 | DEBOUTLN(CERR, "make_delta: Returnvalue= ", Retvalue); |
---|
[1a80b4] | 287 | return Retvalue; |
---|
| 288 | } |
---|
| 289 | |
---|
[14b1e65] | 290 | static CanonicalForm |
---|
| 291 | make_square( int levelU, const CanonicalForm & W, |
---|
| 292 | const CanonicalForm & F1, const CanonicalForm & F2, |
---|
[8de151] | 293 | RememberArray & A, RememberArray & B,const CanonicalForm &alpha) |
---|
| 294 | { |
---|
[1a80b4] | 295 | CanonicalForm Retvalue; |
---|
| 296 | DiophantForm intermediate; |
---|
| 297 | |
---|
[e2ca88] | 298 | DEBOUT(CERR, "make_square: W= ", W ); |
---|
| 299 | DEBOUTLN(CERR, " degree(W,levelU)= ", degree(W,levelU)); |
---|
[1a80b4] | 300 | |
---|
[17b2e2] | 301 | if ( levelU == level(W) ) // same level, good |
---|
| 302 | { |
---|
| 303 | for ( CFIterator i=W; i.hasTerms(); i++) |
---|
| 304 | { |
---|
[8de151] | 305 | intermediate=diophant(levelU,F1,F2,i.exp(),A,B,alpha); |
---|
[1a80b4] | 306 | Retvalue += i.coeff() * intermediate.Two; |
---|
[927b7e] | 307 | |
---|
| 308 | if (interrupt_handle()) return Retvalue; |
---|
[1a80b4] | 309 | } |
---|
| 310 | } |
---|
[17b2e2] | 311 | else // level(W) < levelU ; i.e. degree(w,levelU) == 0 |
---|
| 312 | { |
---|
[8de151] | 313 | intermediate=diophant(levelU,F1,F2,0,A,B,alpha); |
---|
[1a80b4] | 314 | Retvalue = W * intermediate.Two; |
---|
| 315 | } |
---|
[e2ca88] | 316 | DEBOUTLN(CERR, "make_square: Returnvalue= ", Retvalue); |
---|
[1a80b4] | 317 | |
---|
| 318 | return Retvalue; |
---|
| 319 | } |
---|
| 320 | |
---|
| 321 | |
---|
| 322 | /////////////////////////////////////////////////////////////// |
---|
| 323 | // Multivariat Hensel routine for two factors F and G . // |
---|
| 324 | // U is the monic univariat polynomial; we manage two arrays // |
---|
| 325 | // to remember already calculated values for the diophantine // |
---|
| 326 | // equation. This is suggested by Joel Moses [Moses71] . // |
---|
| 327 | // Return the fully lifted factors. // |
---|
| 328 | /////////////////////////////////////////////////////////////// |
---|
[14b1e65] | 329 | static DiophantForm |
---|
| 330 | mvhensel( const CanonicalForm & U , const CanonicalForm & F , |
---|
[8de151] | 331 | const CanonicalForm & G , const SFormList & Substitutionlist, |
---|
| 332 | const CanonicalForm &alpha) |
---|
| 333 | { |
---|
[1a80b4] | 334 | CanonicalForm V,Fk=F,Gk=G,Rk,W,D,S; |
---|
[e89e56] | 335 | int levelU=level(U), degU=subvardegree(U,levelU); // degree(U,{x_1,..,x_(level(U)-1)}) |
---|
[1a80b4] | 336 | DiophantForm Retvalue; |
---|
[184d6d] | 337 | RememberArray A(degree(F,levelU)+degree(G,levelU)+1); |
---|
| 338 | RememberArray B(degree(F,levelU)+degree(G,levelU)+1); |
---|
[1a80b4] | 339 | |
---|
[e2ca88] | 340 | DEBOUTLN(CERR, "mvhensel called with: U= ", U); |
---|
| 341 | DEBOUTLN(CERR, " F= ", F); |
---|
| 342 | DEBOUTLN(CERR, " G= ", G); |
---|
| 343 | DEBOUTLN(CERR, " degU= ", degU); |
---|
[1a80b4] | 344 | |
---|
| 345 | V=change_poly(U,Substitutionlist,0); // change x_i <- x_i + a_i for all i |
---|
| 346 | Rk = F*G-V; |
---|
| 347 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 348 | CERR << "mvhensel: V = " << V << "\n" |
---|
| 349 | << " Fk= " << F << "\n" |
---|
| 350 | << " Gk= " << G << "\n" |
---|
| 351 | << " Rk= " << Rk << "\n"; |
---|
[1a80b4] | 352 | #endif |
---|
[8de151] | 353 | for ( int k=2; k<=degU+1; k++) |
---|
| 354 | { |
---|
[1a80b4] | 355 | W = mod_power(Rk,k,levelU); |
---|
| 356 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 357 | CERR << "mvhensel: Iteration: " << k << "\n"; |
---|
| 358 | CERR << "mvhensel: W= " << W << "\n"; |
---|
[1a80b4] | 359 | #endif |
---|
[8de151] | 360 | D = make_delta(levelU,W,F,G,A,B,alpha); |
---|
[1a80b4] | 361 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 362 | CERR << "mvhensel: D= " << D << "\n"; |
---|
[1a80b4] | 363 | #endif |
---|
[8de151] | 364 | S = make_square(levelU,W,F,G,A,B,alpha); |
---|
[1a80b4] | 365 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 366 | CERR << "mvhensel: S= " << S << "\n"; |
---|
[1a80b4] | 367 | #endif |
---|
| 368 | Rk += S*D - D*Fk - S*Gk; |
---|
| 369 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 370 | CERR << "mvhensel: Rk= " << Rk << "\n"; |
---|
[1a80b4] | 371 | #endif |
---|
| 372 | Fk -= S; |
---|
| 373 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 374 | CERR << "mvhensel: Fk= " << Fk << "\n"; |
---|
[1a80b4] | 375 | #endif |
---|
| 376 | Gk -= D; |
---|
| 377 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 378 | CERR << "mvhensel: Gk= " << Gk << "\n"; |
---|
[1a80b4] | 379 | #endif |
---|
| 380 | if ( Rk.isZero() ) break; |
---|
[927b7e] | 381 | if (interrupt_handle()) break; |
---|
[1a80b4] | 382 | } |
---|
| 383 | Retvalue.One = change_poly(Fk,Substitutionlist,1); |
---|
| 384 | Retvalue.Two = change_poly(Gk,Substitutionlist,1); |
---|
| 385 | |
---|
[e2ca88] | 386 | DEBOUTLN(CERR, "mvhensel: Retvalue: ", Retvalue.One); |
---|
| 387 | DEBOUTLN(CERR, " ", Retvalue.Two); |
---|
[1a80b4] | 388 | |
---|
| 389 | return Retvalue ; |
---|
| 390 | } |
---|
| 391 | |
---|
| 392 | /////////////////////////////////////////////////////////////// |
---|
| 393 | // Recursive Version of MultiHensel. // |
---|
| 394 | /////////////////////////////////////////////////////////////// |
---|
[14b1e65] | 395 | CFFList |
---|
| 396 | multihensel( const CanonicalForm & mF, const CFFList & Factorlist, |
---|
[8de151] | 397 | const SFormList & Substitutionlist, |
---|
| 398 | const CanonicalForm &alpha) |
---|
| 399 | { |
---|
[1a80b4] | 400 | CFFList Returnlist,factorlist=Factorlist; |
---|
| 401 | DiophantForm intermediat; |
---|
| 402 | CanonicalForm Pl,Pr; |
---|
| 403 | int n = factorlist.length(); |
---|
| 404 | |
---|
[e2ca88] | 405 | DEBOUT(CERR, "multihensel: called with ", mF); |
---|
| 406 | DEBOUTLN(CERR, " ", factorlist); |
---|
[1a80b4] | 407 | |
---|
[17b2e2] | 408 | if ( n == 1 ) |
---|
| 409 | { |
---|
[1a80b4] | 410 | Returnlist.append(CFFactor(mF,1)); |
---|
| 411 | } |
---|
[17b2e2] | 412 | else |
---|
| 413 | { |
---|
| 414 | if ( n == 2 ) |
---|
| 415 | { |
---|
[14b1e65] | 416 | intermediat= mvhensel(mF, factorlist.getFirst().factor(), |
---|
| 417 | Factorlist.getLast().factor(), |
---|
[8de151] | 418 | Substitutionlist,alpha); |
---|
[1a80b4] | 419 | Returnlist.append(CFFactor(intermediat.One,1)); |
---|
| 420 | Returnlist.append(CFFactor(intermediat.Two,1)); |
---|
| 421 | } |
---|
[17b2e2] | 422 | else // more then two factors |
---|
| 423 | { |
---|
[1a80b4] | 424 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 425 | CERR << "multihensel: more than two factors!" << "\n"; |
---|
[1a80b4] | 426 | #endif |
---|
| 427 | Pl=factorlist.getFirst().factor(); factorlist.removeFirst(); |
---|
| 428 | Pr=Pl.genOne(); |
---|
| 429 | for ( ListIterator<CFFactor> i=factorlist; i.hasItem(); i++ ) |
---|
[14b1e65] | 430 | Pr *= i.getItem().factor() ; |
---|
[1a80b4] | 431 | #ifdef HENSELDEBUG2 |
---|
[e2ca88] | 432 | CERR << "multihensel: Pl,Pr, factorlist: " << Pl << " " << Pr |
---|
| 433 | << " " << factorlist << "\n"; |
---|
[1a80b4] | 434 | #endif |
---|
[8de151] | 435 | intermediat= mvhensel(mF,Pl,Pr,Substitutionlist,alpha); |
---|
[1a80b4] | 436 | Returnlist.append(CFFactor(intermediat.One,1)); |
---|
[8de151] | 437 | Returnlist=Union( multihensel(intermediat.Two,factorlist,Substitutionlist,alpha), |
---|
| 438 | Returnlist); |
---|
[1a80b4] | 439 | } |
---|
| 440 | } |
---|
| 441 | return Returnlist; |
---|
| 442 | } |
---|
| 443 | |
---|
| 444 | /////////////////////////////////////////////////////////////// |
---|
| 445 | // Generalized Hensel routine. // |
---|
| 446 | // mF is the monic multivariat polynomial, Factorlist is the // |
---|
| 447 | // list of factors, Substitutionlist represents the ideal // |
---|
| 448 | // <x_1+a_1, .. , x_r+a_r>, where r=level(mF)-1 . // |
---|
| 449 | // Returns the list of fully lifted factors. // |
---|
| 450 | /////////////////////////////////////////////////////////////// |
---|
[14b1e65] | 451 | CFFList |
---|
| 452 | MultiHensel( const CanonicalForm & mF, const CFFList & Factorlist, |
---|
[8de151] | 453 | const SFormList & Substitutionlist, const CanonicalForm &alpha) |
---|
| 454 | { |
---|
[17b2e2] | 455 | CFFList Ll; |
---|
| 456 | CFFList Returnlist,Retlistinter,factorlist=Factorlist; |
---|
[1a80b4] | 457 | CFFListIterator i; |
---|
| 458 | DiophantForm intermediat; |
---|
| 459 | CanonicalForm Pl,Pr; |
---|
| 460 | int n = factorlist.length(),h=n/2, k; |
---|
| 461 | |
---|
[e2ca88] | 462 | DEBOUT(CERR, "MultiHensel: called with ", mF); |
---|
| 463 | DEBOUTLN(CERR, " ", factorlist); |
---|
| 464 | DEBOUT(CERR," : n,h = ", n); |
---|
| 465 | DEBOUTLN(CERR," ", h); |
---|
[1a80b4] | 466 | |
---|
[8de151] | 467 | if ( n == 1 ) |
---|
| 468 | { |
---|
[1a80b4] | 469 | Returnlist.append(CFFactor(mF,1)); |
---|
| 470 | } |
---|
[8de151] | 471 | else |
---|
| 472 | { |
---|
| 473 | if ( n == 2 ) |
---|
| 474 | { |
---|
[14b1e65] | 475 | intermediat= mvhensel(mF, factorlist.getFirst().factor(), |
---|
| 476 | Factorlist.getLast().factor(), |
---|
[8de151] | 477 | Substitutionlist,alpha); |
---|
[1a80b4] | 478 | Returnlist.append(CFFactor(intermediat.One,1)); |
---|
| 479 | Returnlist.append(CFFactor(intermediat.Two,1)); |
---|
| 480 | } |
---|
[8de151] | 481 | else // more then two factors |
---|
| 482 | { |
---|
| 483 | for ( k=1 ; k<=h; k++) |
---|
| 484 | { |
---|
[14b1e65] | 485 | Ll.append(factorlist.getFirst()); |
---|
| 486 | factorlist.removeFirst(); |
---|
[1a80b4] | 487 | } |
---|
| 488 | |
---|
[e2ca88] | 489 | DEBOUTLN(CERR, "MultiHensel: Ll= ", Ll); |
---|
| 490 | DEBOUTLN(CERR, " factorlist= ", factorlist); |
---|
[1a80b4] | 491 | |
---|
| 492 | Pl = 1; Pr = 1; |
---|
| 493 | for ( i = Ll; i.hasItem(); i++) |
---|
[14b1e65] | 494 | Pl *= i.getItem().factor(); |
---|
[e2ca88] | 495 | DEBOUTLN(CERR, "MultiHensel: Pl= ", Pl); |
---|
[1a80b4] | 496 | for ( i = factorlist; i.hasItem(); i++) |
---|
[14b1e65] | 497 | Pr *= i.getItem().factor(); |
---|
[e2ca88] | 498 | DEBOUTLN(CERR, "MultiHensel: Pr= ", Pr); |
---|
[8de151] | 499 | intermediat = mvhensel(mF,Pl,Pr,Substitutionlist,alpha); |
---|
[1a80b4] | 500 | // divison test for intermediat.One and intermediat.Two ? |
---|
| 501 | CanonicalForm a,b; |
---|
| 502 | // we add a division test now for intermediat.One and intermediat.Two |
---|
[e89e56] | 503 | if ( mydivremt (mF,intermediat.One,a,b) && b == mF.genZero() ) |
---|
[14b1e65] | 504 | Retlistinter.append(CFFactor(intermediat.One,1) ); |
---|
[e89e56] | 505 | if ( mydivremt (mF,intermediat.Two,a,b) && b == mF.genZero() ) |
---|
[14b1e65] | 506 | Retlistinter.append(CFFactor(intermediat.Two,1) ); |
---|
[1a80b4] | 507 | |
---|
[8de151] | 508 | Ll = MultiHensel(intermediat.One, Ll, Substitutionlist,alpha); |
---|
| 509 | Returnlist = MultiHensel(intermediat.Two, factorlist, Substitutionlist,alpha); |
---|
[1a80b4] | 510 | Returnlist = Union(Returnlist,Ll); |
---|
| 511 | |
---|
| 512 | Returnlist = Union(Retlistinter,Returnlist); |
---|
| 513 | |
---|
| 514 | } |
---|
| 515 | } |
---|
| 516 | return Returnlist; |
---|
| 517 | } |
---|
| 518 | |
---|
| 519 | /* |
---|
| 520 | $Log: not supported by cvs2svn $ |
---|
[91b36d] | 521 | Revision 1.18 2008/03/18 17:46:15 Singular |
---|
| 522 | *hannes: gcc 4.2 |
---|
| 523 | |
---|
[36b7a3] | 524 | Revision 1.17 2008/03/17 17:44:16 Singular |
---|
| 525 | *hannes: fact.tst |
---|
| 526 | |
---|
[b429551] | 527 | Revision 1.14 2007/06/14 14:16:35 Singular |
---|
| 528 | *hannes: Factorize2 etc. |
---|
| 529 | |
---|
[927b7e] | 530 | Revision 1.13 2007/05/25 16:02:02 Singular |
---|
| 531 | *hannes: removed diophant_error, format |
---|
| 532 | |
---|
[7fa52c2] | 533 | Revision 1.12 2007/05/22 14:30:53 Singular |
---|
| 534 | *hannes: diophant_error |
---|
| 535 | |
---|
[17b2e2] | 536 | Revision 1.11 2007/05/21 16:40:12 Singular |
---|
| 537 | *hannes: Factorize2 |
---|
| 538 | |
---|
[8de151] | 539 | Revision 1.10 2007/05/15 14:46:49 Singular |
---|
| 540 | *hannes: factorize in Zp(a)[x...] |
---|
| 541 | |
---|
[38e7b3] | 542 | Revision 1.9 2006/05/16 14:46:49 Singular |
---|
| 543 | *hannes: gcc 4.1 fixes |
---|
| 544 | |
---|
[e2ca88] | 545 | Revision 1.8 2002/07/30 15:11:19 Singular |
---|
| 546 | *hannes: minor cleanups |
---|
| 547 | |
---|
[184d6d] | 548 | Revision 1.7 2001/08/22 14:21:17 Singular |
---|
| 549 | *hannes: added search for main var to Factorize |
---|
| 550 | |
---|
[b6249e] | 551 | Revision 1.6 2001/08/08 14:26:55 Singular |
---|
| 552 | *hannes: Dan's HAVE_SINGULAR_ERROR |
---|
| 553 | |
---|
[456842] | 554 | Revision 1.5 2001/08/08 11:59:12 Singular |
---|
| 555 | *hannes: Dan's NOSTREAMIO changes |
---|
| 556 | |
---|
[14b1e65] | 557 | Revision 1.4 1997/11/18 16:39:05 Singular |
---|
| 558 | * hannes: moved WerrorS from C++ to C |
---|
| 559 | (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc) |
---|
| 560 | |
---|
[7d889c] | 561 | Revision 1.3 1997/09/12 07:19:48 Singular |
---|
| 562 | * hannes/michael: libfac-0.3.0 |
---|
| 563 | |
---|
[1a80b4] | 564 | Revision 1.4 1997/04/25 22:40:02 michael |
---|
| 565 | changed cerr and cout messages for use with Singular |
---|
| 566 | Version for libfac-0.2.1 |
---|
| 567 | |
---|
| 568 | */ |
---|