# source:git/Singular/LIB/presolve.lib@0bc582c

spielwiese
Last change on this file since 0bc582c was 0bc582c, checked in by Frank Seelisch <seelisch@…>, 14 years ago
removed some docu bugs prior to release 3-1-0 git-svn-id: file:///usr/local/Singular/svn/trunk@11624 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 49.8 KB
Line
1///////////////////////////////////////////////////////////////////////////////
2version="\$Id: presolve.lib,v 1.29 2009-04-06 09:17:01 seelisch Exp \$";
3category="Symbolic-numerical solving";
4info="
5LIBRARY:  presolve.lib     Pre-Solving of Polynomial Equations
6AUTHOR:   Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de,
7
8PROCEDURES:
9 degreepart(id,d1,d2);  elements of id of total degree >= d1 and <= d2, and rest
10 elimlinearpart(id);    linear part eliminated from id
11 elimpart(id[,n]);      partial elimination of vars [among first n vars]
12 elimpartanyr(i,p);     factors of p partially eliminated from i in any ring
13 fastelim(i,p[..]);     fast elimination of factors of p from i [options]
15 hilbvec(id[,c,o]);     intvec of Hilberseries of id [in char c and ord o]
16 linearpart(id);        elements of id of total degree <=1
17 tolessvars(id[,]);     maps id to new basering having only vars occuring in id
18 solvelinearpart(id);   reduced std-basis of linear part of id
19 sortandmap(id[..]);    map to new basering with vars sorted w.r.t. complexity
20 sortvars(id[n1,p1..]); sort vars w.r.t. complexity in id [different blocks]
21 valvars(id[..]);       valuation of vars w.r.t. to their complexity in id
22 idealSplit(id,tF,fS);  a list of ideals such that their intersection
23                        has the same radical as id
24                       ( parameters in square brackets [] are optional)
25";
26
27LIB "inout.lib";
28LIB "general.lib";
29LIB "matrix.lib";
30LIB "ring.lib";
31LIB "elim.lib";
32///////////////////////////////////////////////////////////////////////////////
33proc shortid (id,int n,list #)
34"USAGE:   shortid(id,n[,e]); id= ideal/module, n,e=integers
35RETURN:  - if called with two arguments or e=0:
36@*       same type as id, containing generators of id having <= n terms.
37@*       - if called with three arguments and e!=0:
38@*       a list L:
39@*       L[1]: same type as id, containing generators of id having <= n terms.
40@*       L[2]: number of corresponding generator of id
41NOTE:    May be used to compute partial standard basis in case id is to hard
42EXAMPLE: example shortid; shows an example
43"
44{
45  intvec v;
46  int ii;
47  for(ii=1; ii<=ncols(id); ii++)
48  {
49   if (size(id[ii]) <=n and id[ii]!=0 )
50   {
51     v=v,ii;
52   }
53   if (size(id[ii]) > n )
54   {
55       id[ii]=0;
56   }
57  }
58  if( size(v)>1 )
59  {
60    v = v[2..size(v)];
61  }
62  id = simplify(id,2);
63  list L = id,v;
64  if ( size(#)==0 )
65  {
66    return(id);
67  }
68  if ( size(#)!=0 )
69  {
70    if(#[1]==0)
71    {
72      return(id);
73    }
74    if(#[1]!=0)
75    {
76      return(L);
77    }
78  }
79}
80example
81{ "EXAMPLE:"; echo = 2;
82   ring s=0,(x,y,z,w),dp;
83   ideal i = (x3+y2+yw2)^2,(xz+z2)^2,xyz-w2-xzw;
84   shortid(i,3);
85}
86///////////////////////////////////////////////////////////////////////////////
87
88proc degreepart (id,int d1,int d2,list #)
89"USAGE:   degreepart(id,d1,d2[,v]);  id=ideal/module, d1,d1=integers, v=intvec
90RETURN:  list of size 2,
91         _[1]: generators of id of [v-weighted] total degree >= d1 and <= d2
92          (default: v = 1,...,1)
93         _[2]: remaining generators of id
94EXAMPLE: example degreepart; shows an example
95"
96{
97   if( typeof(id)=="int" or typeof(id)=="number" or typeof(id)=="ideal" )
98   {
99      ideal dpart = ideal(id);
100   }
101   if( typeof(id)=="intmat" or typeof(id)=="matrix" or typeof(id)=="module")
102   {
103      module dpart = module(id);
104   }
105
106   def epart = dpart;
107   int s,ii = ncols(id),0;
108   if ( size(#)==0 )
109   {
110      for ( ii=1; ii<=s; ii++ )
111      {
112         dpart[ii] = (jet(id[ii],d1-1)==0)*(id[ii]==jet(id[ii],d2))*id[ii];
113         epart[ii] = (size(dpart[ii])==0) * id[ii];
114      }
115   }
116   else
117   {
118      for ( ii=1; ii<=s; ii=ii+1 )
119      {
120      dpart[ii]=(jet(id[ii],d1-1,#[1])==0)*(id[ii]==jet(id[ii],d2,#[1]))*id[ii];
121       epart[ii] = (size(dpart[ii])==0)*id[ii];
122      }
123   }
124   list L = simplify(dpart,2),simplify(epart,2);
125   return(L);
126}
127example
128{ "EXAMPLE:"; echo = 2;
129   ring r=0,(x,y,z),dp;
130   ideal i=1+x+x2+x3+x4,3,xz+y3+z8;
131   degreepart(i,0,4);
132
133   module m=[x,y,z],x*[x3,y2,z],[1,x2,z3,0,1];
134   intvec v=2,3,6;
135   show(degreepart(m,8,8,v));
136}
137///////////////////////////////////////////////////////////////////////////////
138
139proc linearpart (id)
140"USAGE:   linearpart(id);  id=ideal/module
141RETURN:  list of size 2,
142         _[1]: generators of id of total degree <= 1
143         _[2]: remaining generators of id
144EXAMPLE: example linearpart; shows an example
145"
146{
147   return(degreepart(id,0,1));
148}
149example
150{ "EXAMPLE:"; echo = 2;
151   ring r=0,(x,y,z),dp;
152   ideal i=1+x+x2+x3,3,x+3y+5z;
153   linearpart(i);
154
155   module m=[x,y,z],x*[x3,y2,z],[1,x2,z3,0,1];
156   show(linearpart(m));
157}
158///////////////////////////////////////////////////////////////////////////////
159
160proc elimlinearpart (ideal i,list #)
161"USAGE:   elimlinearpart(i[,n]);  i=ideal, n=integer,@*
162          default: n=nvars(basering)
163RETURN:   list L with 5 entries:
164  @format
165  L[1]: ideal obtained from i by substituting from the first n variables those
166        which appear in a linear part of i, by putting this part into triangular
167        form
168  L[2]: ideal of variables which have been substituted
169  L[3]: ideal, j-th element defines substitution of j-th var in [2]
170  L[4]: ideal of variables of basering, eliminated ones are set to 0
171  L[5]: ideal, describing the map from the basering to itself such that
172        L[1] is the image of i
173  @end format
174NOTE:    the procedure always interreduces the ideal i internally w.r.t.
175         ordering dp.
176EXAMPLE: example elimlinearpart; shows an example
177"
178{
179   int ii,n,k;
180   string o, newo;
181   intvec getoption = option(get);
182   option(redSB);
183   def BAS = basering;
184   n = nvars(BAS);
185   list gnirlist = ringlist(basering);
186   list g3 = gnirlist[3];
187   list g32 = g3[size(g3)];
188
189//---------------------------------- start ------------------------------------
190   if ( size(#)!=0 ) {  n=#[1]; }
191   ideal maxi,rest = maxideal(1),0;
192   if ( n < nvars(BAS) )
193   {
194      rest = maxi[n+1..nvars(BAS)];
195   }
196   attrib(rest,"isSB",1);
197
198//-------------------- find linear part and reduce rest ----------------------
199// Perhaps for big systems, check only those generators of id
200// which do not contain elements not to be eliminated
201
202   //ideal id = interred(i);
203   //## gmg, gendert 9/2008: interred sehr lange z.B. bei Leonard1 in normal,
204   //daher interred ersetzt durch: std nur auf linearpart angewendet
205   //Ordnung muss global sein, sonst egal (da Lin affin linear)
206
207//--------------- replace ordering by dp if it is not global -----------------
208   if ( ord_test(BAS) <= 0 )
209   {
210      intvec V;
211      V[n]=0; V=V+1;                          //weights for dp ordering
212      gnirlist[3] = list("dp",V), g32;
213      def newBAS = ring(gnirlist);            //change of ring to dp ordering
214      setring newBAS;
215      ideal i = imap(BAS,i);
216   }
217
218   list  Lin = linearpart(i);
219   ideal lin = std(Lin[1]);          //SB of ideal generated by polys of i
220                                     //having at most degree 1
221   ideal id = Lin[2];                //remaining polys from i, of deg > 1
222   id = simplify(NF(id,lin),2);      //instead of subst
223   ideal id1 = linearpart(id)[1];
224   while( size(id1) != 0 )           //repeat to find linear parts
225   {
226      lin = lin,id1;
227      lin = std(lin);
228      id = simplify(NF(id,lin),2);   //instead of subst
229      id1 = linearpart(id)[1];
230   }
231//------------- check for special case of unit ideal and return ---------------
232   int check;
233   if( lin[1] == 1 )
234   {
235     check = 1;
236   }
237   else
238   {
239     for (ii=1; ii<=size(id); ii++ )
240     {
241       if ( id[ii] == 1 )
242       {
243         check = 1; break;
244        }
245      }
246    }
247
248   if (check == 1)        //case of a unit ideal
249   {
250     setring BAS;
251     list L = ideal(1), ideal(0), ideal(0), maxideal(1), maxideal(1);
252     option(set,getoption);
253     return(L);
254   }
255//----- remove generators from lin containing vars not to be eliminated  ------
256   if ( n < nvars(BAS) )
257   {
258      for ( ii=1; ii<=size(lin); ii++ )
259      {
260         if ( reduce(lead(lin[ii]),rest) == 0 )
261         {
262            id=lin[ii],id;
263            lin[ii] = 0;
264         }
265      }
266   }
267   lin = simplify(lin,1);
268   ideal eva = lead(lin);               //vars to be eliminated
269   attrib(eva,"isSB",1);
270   ideal neva = NF(maxideal(1),eva);    //vars not to be eliminated
271//------------------ go back to original ring end return  ---------------------
272
273   if ( ord_test(BAS) <= 0  )           //i.e there was a ring change
274   {
275      setring BAS;
276      ideal id = imap(newBAS,id);
277      ideal eva = imap(newBAS,eva);
278      ideal lin = imap(newBAS,lin);
279      ideal neva = imap(newBAS,neva);
280   }
281
282   eva = eva[ncols(eva)..1];  // sorting according to variables in basering
283   lin = lin[ncols(lin)..1];
284   ideal phi = neva;
285   k = 1;
286   for( ii=1; ii<=n; ii++ )
287   {
288      if( neva[ii] == 0 )
289      {
290         phi[ii] = eva[k]-lin[k];
291         k=k+1;
292      }
293   }
294
295   list L = id, eva, lin, neva, phi;
296   option(set,getoption);
297   return(L);
298}
299example
300{ "EXAMPLE:"; echo = 2;
301   ring s=0,(u,x,y,z),dp;
302   ideal i = u3+y3+z-x,x2y2+z3,y+z+1,y+u;
303   elimlinearpart(i);
304}
305///////////////////////////////////////////////////////////////////////////////
306proc elimpart (ideal i,list #)
307"USAGE:   elimpart(i [,n,e] );  i=ideal, n,e=integers
308         n   : only the first n vars are considered for substitution,@*
309         e =0: substitute from linear part of i (same as elimlinearpart)@*
310         e!=0: eliminate also by direct substitution@*
311         (default: n = nvars(basering), e = 1)
312RETURN:  list of 5 objects:
313  @format
314  [1]: ideal obtained by substituting from the first n variables those
315       from i, which appear in the linear part of i (or, if e!=0, which
316       can be expressed directly in the remaining vars)
317  [2]: ideal, variables which have been substituted
318  [3]: ideal, i-th element defines substitution of i-th var in [2]
319  [4]: ideal of variables of basering, substituted ones are set to 0
320  [5]: ideal, describing the map from the basering, say k[x(1..m)], to
321       itself onto k[..variables from [4]..] and [1] is the image of i
322  @end format
323  The ideal i is generated by [1] and [3] in k[x(1..m)], the map [5]
324  maps [3] to 0, hence induces an isomorphism
325  @format
326            k[x(1..m)]/i -> k[..variables from [4]..]/[1]
327  @end format
328NOTE:    Applying elimpart to interred(i) may result in more substitutions.
329         However, interred may be more expansive than elimpart for big ideals
330EXAMPLE: example elimpart; shows an example
331"
332{
333   def BAS = basering;
334   int n,e = nvars(BAS),1;
335   if ( size(#)==1 ) {  n=#[1]; }
336   if ( size(#)==2 ) {  n=#[1]; e=#[2];}
337//----------- interreduce linear part with proc elimlinearpart ----------------
338// lin = ideal i after interreduction with linear part
339// eva = eliminated (substituted) variables
340// sub = polynomials defining substitution
341// neva= not eliminated variables
342// phi = map describing substitution
343
344   list L = elimlinearpart(i,n);
345   ideal lin, eva, sub, neva, phi = L[1], L[2], L[3], L[4], L[5];
346   if ( e == 0 )
347   {
348       return(L);
349   }
350//-------- direct substitution of variables if possible and if e!=0 -----------
351// first find terms lin1 in lin of pure degree 1 in each poly of lin
352// k1 = pure degree 1 part, i.e. nonzero elts of lin1, renumbered
353// k2 = lin2 (=matrix(lin) - matrix(lin2)), renumbered
354// kin = matrix(k1)+matrix(k2) = those polys of lin which contained a pure
355// degree 1 part.
356/*
357Alte Version mit interred:
358// Then go to ring newBAS with ordering c,dp(n) and create a matrix with
359// size(k1) colums and 2 rows, such that if [f1,f2] is a column of M then f1+f2
360// is one of the polys of lin containing a pure degree 1 part and f1 is this
361// part interreduce this matrix (i.e. Gauss elimination on linear part, with
362// rest transformed accordingly).
363//Ist jetzt durch direkte Substitution gemacht (schneller!)
364         //Variante falls wieder interred angewendet werden soll:
365         //ideal k12 = k1,k2;
366         //matrix M = matrix(k12,2,kk);     //degree 1 part is now in row 1
367         //M = interred(M);
368         //### interred zu teuer, muss nicht sein. Wenn interred angewendet
369         //werden soll, vorher in Ring mit Ordnung (c,dp) wechseln!
370         //Abfrage:  if( ordstr(BAS) != "c,dp("+string(n)+")" )
371         //auf KEINEN Fall std (wird zu gross)
372         //l = ncols(M);
373         //k1 = M[1,1..l];
374         //k2 = M[2,1..l];
375Interred ist jetzt ganz weggelassen. Aber es gibt Beispiele wo interred polys
376mit Grad 1 Teilen produziert, die vorher nicht da waren (aus polys, die einen konstanten Term haben).
377z.B. i=xy2-xu4-x+y2,x2y2+z3+zy,y+z2+1,y+u2;, interred(i)=z2+y+1,y2-x,u2+y,x3-z
378-z ergibt ich auch i[2]-z*i[3] mit option(redThrough)
379statt interred kann man hier auch NF(i,i[3])+i[3] verwenden
380hier lifert elimpart(i) 2 Substitutionen (x,y) elimpart(interred(i))
381aber 3 (x,y,z)
382Da interred oder NF aber die Laenge der polys vergroessern kann, nicht gemacht
383*/
384   int ii, kk;
385   ideal k1, k2, lin2;
386   int l = size(lin);                   // lin=i after applying elimlinearpart
387   ideal lin1 = jet(lin,1)-jet(lin,0);  // part of pure degree 1
388   //Note: If i,i1,i2 are ideals, then i = i1 - i2 is equivalent to
389   //i = ideal(matrix(i1) - matrix(i2))
390
391   if (size(lin1) == 0 )
392   {
393       return(L);
394   }
395
396   //-------- check candidates for direct substitution of variables ----------
397   //since lin1 != 0 there are candidates for substituting variables
398
399   lin2 = lin - lin1;      //difference as matrix
400   // rest of lin, part of pure degree 1 substracted from each generator of lin
401
402   for( ii=1; ii<=l; ii++ )
403   {
404      if( lin1[ii] != 0 )
405      {
406         kk = kk+1;
407         k1[kk] = lin1[ii];  // part of pure degree 1, renumbered
408         k2[kk] = lin2[ii];  // rest of those polys which had a degree 1 part
409         lin2[ii] = 0;
410      }
411   }
412   //Now each !=0 generator of lin2 contains only constant terms or terms of
413   //degree >= 2, hence lin 2 can never be used for further substitutions
414   //We have: lin = ideal(matrix(k1)+matrix(k2)), lin2
415
416   ideal kin = matrix(k1)+matrix(k2);
417   //kin = polys of lin which contained a pure degree 1 part.
418   kin = simplify(kin,2);
419   l = size(kin);                      //l != 0 since lin1 != 0
420   poly p,kip,vip, cand;
421   int count=1;
422   while ( count != 0 )
423   {
424         count = 0;
425         for ( ii=1; ii<=n; ii++  )    //start direct substitution of var(ii)
426         {
427            for (kk=1; kk<=l; kk++ )
428            {
429               p = kin[kk]/var(ii);
430               if ( deg(p) == 0 )  //this means that kin[kk]= p*var(ii) + h,
431                                   //with p=const and h not depending on var(ii)
432               {
433                  //we look for the shortest candidate to substitute var(ii)
434                  if ( cand == 0 )
435                  {
436                     cand = kin[kk];  //candidate for substituting var(ii)
437                  }
438                  else
439                  {
440                     if ( size(kin[kk]) < size(cand) )
441                     {
442                        cand = kin[kk];
443                     }
444                  }
445                }
446            }
447            if ( cand != 0 )
448            {
449                  p = cand/var(ii);
450                  kip = cand/p;      //normalized poly of kin w.r.t var(ii)
451                  eva = eva+var(ii); //var(ii) added to list of elimin. vars
452                  neva[ii] = 0;
453                  sub = sub+kip;     //poly defining substituion
454                  //## gmg: gendert 08/2008, map durch subst ersetzt
455                  //(viel schneller)
456                  vip = var(ii) - kip;  //poly to be substituted
457                  lin = subst(lin, var(ii), vip);  //subst in rest
458                  lin = simplify(lin,2);
459                  kin = subst(kin, var(ii), vip);  //subst in pure dgree 1 part
460                  kin = simplify(kin,2);
461                  l = size(kin);
462                  count = 1;
463            }
464            cand=0;
465         }
466   }
467
468   lin = kin+lin;
469
470   for( ii=1; ii<=size(lin); ii++ )
471   {
472      lin[ii] = cleardenom(lin[ii]);
473   }
474
475   for( ii=1; ii<=n; ii++ )
476   {
477      for( kk=1; kk<=size(eva); kk++ )
478      {
479         if (phi[ii] == eva[kk] )
480         {  phi[ii] = eva[kk]-sub[kk]; break; }
481      }
482   }
483   map psi = BAS,phi;
484   ideal phi1 = maxideal(1);
485   for(ii=1; ii<=size(eva); ii++)
486   {
487      phi1=psi(phi1);
488   }
489   L = lin, eva, sub, neva, phi1;
490   return(L);
491}
492example
493{ "EXAMPLE:"; echo = 2;
494   ring s=0,(u,x,y,z),dp;
495   ideal i = xy2-xu4-x+y2,x2y2+z3+zy,y+z2+1,y+u2;
496   elimpart(i);
497
498   i = interred(i); i;
499   elimpart(i);
500
501   elimpart(i,2);
502}
503
504///////////////////////////////////////////////////////////////////////////////
505
506proc elimpartanyr (ideal i, list #)
507"USAGE:   elimpartanyr(i [,p,e] );  i=ideal, p=polynomial, e=integer@*
508         p: product of vars to be eliminated,@*
509         e =0: substitute from linear part of i (same as elimlinearpart)@*
510         e!=0: eliminate also by direct substitution@*
511         (default: p=product of all vars, e=1)
512RETURN:  list of 6 objects:
513  @format
514  [1]: (interreduced) ideal obtained by substituting from i those vars
515       appearing in p, which occur in the linear part of i (or which can
516       be expressed directly in the remaining variables, if e!=0)
517  [2]: ideal, variables which have been substituted
518  [3]: ideal, i-th element defines substitution of i-th var in [2]
519  [4]: ideal of variables of basering, substituted ones are set to 0
520  [5]: ideal, describing the map from the basering, say k[x(1..m)], to
521       itself onto k[..variables fom [4]..] and [1] is the image of i
522  [6]: int, # of vars considered for substitution (= # of factors of p)
523  @end format
524  The ideal i is generated by [1] and [3] in k[x(1..m)], the map [5]
525  maps [3] to 0, hence induces an isomorphism
526  @format
527            k[x(1..m)]/i -> k[..variables fom [4]..]/[1]
528  @end format
529NOTE:    the procedure uses @code{execute} to create a ring with ordering dp
530         and vars placed correctly and then applies @code{elimpart}.
531EXAMPLE: example elimpartanyr; shows an example
532"
533{
534   def P = basering;
535   int j,n,e = 0,0,1;
536   poly p = product(maxideal(1));
537   if ( size(#)==1 ) { p=#[1]; }
538   if ( size(#)==2 ) { p=#[1]; e=#[2]; }
539   string a,b;
540   for ( j=1; j<=nvars(P); j++ )
541   {
542      if (deg(p/var(j))>=0) { a = a+varstr(j)+","; n = n+1; }
543      else { b = b+varstr(j)+","; }
544   }
545   if ( size(b) != 0 ) { b = b[1,size(b)-1]; }
546   else { a = a[1,size(a)-1]; }
547   execute("ring gnir ="+charstr(P)+",("+a+b+"),dp;");
548   ideal i = imap(P,i);
549   list L = elimpart(i,n,e)+list(n);
550   setring P;
551   list L = imap(gnir,L);
552   return(L);
553}
554example
555{ "EXAMPLE:"; echo = 2;
556   ring s=0,(x,y,z),dp;
557   ideal i = x3+y2+z,x2y2+z3,y+z+1;
558   elimpartanyr(i,z);
559}
560///////////////////////////////////////////////////////////////////////////////
561
562proc fastelim (ideal i, poly p, list #)
563"USAGE:   fastelim(i,p[h,o,a,b,e,m]); i=ideal, p=polynomial; h,o,a,b,e=integers@*
564          p: product of variables to be eliminated;@*
565  Optional parameters:
566  @format
567  - h !=0: use Hilbert-series driven std-basis computation
568  - o !=0: use proc @code{valvars} for a - hopefully - optimal ordering of vars
569  - a !=0: order vars to be eliminated w.r.t. increasing complexity
570  - b !=0: order vars not to be eliminated w.r.t. increasing complexity
571  - e !=0: use @code{elimpart} first to eliminate easy part
572  - m !=0: compute a minimal system of generators
573  @end format
574  (default: h,o,a,b,e,m = 0,1,0,0,0,0)
575RETURN:  ideal obtained from i by eliminating those variables, which occur in p
576EXAMPLE: example fastelim; shows an example.
577"
578{
579   def P = basering;
580   int h,o,a,b,e,m = 0,1,0,0,0,0;
581   if ( size(#) == 1 ) { h=#[1]; }
582   if ( size(#) == 2 ) { h=#[1]; o=#[2]; }
583   if ( size(#) == 3 ) { h=#[1]; o=#[2]; a=#[3]; }
584   if ( size(#) == 4 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4];}
585   if ( size(#) == 5 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4]; e=#[5]; }
586   if ( size(#) == 6 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4]; e=#[5]; m=#[6]; }
587   list L = elimpartanyr(i,p,e);
588   poly q = product(L[2]);     //product of vars which are already eliminated
589   if ( q==0 ) { q=1; }
590   p = p/q;                    //product of vars which must still be eliminated
591   int nu = size(L[5])-size(L[2]);   //number of vars which must still be eliminated
592   if ( p==1 )                 //ready if no vars are left
593   {                           //compute minbase if 3-rd argument !=0
594      if ( m != 0 ) { L[1]=minbase(L[1]); }
595      return(L);
596   }
597//---------------- create new ring with remaining variables -------------------
598   string newvar = string(L[4]);
599   L = L[1],p;
600   execute("ring r1=("+charstr(P)+"),("+newvar+"),"+"dp;");
601   list L = imap(P,L);
602//------------------- find "best" ordering of variables  ----------------------
603   newvar = string(maxideal(1));
604   if ( o != 0 )
605   {
606      list ordevar = valvars(L[1],a,L[2],b);
607      intvec v = ordevar[1];
608      newvar=string(sort(maxideal(1),v)[1]);
609//------------ create new ring with "best" ordering of variables --------------
610      def r0=changevar(newvar);
611      setring r0;
612      list L = imap(r1,L);
613      kill r1;
614      def r1 = r0;
615      kill r0;
616   }
617//----------------- h==0: eliminate remaining vars directly -------------------
618   if ( h == 0 )
619   {
620      L[1] = eliminate(L[1],L[2]);
621      def r2 = r1;
622   }
623   else
624//------- h!=0: homogenize and compute Hilbert series using hilbvec ----------
625   {
626      intvec hi = hilbvec(L[1]);         // Hilbert series of i
627      execute("ring r2=("+charstr(P)+"),("+varstr(basering)+",@homo),dp;");
628      list L = imap(r1,L);
629      L[1] = homog(L[1],@homo);          // @homo = homogenizing var
630//---- use Hilbert-series to eliminate variables with Hilbert-driven std -----
631      L[1] = eliminate(L[1],L[2],hi);
632      L[1]=subst(L[1],@homo,1);          // dehomogenize by setting @homo=1
633   }
634   if ( m != 0 )                         // compute minbase
635   {
636      if ( #[1] != 0 ) { L[1] = minbase(L[1]); }
637   }
638   def id = L[1];
639   setring P;
640   return(imap(r2,id));
641}
642example
643{ "EXAMPLE:"; echo = 2;
644   ring s=31991,(e,f,x,y,z,t,u,v,w,a,b,c,d),dp;
645   ideal i = w2+f2-1, x2+t2+a2-1,  y2+u2+b2-1, z2+v2+c2-1,
646            d2+e2-1, f4+2u, wa+tf, xy+tu+ab;
647   fastelim(i,xytua,1,1);       //with hilb,valvars
648   fastelim(i,xytua,1,0,1);     //with hilb,minbase
649}
650///////////////////////////////////////////////////////////////////////////////
651
652proc faststd (@id, list #)
653"USAGE:   faststd(id [,\"hilb\",\"sort\",\"dec\",o,\"blocks\"]);
654         id=ideal/module, o=string (allowed:\"lp\",\"dp\",\"Dp\",\"ls\",
655         \"ds\",\"Ds\"),  \"hilb\",\"sort\",\"dec\",\"block\" options for
656         Hilbert-driven std, and the procedure sortandmap
657RETURN:  a ring R, in which an ideal STD_id is stored: @*
658         - the ring R differs from the active basering only in the choice
659         of monomial ordering and in the sorting of the variables.
660         - STD_id is a standard basis for the image (under imap) of the input
661         ideal/module id with respect to the new monomial ordering. @*
662NOTE:    Using the optional input parameters, we may modify the computations
663         performed: @*
664         - \"hilb\"  : use Hilbert-driven standard basis computation@*
665         - \"sort\"  : use 'sortandmap' for a best sorting of the variables@*
666         - \"dec\"   : order vars w.r.t. decreasing complexity (with \"sort\")@*
667         - \"block\" : create block ordering, each block having ordstr=o, s.t.
668                     vars of same complexity are in one block (with \"sort\")@*
669         - o       : defines the basic ordering of the resulting ring@*
670         [default: o=ordering of 1st block of basering (if allowed, else o=\"dp\"],
671                  \"sort\", if none of the optional parameters is given @*
672         This procedure is only useful for hard problems where other methods fail.@*
673         \"hilb\" is useful for hard orderings (as \"lp\") or for characteristic 0,@*
674         it is correct for \"lp\",\"dp\",\"Dp\" (and for block orderings combining
675         these) but not for s-orderings or if the vars have different weights.@*
676         There seem to be only few cases in which \"dec\" is fast.
678EXAMPLE: example faststd; shows an example.
679"
680{
681   def @P = basering;
682   int @h,@s,@n,@m,@ii = 0,0,0,0,0;
683   string @o,@va,@c = ordstr(basering),"","";
684//-------------------- prepare ordering and set options -----------------------
685   if ( @o[1]=="c" or @o[1]=="C")
686      {  @o = @o[3,2]; }
687   else
688      { @o = @o[1,2]; }
689   if( @o[1]!="d" and @o[1]!="D" and @o[1]!="l")
690      { @o="dp"; }
691
692   if (size(#) == 0 )
693      { @s = 1; }
694   for ( @ii=1; @ii<=size(#); @ii++ )
695   {
696      if ( typeof(#[@ii]) != "string" )
697      {
698         "// wrong syntax! type: help faststd";
699         return();
700      }
701      else
702      {
703         if ( #[@ii] == "hilb"  ) { @h = 1; }
704         if ( #[@ii] == "dec"   ) { @n = 1; }
705         if ( #[@ii] == "block" ) { @m = 1; }
706         if ( #[@ii] == "sort"  ) { @s = 1; }
707         if ( #[@ii]=="lp" or #[@ii]=="dp" or #[@ii]=="Dp" or #[@ii]=="ls"
708              or #[@ii]=="ds" or #[@ii]=="Ds" ) { @o = #[@ii]; }
709      }
710   }
711   if( voice==2 ) { "// chosen options, hilb sort dec block:",@h,@s,@n,@m; }
712
713//-------------------- nosort: create ring with new name ----------------------
714   if ( @s==0 )
715   {
716      execute("ring @S1 =("+charstr(@P)+"),("+varstr(@P)+"),("+@o+");");
717      def STD_id = imap(@P,@id);
718      if ( @h==0 ) { STD_id = std(STD_id); }
719   }
720
721//---------------------- no hilb: compute SB directly -------------------------
722   if ( @s != 0 and @h == 0 )
723   {
724      intvec getoption = option(get);
725      option(redSB);
726      @id = interred(sort(@id)[1]);
727      poly @p = product(maxideal(1),1..nvars(@P));
728      def @S1=sortandmap(@id,@n,@p,0,@o,@m);
729      setring @S1;
730      option(set,getoption);
731      def STD_id=imap(@S1,IMAG);
732      STD_id = std(STD_id);
733   }
734//------- hilb: homogenize and compute Hilbert-series using hilbvec -----------
735// this uses another standardbasis computation
736   if ( @h != 0 )
737   {
738      execute("ring @Q=("+charstr(@P)+"),("+varstr(@P)+",@homo),("+@o+");");
739      def @id = imap(@P,@id);
740      @id = homog(@id,@homo);               // @homo = homogenizing var
741      if ( @s != 0 )
742      {
743        intvec getoption = option(get);
744        option(redSB);
745        @id = interred(sort(@id)[1]);
746        poly @p = product(maxideal(1),1..(nvars(@Q)-1));
747        def @S1=sortandmap(@id,@n,@p,0,@o,@m);
748        setring @S1;
749        option(set,getoption);
750        kill @Q;
751        def @Q= basering;
752        def @id = IMAG;
753      }
754      intvec @hi;                     // encoding of Hilbert-series of i
755      @hi = hilbvec(@id);
756      //if ( @s!=0 ) { @hi = hilbvec(@id,"32003",ordstr(@Q)); }
757      //else { @hi = hilbvec(@id); }
758//-------------------------- use Hilbert-driven std --------------------------
759      @id = std(@id,@hi);
760      @id = subst(@id,@homo,1);             // dehomogenize by setting @homo=1
761      @va = varstr(@Q)[1,size(varstr(@Q))-6];
762      if ( @s!=0 )
763      {
764         @o = ordstr(@Q);
765         if ( @o[1]=="c" or @o[1]=="C") { @o = @o[1,size(@o)-6]; }
766         else { @o = @o[1,size(@o)-8] + @o[size(@o)-1,2]; }
767      }
768      kill @S1;
769      execute("ring @S1=("+charstr(@Q)+"),("+@va+"),("+@o+");");
770      def STD_id = imap(@Q,@id);
771   }
772   attrib(STD_id,"isSB",1);
773   export STD_id;
774   if (defined(IMAG)) { kill IMAG; }
775   setring @P;
776   dbprint(printlevel-voice+3,"
777// 'faststd' created a ring, in which an object STD_id is stored.
778// To access the object, type (if the name R was assigned to the return value):
779        setring R; STD_id; ");
780   return(@S1);
781}
782example
783{ "EXAMPLE:"; echo = 2;
784   system("--ticks-per-sec",100); // show time in 1/100 sec
785   ring s = 0,(e,f,x,y,z,t,u,v,w,a,b,c,d),(c,lp);
786   ideal i = w2+f2-1, x2+t2+a2-1,  y2+u2+b2-1, z2+v2+c2-1,
787            d2+e2-1, f4+2u, wa+tf, xy+tu+ab;
788   option(prot); timer=1;
789   int time = timer;
790   ideal j=std(i);
791   timer-time;
792   dim(j),mult(j);
793
794   time = timer;
795   def R=faststd(i);                      // use "best" ordering of vars
796   timer-time;
797   show(R);setring R;dim(STD_id),mult(STD_id);
798
799   setring s;kill R;time = timer;
800   def R=faststd(i,"hilb");                // hilb-std only
801   timer-time;
802   show(R);setring R;dim(STD_id),mult(STD_id);
803
804   setring s;kill R;time = timer;
805   def R=faststd(i,"hilb","sort");         // hilb-std,"best" ordering
806   timer-time;
807   show(R);setring R;dim(STD_id),mult(STD_id);
808
809   setring s;kill R;time = timer;
810   def R=faststd(i,"hilb","sort","block","dec"); // hilb-std,"best",blocks
811   timer-time;
812   show(R);setring R;dim(STD_id),mult(STD_id);
813
814   setring s;kill R;time = timer;
815   timer-time;time = timer;
816   def R=faststd(i,"sort","block","Dp"); //"best",decreasing,Dp-blocks
817   timer-time;
818   show(R);setring R;dim(STD_id),mult(STD_id);
819}
820///////////////////////////////////////////////////////////////////////////////
821
822proc findvars(id, list #)
823"USAGE:   findvars(id [,any] ); id=poly/ideal/vector/module/matrix, any=any type
824RETURN:  if no second argument is present: ideal of variables occuring in id,@*
825         if a second argument is given (of any type): list L with 4 entries:
826  @format
827  L[1]: ideal of variables occuring in id
828  L[2]: intvec of variables occuring in id
829  L[3]: ideal of variables not occuring in id
830  L[4]: intvec of variables not occuring in id
831  @end format
832EXAMPLE: example findvars; shows an example
833"
834{
835   int ii,n;
836   ideal found, notfound;
837   intvec f,nf;
838   n = nvars(basering);
839   ideal i = simplify(ideal(matrix(id)),10);
840   matrix M[ncols(i)][1] = i;
841   vector v = module(M)[1];
842   ideal max = maxideal(1);
843
844   for (ii=1; ii<=n; ii++)
845   {
846      if ( v != subst(v,var(ii),0) )
847      {
848         found = found+var(ii);
849         f = f,ii;
850      }
851      else
852      {
853         notfound = notfound+var(ii);
854         nf = nf,ii;
855      }
856   }
857   if ( size(f)>1 ) { f = f[2..size(f)]; }      //intvec of found vars
858   if ( size(nf)>1 ) { nf = nf[2..size(nf)]; }  //intvec of vars not found
859   if( size(#)==0 )  { return(found); }
860   if( size(#)!=0 )  { list L = found,f,notfound,nf; return(L); }
861}
862example
863{ "EXAMPLE:"; echo = 2;
864   ring s  = 0,(e,f,x,y,t,u,v,w,a,d),dp;
865   ideal i = w2+f2-1, x2+t2+a2-1;
866   findvars(i);
867   findvars(i,1);
868}
869///////////////////////////////////////////////////////////////////////////////
870
871proc hilbvec (@id, list #)
872"USAGE:   hilbvec(id[,c,o]); id=poly/ideal/vector/module/matrix, c,o=strings,@*
873          c=char, o=ordering used by @code{hilb} (default: c=\"32003\", o=\"dp\")
874RETURN:  intvec of 1st Hilbert-series of id, computed in char c and ordering o
875NOTE:    id must be homogeneous (i.e. all vars have weight 1)
876EXAMPLE: example hilbvec; shows an example
877"
878{
879   def @P = basering;
880   string @c,@o = "32003", "dp";
881   if ( size(#) == 1 ) {  @c = #[1]; }
882   if ( size(#) == 2 ) {  @c = #[1]; @o = #[2]; }
883   string @si = typeof(@id)+" @i = "+string(@id)+";";  //** weg
884   execute("ring @r=("+@c+"),("+varstr(basering)+"),("+@o+");");
885   //**def i = imap(P,@id);
886   execute(@si);                   //** weg
887   //show(basering);
888   @i = std(@i);
889   intvec @hi = hilb(@i,1);         // intvec of 1-st Hilbert-series of id
890   return(@hi);
891}
892example
893{ "EXAMPLE:"; echo = 2;
894   ring s   = 0,(e,f,x,y,z,t,u,v,w,a,b,c,d,H),dp;
895   ideal id = w2+f2-1, x2+t2+a2-1,  y2+u2+b2-1, z2+v2+c2-1,
896              d2+e2-1, f4+2u, wa+tf, xy+tu+ab;
897   id = homog(id,H);
898   hilbvec(id);
899}
900///////////////////////////////////////////////////////////////////////////////
901
902proc tolessvars (id ,list #)
903"USAGE:   tolessvars(id [,s1,s2] ); id poly/ideal/vector/module/matrix,
904          s1=string (new ordering)@*
905          [default: s1=\"dp\" or \"ds\" depending on whether the first block
906          of the old ordering is a p- or an s-ordering, respectively]
907RETURN:  If id contains all vars of the basering: empty list. @*
908         Else: ring R with the same char as the basering, but possibly less
909         variables (only those variables which actually occur in id). In R
910         an object IMAG (image of id under imap) is stored.
911DISPLAY: If printlevel >=0, display ideal of vars, which have been omitted
912         from the old ring.
913EXAMPLE: example tolessvars; shows an example
914"
915{
916//---------------- initialisation and check occurence of vars -----------------
917   int s,ii,n,fp,fs;
918   string s2,newvar;
919   int pr = printlevel-voice+3;  // p = printlevel+1 (default: p=1)
920   def P = basering;
921   s2 = ordstr(P);
922
923   list L = findvars(id,1);
924   newvar = string(L[1]);    // string of new variables
925   n = size(L[1]);           // number of new variables
926   if( n == 0 )
927   {
928      dbprint( pr,"","// no variable occured in "+typeof(id)+", no change of ring!");
929      return(id);
930   }
931   if( n == nvars(P) )
932   {
933     dbprint(printlevel-voice+3,"
934// All variables appear in input object.
935// empty list returned. ");
936     return(list());
937   }
938//----------------- prepare new ring, map to it and return --------------------
939   if ( size(#) == 0 )
940   {
941       fp = find(s2,"p");
942       fs = find(s2,"s");
943       if( fs==0 or (fs>=fp && fp!=0) ) { s2="dp"; }
944       else {  s2="ds"; }
945   }
946   if ( size(#) ==1 ) { s2=#[1]; }
947   dbprint( pr,"","// variables which did not occur:",L[3] );
948   execute("ring S1=("+charstr(P)+"),("+newvar+"),("+s2+");");
949   def IMAG = imap(P,id);
950   export IMAG;
951   dbprint(printlevel-voice+3,"
952// 'tolessvars' created a ring, in which an object IMAG is stored.
953// To access the object, type (if the name R was assigned to the return value):
954        setring R; IMAG; ");
955   return(S1);
956}
957example
958{ "EXAMPLE:"; echo = 2;
959   ring r  = 0,(x,y,z),dp;
960   ideal i = y2-x3,x-3,y-2x;
961   def R_r = tolessvars(i,"lp");
962   setring R_r;
963   show(basering);
964   IMAG;
965   kill R_r;
966}
967///////////////////////////////////////////////////////////////////////////////
968
969proc solvelinearpart (id,list #)
970"USAGE:   solvelinearpart(id [,n] );  id=ideal/module, n=integer (default: n=0)
971RETURN:  (interreduced) generators of id of degree <=1 in reduced triangular
972         form if n=0 [non-reduced triangular form if n!=0]
973ASSUME:  monomial ordering is a global ordering (p-ordering)
974NOTE:    may be used to solve a system of linear equations,
975         see @code{gauss_row} from 'matrix.lib' for a different method
976WARNING: the result is very likely to be false for 'real' coefficients, use
978EXAMPLE: example solvelinearpart; shows an example
979"
980{
981   intvec getoption = option(get);
982   option(redSB);
983   if ( size(#)!=0 )
984   {
985      if(#[1]!=0) { option(noredSB); }
986   }
987   def lin = interred(degreepart(id,0,1)[1]);
988   if ( size(#)!=0 )
989   {
990      if(#[1]!=0)
991      {
992         return(lin);
993      }
994   }
995   option(set,getoption);
996   return(simplify(lin,1));
997}
998example
999{ "EXAMPLE:"; echo = 2;
1000   // Solve the system of linear equations:
1001   //         3x +   y +  z -  u = 2
1002   //         3x +  8y + 6z - 7u = 1
1003   //        14x + 10y + 6z - 7u = 0
1004   //         7x +  4y + 3z - 3u = 3
1005   ring r = 0,(x,y,z,u),lp;
1006   ideal i= 3x +   y +  z -  u,
1007           13x +  8y + 6z - 7u,
1008           14x + 10y + 6z - 7u,
1009            7x +  4y + 3z - 3u;
1010   ideal j= 2,1,0,3;
1011   j = i-j;                        // difference of 1x4 matrices
1012                                   // compute reduced triangular form, setting
1013   solvelinearpart(j);             // the RHS equal 0 gives the solutions!
1014   solvelinearpart(j,1); "";       // triangular form, not reduced
1015}
1016///////////////////////////////////////////////////////////////////////////////
1017
1018proc sortandmap (@id, list #)
1019"USAGE:   sortandmap(id [,n1,p1,n2,p2...,o1,m1,o2,m2...]);@*
1020         id=poly/ideal/vector/module,@*
1021         p1,p2,...= polynomials (product of variables),@*
1022         n1,n2,...= integers,@*
1023         o1,o2,...= strings,@*
1024         m1,m2,...= integers@*
1025         (default: p1=product of all vars, n1=0, o1=\"dp\",m1=0)
1026         the last pi (containing the remaining vars) may be omitted
1027RETURN:  a ring R, in which a poly/ideal/vector/module IMAG is stored: @*
1028         - the ring R differs from the active basering only in the choice
1029         of monomial ordering and in the sorting of the variables.@*
1030         - IMAG is the image (under imap) of the input ideal/module id @*
1031         The new monomial ordering and sorting of vars is as follows:
1032  @format
1033  - each block of vars occuring in pi is sorted w.r.t. its complexity in id,
1034  - ni controls the sorting in i-th block (= vars occuring in pi):
1035    ni=0 (resp. ni!=0) means that least complex (resp. most complex) vars come
1036    first
1037  - oi and mi define the monomial ordering of the i-th block:
1038    if mi =0, oi=ordstr(i-th block)
1039    if mi!=0, the ordering of the i-th block itself is a blockordering,
1040      each subblock having ordstr=oi, such that vars of same complexity are
1041      in one block
1042  @end format
1043         Note that only simple ordstrings oi are allowed: \"lp\",\"dp\",\"Dp\",
1044         \"ls\",\"ds\",\"Ds\". @*
1045NOTE:    We define a variable x to be more complex than y (with respect to id)
1046         if val(x) > val(y) lexicographically, where val(x) denotes the
1047         valuation vector of x:@*
1048         consider id as list of polynomials in x with coefficients in the
1049         remaining variables. Then:@*
1050         val(x) = (maximal occuring power of x,  # of all monomials in leading
1051         coefficient, # of all monomials in coefficient of next smaller power
1052         of x,...).
1053EXAMPLE: example sortandmap; shows an example
1054"
1055{
1056   def @P = basering;
1057   int @ii,@jj;
1058   intvec @v;
1059   string @o;
1060//----------------- find o in # and split # into 2 lists ---------------------
1061   # = # +list("dp",0);
1062   for ( @ii=1; @ii<=size(#); @ii++)
1063   {
1064      if ( typeof(#[@ii])=="string" )  break;
1065   }
1066   if ( @ii==1 ) { list @L1 = list(); }
1067   else { list @L1 = #[1..@ii-1]; }
1068   list @L2 = #[@ii..size(#)];
1069   list @L = sortvars(@id,@L1);
1070   string @va = string(@L[1]);
1071   list @l = @L[2];   //e.g. @l[4]=intvec describing permutation of 1-st block
1072//----------------- construct correct ordering with oi and mi ----------------
1073   for ( @ii=4; @ii<=size(@l); @ii=@ii+4 )
1074   {
1075      @L2=@L2+list("dp",0);
1076      if ( @L2[@ii/2] != 0)
1077      {
1078         @v = @l[@ii];
1079         for ( @jj=1; @jj<=size(@v); @jj++ )
1080         {
1081           @o = @o+@L2[@ii/2 -1]+"("+string(@v[@jj])+"),";
1082         }
1083      }
1084      else
1085      {
1086         @o = @o+@L2[@ii/2 -1]+"("+string(size(@l[@ii/2]))+"),";
1087      }
1088   }
1089   @o=@o[1..size(@o)-1];
1090   execute("ring @S1 =("+charstr(@P)+"),("+@va+"),("+@o+");");
1091   def IMAG = imap(@P,@id);
1092   export IMAG;
1093   dbprint(printlevel-voice+3,"
1094// 'sortandmap' created a ring, in which an object IMAG is stored.
1095// To access the object, type (if the name R was assigned to the return value):
1096        setring R; IMAG; ");
1097   return(@S1);
1098}
1099example
1100{ "EXAMPLE:"; echo = 2;
1101   ring s = 32003,(x,y,z),dp;
1102   ideal i=x3+y2,xz+z2;
1103   def R_r=sortandmap(i);
1104   show(R_r);
1105   setring R_r; IMAG;
1106   kill R_r; setring s;
1107   def R_r=sortandmap(i,1,xy,0,z,0,"ds",0,"lp",0);
1108   show(R_r);
1109   setring R_r; IMAG;
1110   kill R_r;
1111}
1112///////////////////////////////////////////////////////////////////////////////
1113
1114proc sortvars (id, list #)
1115"USAGE:   sortvars(id[,n1,p1,n2,p2,...]);@*
1116         id=poly/ideal/vector/module,@*
1117         p1,p2,...= polynomials (product of vars),@*
1118         n1,n2,...= integers@*
1119         (default: p1=product of all vars, n1=0)
1120         the last pi (containing the remaining vars) may be omitted
1121COMPUTE: sort variables with respect to their complexity in id
1122RETURN:  list of two elements, an ideal and a list:
1123  @format
1124  [1]: ideal, variables of basering sorted w.r.t their complexity in id
1125       ni controls the ordering in i-th block (= vars occuring in pi):
1126       ni=0 (resp. ni!=0) means that less (resp. more) complex vars come first
1127  [2]: a list with 4 entries for each pi:
1128       _[1]: ideal ai : vars of pi in correct order,
1129       _[2]: intvec vi: permutation vector describing the ordering in ai,
1130       _[3]: intmat Mi: valuation matrix of ai, the columns of Mi being the
1131                  valuation vectors of the vars in ai
1132       _[4]: intvec wi: size of 1-st, 2-nd,... block of identical columns of Mi
1133                  (vars with same valuation)
1134  @end format
1135NOTE:    We define a variable x to be more complex than y (with respect to id)
1136         if val(x) > val(y) lexicographically, where val(x) denotes the
1137         valuation vector of x:@*
1138         consider id as list of polynomials in x with coefficients in the
1139         remaining variables. Then:@*
1140         val(x) = (maximal occuring power of x,  # of all monomials in leading
1141         coefficient, # of all monomials in coefficient of next smaller power
1142         of x,...).
1143EXAMPLE: example sortvars; shows an example
1144"
1145{
1146   int ii,jj,n,s;
1147   list L = valvars(id,#);
1148   list L2, L3 = L[2], L[3];
1149   list K; intmat M; intvec v1,v2,w;
1150   ideal i = sort(maxideal(1),L[1])[1];
1151   for ( ii=1; ii<=size(L2); ii++ )
1152   {
1153      M = transpose(L3[2*ii]);
1154      M = M[L2[ii],1..nrows(L3[2*ii])];
1155      w = 0; s = 0;
1156      for ( jj=1; jj<=nrows(M)-1; jj++ )
1157      {
1158         v1 = M[jj,1..ncols(M)];
1159         v2 = M[jj+1,1..ncols(M)];
1160         if ( v1 != v2 ) { n=jj-s; s=s+n; w = w,n; }
1161      }
1162      w=w,nrows(M)-s; w=w[2..size(w)];
1163      K = K+sort(L3[2*ii-1],L2[ii])+list(transpose(M))+list(w);
1164   }
1165   L = i,K;
1166   return(L);
1167}
1168example
1169{ "EXAMPLE:"; echo = 2;
1170   ring s=0,(x,y,z,w),dp;
1171   ideal i = x3+y2+yw2,xz+z2,xyz-w2;
1172   sortvars(i,0,xy,1,zw);
1173}
1174///////////////////////////////////////////////////////////////////////////////
1175
1176proc valvars (id, list #)
1177"USAGE:   valvars(id[,n1,p1,n2,p2,...]);@*
1178         id=poly/ideal/vector/module,@*
1179         p1,p2,...= polynomials (product of vars),@*
1180         n1,n2,...= integers,
1181
1182         ni controls the ordering of vars occuring in pi: ni=0 (resp. ni!=0)
1183         means that less (resp. more) complex vars come first (default: p1=product of all vars, n1=0),@*
1184         the last pi (containing the remaining vars) may be omitted
1185COMPUTE: valuation (complexity) of variables with respect to id.@*
1186         ni controls the ordering of vars occuring in pi:@*
1187         ni=0 (resp. ni!=0) means that less (resp. more) complex vars come first.
1188RETURN:  list with 3 entries:
1189  @format
1190  [1]: intvec, say v, describing the permutation such that the permuted
1191       ring variables are ordered with respect to their complexity in id
1192  [2]: list of intvecs, i-th intvec, say v(i) describing permutation
1193       of vars in a(i) such that v=v(1),v(2),...
1194  [3]: list of ideals and intmat's, say a(i) and M(i), where
1195       a(i): factors of pi,
1196       M(i): valuation matrix of a(i), such that the j-th column of M(i)
1197             is the valuation vector of j-th generator of a(i)
1198         @end format
1199NOTE:    Use @code{sortvars} in order to actually sort the variables!
1200         We define a variable x to be more complex than y (with respect to id)
1201         if val(x) > val(y) lexicographically, where val(x) denotes the
1202         valuation vector of x:@*
1203         consider id as list of polynomials in x with coefficients in the
1204         remaining variables. Then:@*
1205         val(x) = (maximal occuring power of x,  # of all monomials in leading
1206         coefficient, # of all monomials in coefficient of next smaller power
1207         of x,...).
1208EXAMPLE: example valvars; shows an example
1209"
1210{
1211//---------------------------- initialization ---------------------------------
1212   int ii,jj,kk,n;
1213   list L;                    // list of valuation vectors in one block
1214   intvec vec;                // describes permutation of vars (in one block)
1215   list blockvec;             // i-th element = vec of i-th block
1216   intvec varvec;             // result intvector
1217   list Li;                   // result list of ideals
1218   list LM;                   // result list of intmat's
1219   intvec v,w,s;              // w valuation vector for one variable
1220   matrix C;                  // coefficient matrix for different variables
1221   ideal i = simplify(ideal(matrix(id)),10);
1222
1223//---- for each pii in # create ideal a(ii) intvec v(ii) and list L(ii) -------
1224// a(ii) = ideal of vars in product, v(ii)[j]=k <=> a(ii)[j]=var(k)
1225
1226   v = 1..nvars(basering);
1227   int l = size(#);
1228   if ( l >= 2 )
1229   {
1230      ideal m=maxideal(1);
1231      for ( ii=2; ii<=l; ii=ii+2 )
1232      {
1233         int n(ii) = #[ii-1];
1234         ideal a(ii);
1235         intvec v(ii);
1236         for ( jj=1; jj<=nvars(basering); jj++ )
1237         {
1238            if ( #[ii]/var(jj) != 0)
1239            {
1240               a(ii) = a(ii) + var(jj);
1241               v(ii)=v(ii),jj;
1242               m[jj]=0;
1243               v[jj]=0;
1244            }
1245         }
1246         v(ii)=v(ii)[2..size(v(ii))];
1247      }
1248      if ( size(m)!=0 )
1249      {
1250         l = 2*(l/2)+2;
1251         ideal a(l) = simplify(m,2);
1252         intvec v(l) = compress(v);
1253         int n(l);
1254         if ( size(#)==l-1 ) { n(l) = #[l-1]; }
1255      }
1256   }
1257   else
1258   {
1259      l = 2;
1260      ideal a(2) = maxideal(1);
1261      intvec v(2) = v;
1262      int n(2);
1263      if ( size(#)==1 ) { n(2) = #[1]; }
1264   }
1265//------------- start loop to order variables in each a(ii) -------------------
1266
1267   for ( kk=2; kk<=l; kk=kk+2 )
1268   {
1269      L = list();
1270      n = 0;
1271//---------------- get valuation of all variables in a(kk) --------------------
1272      for ( ii=1; ii<=size(a(kk)); ii++ )
1273      {
1274         C = coeffs(i,a(kk)[ii]);
1275         w = nrows(C); // =(maximal occuring power of a(kk)[ii])+1
1276         for ( jj=w[1]; jj>1; jj-- )
1277         {
1278            s = size(C[jj,1..ncols(C)]);
1279            w[w[1]-jj+2] = sum(s);
1280         }
1281         // w[1] should represent the maximal occuring power of a(kk)[ii] so it
1282         // has to be decreased by 1 since otherwise the constant term is also
1283         // counted
1284         w[1]=w[1]-1;
1285
1286         L[ii]=w;
1287         n = size(w)*(size(w) > n) + n*(size(w) <= n);
1288      }
1289      intmat M(kk)[size(a(kk))][n];
1290      for ( ii=1; ii<=size(a(kk)); ii++ )
1291      {
1292         if ( n==1 ) { w = L[ii]; M(kk)[ii,1] = w[1]; }
1293         else  { M(kk)[ii,1..n] = L[ii]; }
1294      }
1295      LM[kk-1] = a(kk);
1296      LM[kk] = transpose(compress(M(kk)));
1297//------------------- compare valuation and insert in vec ---------------------
1298      vec = sort(L)[2];
1299      if ( n(kk) != 0 ) { vec = vec[size(vec)..1]; }
1300      blockvec[kk/2] = vec;
1301      vec = sort(v(kk),vec)[1];
1302      varvec = varvec,vec;
1303   }
1304   varvec = varvec[2..size(varvec)];
1305   list result = varvec,blockvec,LM;
1306   return(result);
1307}
1308example
1309{ "EXAMPLE:"; echo = 2;
1310   ring s=0,(x,y,z,a,b),dp;
1311   ideal i=ax2+ay3-b2x,abz+by2;
1312   valvars (i,0,xyz);
1313}
1314///////////////////////////////////////////////////////////////////////////////
1315proc idealSplit(ideal I,list #)
1316"USAGE:  idealSplit(id,timeF,timeS);  id ideal and optional
1317         timeF, timeS integers to bound the time which can be used
1318         for factorization resp. standard basis computation
1319RETURN:  a list of ideals such that their intersection
1320         has the same radical as id
1321EXAMPLE: example idealSplit; shows an example
1322"
1323{
1324   option(redSB);
1325   int j,k,e;
1326   int i=1;
1327   int l=attrib(I,"isSB");
1328   ideal J;
1329   int timeF;
1330   int timeS;
1331   list re,fac,te;
1332
1333   if(size(#)==1)
1334   {
1335     if(typeof(#[1])=="ideal")
1336     {
1337        re=#;
1338     }
1339     else
1340     {
1341       timeF=#[1];
1342     }
1343   }
1344   if(size(#)==2)
1345   {
1346     if(typeof(#[1])=="list")
1347     {
1348        re=#[1];
1349        timeF=#[2];
1350     }
1351     else
1352     {
1353       timeF=#[1];
1354       timeS=#[2];
1355     }
1356   }
1357   if(size(#)==3){re=#[1];timeF=#[2];timeS=#[3];}
1358
1359   fac=timeFactorize(I[1],timeF);
1360
1361   while((size(fac[1])==2)&&(i<size(I)))
1362   {
1363      i++;
1364      fac=timeFactorize(I[i],timeF);
1365   }
1366   if(size(fac[1])>2)
1367   {
1368      for(j=2;j<=size(fac[1]);j++)
1369      {
1370         I[i]=fac[1][j];
1371         attrib(I,"isSB",1);
1372         e=1;
1373         k=0;
1374         while(k<size(re))
1375         {
1376            k++;
1377            if(size(reduce(re[k],I))==0){e=0;break;}
1378            attrib(re[k],"isSB",1);
1379            if(size(reduce(I,re[k]))==0){re=delete(re,k);k--;}
1380         }
1381         if(e)
1382         {
1383            if(l)
1384            {
1385               J=I;
1386               J[i]=0;
1387               J=simplify(J,2);
1388               attrib(J,"isSB",1);
1389               re=idealSplit(std(J,fac[1][j]),re,timeF,timeS);
1390            }
1391            else
1392            {
1393               re=idealSplit(timeStd(I,timeS),re,timeF,timeS);
1394            }
1395         }
1396      }
1397      return(re);
1398   }
1399   J=timeStd(I,timeS);
1400   attrib(I,"isSB",1);
1401   if(size(reduce(J,I))==0){return(re+list(I));}
1402   return(re+idealSplit(J,re,timeF,timeS));
1403}
1404example
1405{ "EXAMPLE:"; echo = 2;
1406   ring r=32003,(b,s,t,u,v,w,x,y,z),dp;
1407   ideal i=
1408   bv+su,
1409   bw+tu,
1410   sw+tv,
1411   by+sx,
1412   bz+tx,
1413   sz+ty,
1414   uy+vx,
1415   uz+wx,
1416   vz+wy,
1417   bvz;
1418   idealSplit(i);
1419}
1420///////////////////////////////////////////////////////////////////////////////
1421proc idealSimplify(ideal J,list #)
1422"USAGE:  idealSimplify(id);  id ideal
1423RETURN:  ideal I = eliminate(Id,m) m is a product of variables
1424         which are only linearly involved in the generators of id
1425EXAMPLE: example idealSimplify; shows an example
1426"
1427{
1428   ideal I=J;
1429   if(size(#)!=0){I=#[1];}
1430   def R=basering;
1431   matrix M=jacob(I);
1432   ideal ma=maxideal(1);
1433   int i,j,k;
1434   map phi;
1435
1436   for(i=1;i<=nrows(M);i++)
1437   {
1438      for(j=1;j<=ncols(M);j++)
1439      {
1440         if(deg(M[i,j])==0)
1441         {
1442            ma[j]=(-1/M[i,j])*(I[i]-M[i,j]*var(j));
1443            phi=R,ma;
1444            I=phi(I);
1445            J=phi(J);
1446            for(k=1;k<=ncols(I);k++){I[k]=cleardenom(I[k]);}
1447            M=jacob(I);
1448         }
1449      }
1450   }
1451   J=simplify(J,2);
1452   for(i=1;i<=size(J);i++){J[i]=cleardenom(J[i]);}
1453   return(J);
1454}
1455example
1456{ "EXAMPLE:"; echo = 2;
1457   ring r=0,(x,y,z,w,t),dp;
1458   ideal i=
1459   t,
1460   x3+y2+2z,
1461   x2+3y,
1462   x2+y2+z2,
1463   w2+z;
1464   ideal j=idealSimplify(i);
1465   ideal k=eliminate(i,zyt);
1466   reduce(k,std(j));
1467   reduce(j,std(k));
1468}
1469
1470///////////////////////////////////////////////////////////////////////////////
1471
1472/*
1473
1474 ring s=31991,(e,f,x,y,z,t,u,v,w,a,b,c,d),dp;
1475 ring s=31991,(x,y,z,t,u,v,w,a,b,c,d,f,e,h),dp; //standard
1476 ring s1=31991,(y,u,b,c,a,z,t,x,v,d,w,e,f,h),dp; //gut
1477v;
147813,12,11,10,8,7,6,5,4,3,2,1,9,14
1479print(matrix(sort(maxideal(1),v)));
1480f,e,w,d,x,t,z,a,c,b,u,y,v,h
1481print(matrix(maxideal(1)));
1482y,u,b,c,a,z,t,x,v,d,w,e,f,h
1483v0;
148414,9,12,11,10,8,7,6,5,4,3,2,1,13
1485print(matrix(sort(maxideal(1),v0)));
1486h,v,e,w,d,x,t,z,a,c,b,u,y,f
1487v1;v2;
14889,12,11,10,8,7,6,5,4,3,2,1,13,14
148913,12,11,10,8,7,6,5,4,3,2,1,9,14
1490
1491Ev. Gute Ordnung fuer i:
1492========================
1494mit ar=(ar1,...,ark), k=size(i)
1495    arj in K[..x^..]
1496d=deg_x(i) := max{deg_x(i[k]) | k=1..size(i)}
1498x>y  <==
1499  1. deg_x(i)>deg_y(i)
1500  2. "=" in 1. und size_x lexikographisch
1501
1502hier im Beispiel:
1503f: 5,1,0,1,2
1504
1505u: 3,1,4
1506
1507y: 3,1,3
1508b: 3,1,3
1509c: 3,1,3
1510a: 3,1,3
1511z: 3,1,3
1512t: 3,1,3
1513
1514x: 3,1,2
1515v: 3,1,2
1516d: 3,1,2
1517w: 3,1,2
1518e: 3,1,2
1519probier mal:
1520 ring s=31991,(f,u,y,z,t,a,b,c,v,w,d,e,h),dp; //standard
1521
1522*/
Note: See TracBrowser for help on using the repository browser.