# source:git/Singular/LIB/presolve.lib@50cbdc

spielwiese
Last change on this file since 50cbdc was 50cbdc, checked in by Hans Schönemann <hannes@…>, 22 years ago
• Property mode set to `100644`
File size: 41.7 KB
Line
1//last change: 13.02.2001 (Eric Westenberger)
2///////////////////////////////////////////////////////////////////////////////
3version="\$Id: presolve.lib,v 1.18 2001-08-27 14:47:57 Singular Exp \$";
4category="Symbolic-numerical solving";
5info="
6LIBRARY:  presolve.lib     Pre-Solving of Polynomial Equations
7AUTHOR:   Gert-Martin Greuel, email: greuel@mathematik.uni-kl.de,
8
9PROCEDURES:
10 degreepart(id,d1,d2);  elements of id of total degree >= d1 and <= d2
11 elimlinearpart(id);    linear part eliminated from id
12 elimpart(id[,n]);      partial elimination of vars [among first n vars]
13 elimpartanyr(i,p);     factors of p partially eliminated from i in any ring
14 fastelim(i,p[..]);     fast elimination of factors of p from i [options]
16 hilbvec(id[,c,o]);     intvec of Hilberseries of id [in char c and ord o]
17 linearpart(id);        elements of id of total degree <=1
18 tolessvars(id[,]);     maps id to new basering having only vars occuring in id
19 solvelinearpart(id);   reduced std-basis of linear part of id
20 sortandmap(id,s1,s2);  map to new basering with vars sorted w.r.t. complexity
21 sortvars(id[n1,p1..]); sort vars w.r.t. complexity in id [different blocks]
22 valvars(id[..]);       valuation of vars w.r.t. to their complexity in id
23           (parameters in square brackets [] are optional)
24";
25
26LIB "inout.lib";
27LIB "general.lib";
28LIB "matrix.lib";
29LIB "ring.lib";
30LIB "elim.lib";
31///////////////////////////////////////////////////////////////////////////////
32
33proc degreepart (id,int d1,int d2,list #)
34"USAGE:   degreepart(id,d1,d2[,v]);  id=ideal/module, d1,d1=integers, v=intvec
35RETURN:  generators of id of [v-weighted] total degree >= d1 and <= d2
36         (default: v = 1,...,1)
37EXAMPLE: example degreepart; shows an example
38"
39{
40   def dpart = id;
41   int s,ii = size(id),0;
42   if ( size(#)==0 )
43   {
44      for ( ii=1; ii<=s; ii=ii+1 )
45      {
46         dpart[ii] = (jet(id[ii],d1-1)==0)*(id[ii]==jet(id[ii],d2))*id[ii];
47      }
48   }
49   else
50   {
51      for ( ii=1; ii<=s; ii=ii+1 )
52      {
53         dpart[ii]=(jet(id[ii],d1-1,#[1])==0)*(id[ii]==jet(id[ii],d2,#[1]))*id[ii];
54      }
55   }
56   return(simplify(dpart,2));
57}
58example
59{ "EXAMPLE:"; echo = 2;
60   ring r=0,(x,y,z),dp;
61   ideal i=1+x+x2+x3+x4,3,xz+y3+z8;
62   degreepart(i,0,4);
63   module m=[x,y,z],x*[x3,y2,z],[1,x2,z3,0,1];
64   intvec v=2,3,6;
65   show(degreepart(m,8,8,v));
66}
67///////////////////////////////////////////////////////////////////////////////
68
69proc elimlinearpart (ideal i,list #)
70"USAGE:   elimlinearpart(i[,n]);  i=ideal, n=integer,@*
71          default: n=nvars(basering)
72RETURN:   list L with 5 entries:
73  @format
74  L[1]: (interreduced) ideal obtained from i by substituing
75        from the first n variables those, which appear in a linear part
76        of i, by putting this part into triangular form
77  L[2]: ideal of variables which have been substituted
78  L[3]: ideal, j-th element defines substitution of j-th var in [2]
79  L[4]: ideal of variables of basering, eliminated ones are set to 0
80  L[5]: ideal, describing the map from the basering to itself such that
81        L[1] is the image of i
82  @end format
83NOTE:    the procedure does always interreduce the ideal i internally w.r.t.
84         ordering dp.
85EXAMPLE: example elimlinearpart; shows an example
86"
87{
88   int ii,n,fi,k;
89   string o, newo;
90   intvec getoption = option(get);
91   option(redSB);
92   def P = basering;
93   n = nvars(P);
94//--------------- replace ordering by dp-ordering if necessary ----------------
95   o = "dp("+string(n)+")";
96   fi = find(ordstr(P),o);
97   if( fi == 0 or find(ordstr(P),"a") != 0 )
98   {
99      execute("ring newP = ("+charstr(P)+"),("+varstr(P)+"),dp;");
100      ideal i = imap(P,i);
101   }
102//---------------------------------- start ------------------------------------
103   if ( size(#)!=0 ) {  n=#[1]; }
104   ideal maxi,rest = maxideal(1),0;
105   if ( n < nvars(P) ) { rest = maxi[n+1..nvars(P)]; }
106   attrib(rest,"isSB",1);
107//-------------------- interreduce and find linear part  ----------------------
108// interred does the only real work. Because of ordering dp the linear part is
109// within the first elements after interreduction
110// **: perhaps Bareiss to constant matrix of linear part instead of interred,
111// and/or for big systems, interred only those generators of id
112// which do not contain elements not to be eliminated
113
114   ideal id = interred(i);
115
116   if(id[1] == 1 )                          //special case of unit ideal
117   {
118     setring P;
119     list L = ideal(1), ideal(0), ideal(0), maxideal(1), maxideal(1);
120     option(set,getoption);
121     return(L);
122   }
123
124   for ( ii=1; ii<=size(id); ii++ )
125   {
126      if( deg(id[ii]) > 1) { break; }
127      k=ii;
128   }
129   if( k == 0 )       { ideal lin; }
130   else               { ideal lin = id[1..k];}
131   if( k < size(id) ) { id = id[k+1..size(id)]; }
132   else               { id = 0; }
133//----- remove generators from lin containing vars not to be eliminated  ------
134   if ( n < nvars(P) )
135   {
136      for ( ii=1; ii<=size(lin); ii++ )
137      {
138         if ( reduce(lead(lin[ii]),rest) == 0 )
139         {
140            id=lin[ii],id;
141            lin[ii] = 0;
142         }
143      }
144   }
145   lin = simplify(lin,2);
146   attrib(lin,"isSB",1);
148   attrib(eva,"isSB",1);
149   ideal neva = reduce(maxideal(1),eva);
150//------------------ go back to original ring end return  ---------------------
151   if( fi == 0 or find(ordstr(P),"a") != 0 )
152   {
153      setring P;
154      ideal id = imap(newP,id);
155      ideal eva = imap(newP,eva);
156      ideal lin = imap(newP,lin);
157      ideal neva = imap(newP,neva);
158   }
159
160   eva = eva[ncols(eva)..1];  // sorting according to variables in basering
161   lin = lin[ncols(lin)..1];
162   ideal phi= neva;
163   k = 1;
164   for( ii=1; ii<=n; ii++ )
165   {
166      if( neva[ii] == 0 )
167      {
168         phi[ii] = eva[k]-lin[k];
169         k=k+1;
170      }
171   }
172   list L = id, eva, lin, neva, phi;
173   option(set,getoption);
174   return(L);
175}
176example
177{ "EXAMPLE:"; echo = 2;
178   ring s=0,(x,y,z),dp;
179   ideal i = x3+y2+z,x2y2+z3,y+z+1;
180  elimlinearpart(i);
181}
182///////////////////////////////////////////////////////////////////////////////
183
184proc elimpart (ideal i,list #)
185"USAGE:   elimpart(i [,n,e] );  i=ideal, n,e=integers
186         n   : only the first n vars are considered for substitution,@*
187         e =0: substitute from linear part of i (same as elimlinearpart)@*
188         e!=0: eliminate also by direct substitution@*
189         (default: n = nvars(basering), e = 1)
190RETURN:  list of 5 objects:
191  @format
192  [1]: ideal obtained by substituting from the first n variables those
193       from i, which appear in the linear part of i (or, if e!=0, which
194       can be expressed directly in the remaining vars)
195  [2]: ideal, variables which have been substituted
196  [3]: ideal, i-th element defines substitution of i-th var in [2]
197  [4]: ideal of variables of basering, substituted ones are set to 0
198  [5]: ideal, describing the map from the basering, say k[x(1..m)], to
199       itself onto k[..variables fom [4]..] and [1] is the image of i
200  @end format
201  The ideal i is generated by [1] and [3] in k[x(1..m)], the map [5]
202  maps [3] to 0, hence induces an isomorphism
203  @format
204            k[x(1..m)]/i -> k[..variables fom [4]..]/[1]
205  @end format
206NOTE:    If the basering has ordering (c,dp), this is faster for big ideals,
207         since it avoids internal ring change and mapping.
208EXAMPLE: example elimpart; shows an example
209"
210{
211   def P = basering;
212   int n,e = nvars(P),1;
213   if ( size(#)==1 ) {  n=#[1]; }
214   if ( size(#)==2 ) {  n=#[1]; e=#[2];}
215//----------- interreduce linear part with proc elimlinearpart ----------------
216// lin = ideal after interreduction of linear part
217// eva = eliminated (substituted) variables
218// sub = polynomials defining substitution
219// neva= not eliminated variables
220// phi = map describing substitution
221   list L = elimlinearpart(i,n);
222   ideal lin, eva, sub, neva, phi = L[1], L[2], L[3], L[4], L[5];
223//-------- direct substitution of variables if possible and if e!=0 -----------
224// first find terms lin1 of pure degree 1 in each poly of lin
225// k1 = pure degree 1 part, k1+k2 = those polys of lin which contained a pure
226// degree 1 part.
227// Then go to ring newP with ordering c,dp(n) and create a matrix with size(k1)
228// colums and 2 rows, such that if [f1,f2] is a column of M then f1+f2 is one
229// of the polys of lin containing a pure degree 1 part and f1 is this part
230// interreduce this matrix (i.e. Gauss elimination on linear part, with rest
231// transformed accordingly).
232   int ii, kk;
233   if ( e!=0 )
234   {
235      ideal k1,k2;
236      int l = size(lin);
237      ideal lin1 = jet(lin,1) - jet(lin,0);  // part of pure degree 1
238      lin = lin - lin1;                      // rest, part of degree 1 substracted
239
240      for( ii=1; ii<=l; ii++ )
241      {
242         if( lin1[ii] != 0 )
243         {
244            kk = kk+1;
245            k1[kk] = lin1[ii];    // part of pure degree 1, renumbered
246            k2[kk] = lin[ii];     // rest of those polys which had a degree 1 part
247            lin[ii] = 0;
248         }
249      }
250
251      if( kk != 0 )
252      {
253         if( ordstr(P) != "c,dp(n)" )
254         {
255            execute("ring newP = ("+charstr(P)+"),("+varstr(P)+"),(c,dp);");
256            ideal k1 = imap(P,k1);
257            ideal k2 = imap(P,k2);
258            ideal lin = imap(P,lin);
259            ideal eva = imap(P,eva);
260            ideal sub = imap(P,sub);
261            ideal neva = imap(P,neva);
262         }
263         ideal k12 = k1,k2;
264         matrix M = matrix(k12,2,kk);
265        // M = interred(M);
266         l = ncols(M);
267         k1 = M[1,1..l];
268         k2 = M[2,1..l];
269         ideal kin = matrix(k1)+matrix(k2);
270         lin = simplify(lin,2);
271
272         l = size(kin);
273         poly p; map phi; ideal max;
274         for ( ii=1; ii<=n; ii++  )
275         {
276            for (kk=1; kk<=l; kk++ )
277            {
278               p = kin[kk]/var(ii);
279               if ( deg(p) == 0 )
280               {
281                  eva = eva+var(ii);
282                  neva[ii] = 0;
283                  sub = sub+kin[kk]/p;
284                  max = maxideal(1);
285                  max[ii] = var(ii) - (kin[kk]/p);
286                  phi = basering,max;
287                  lin = phi(lin);
288                  kin = simplify(phi(kin),2);
289                  l = size(kin);
290                  ii=ii+1;
291                  break;
292               }
293            }
294         }
295         lin = kin+lin;
296      }
297   }
298   for( ii=1; ii<=size(lin); ii++ )
299   {
300      lin[ii] = cleardenom(lin[ii]);
301   }
302   if( defined(newP) )
303   {
304      setring P;
305      lin = imap(newP,lin);
306      eva = imap(newP,eva);
307      sub = imap(newP,sub);
308      neva = imap(newP,neva);
309   }
310   for( ii=1; ii<=n; ii++ )
311   {
312      for( kk=1; kk<=size(eva); kk++ )
313      {
314         if (phi[ii] == eva[kk] )
315         {  phi[ii] = eva[kk]-sub[kk]; break; }
316      }
317   }
318   L = lin, eva, sub, neva, phi;
319  return(L);
320}
321example
322{ "EXAMPLE:"; echo = 2;
323   ring s=0,(x,y,z),dp;
324   ideal i =x2+y2,x2+y+1;
325   elimpart(i,3,0);
326   elimpart(i,3,1);
327}
328
329///////////////////////////////////////////////////////////////////////////////
330
331proc elimpartanyr (ideal i, list #)
332"USAGE:   elimpartanyr(i [,p,e] );  i=ideal, p=polynomial, e=integer@*
333         p: product of vars to be eliminated,@*
334         e =0: substitute from linear part of i (same as elimlinearpart)@*
335         e!=0: eliminate also by direct substitution@*
336         (default: p=product of all vars, e=1)
337RETURN:  list of 6 objects:
338  @format
339  [1]: (interreduced) ideal obtained by substituting from i those vars
340       appearing in p, which occur in the linear part of i (or which can
341       be expressed directly in the remaining variables, if e!=0)
342  [2]: ideal, variables which have been substituted
343  [3]: ideal, i-th element defines substitution of i-th var in [2]
344  [4]: ideal of variables of basering, substituted ones are set to 0
345  [5]: ideal, describing the map from the basering, say k[x(1..m)], to
346       itself onto k[..variables fom [4]..] and [1] is the image of i
347  [6]: int, # of vars considered for substitution (= # of factors of p)
348  @end format
349  The ideal i is generated by [1] and [3] in k[x(1..m)], the map [5]
350  maps [3] to 0, hence induces an isomorphism
351  @format
352            k[x(1..m)]/i -> k[..variables fom [4]..]/[1]
353  @end format
354NOTE:    the proc uses @code{execute} to create a ring with ordering dp and vars
355         placed correctly and then applies @code{elimpart}.
356EXAMPLE: example elimpartanyr; shows an example
357"
358{
359   def P = basering;
360   int j,n,e = 0,0,1;
361   poly p = product(maxideal(1));
362   if ( size(#)==1 ) { p=#[1]; }
363   if ( size(#)==2 ) { p=#[1]; e=#[2]; }
364   string a,b;
365   for ( j=1; j<=nvars(P); j++ )
366   {
367      if (deg(p/var(j))>=0) { a = a+varstr(j)+","; n = n+1; }
368      else { b = b+varstr(j)+","; }
369   }
370   if ( size(b) != 0 ) { b = b[1,size(b)-1]; }
371   else { a = a[1,size(a)-1]; }
372   execute("ring gnir ="+charstr(P)+",("+a+b+"),dp;");
373   ideal i = imap(P,i);
374   list L = elimpart(i,n,e)+list(n);
375   setring P;
376   list L = imap(gnir,L);
377   return(L);
378}
379example
380{ "EXAMPLE:"; echo = 2;
381   ring s=0,(x,y,z),dp;
382   ideal i = x3+y2+z,x2y2+z3,y+z+1;
383   elimpartanyr(i,z);
384}
385///////////////////////////////////////////////////////////////////////////////
386
387proc fastelim (ideal i, poly p, list #)
388"USAGE:   fastelim(i,p[h,o,a,b,e,m]); i=ideal, p=polynomial; h,o,a,b,e=integers
389          p: product of variables to be eliminated;@*
390  Optional parameters:
391  @format
392  - h !=0: use Hilbert-series driven std-basis computation
393  - o !=0: use proc @code{valvars} for a - hopefully - optimal ordering of vars
394  - a !=0: order vars to be eliminated w.r.t. increasing complexity
395  - b !=0: order vars not to be eliminated w.r.t. increasing complexity
396  - e !=0: use @code{elimpart} first to eliminate easy part
397  - m !=0: compute a minimal system of generators
398  @end format
399  (default: h,o,a,b,e,m = 0,1,0,0,0,0)
400RETURN:  ideal obtained from i by eliminating those variables, which occur in p
401EXAMPLE: example fastelim; shows an example.
402"
403{
404   def P = basering;
405   int h,o,a,b,e,m = 0,1,0,0,0,0;
406   if ( size(#) == 1 ) { h=#[1]; }
407   if ( size(#) == 2 ) { h=#[1]; o=#[2]; }
408   if ( size(#) == 3 ) { h=#[1]; o=#[2]; a=#[3]; }
409   if ( size(#) == 4 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4];}
410   if ( size(#) == 5 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4]; e=#[5]; }
411   if ( size(#) == 6 ) { h=#[1]; o=#[2]; a=#[3]; b=#[4]; e=#[5]; m=#[6]; }
412   list L = elimpartanyr(i,p,e);
413   poly q = product(L[2]);     //product of vars which are already eliminated
414   if ( q==0 ) { q=1; }
415   p = p/q;                    //product of vars which must still be eliminated
416   int nu = size(L[5])-size(L[2]);   //number of vars which must still be eliminated
417   if ( p==1 )                 //ready if no vars are left
418   {                           //compute minbase if 3-rd argument !=0
419      if ( m != 0 ) { L[1]=minbase(L[1]); }
420      return(L);
421   }
422//---------------- create new ring with remaining variables -------------------
423   string newvar = string(L[4]);
424   L = L[1],p;
425   execute("ring r1=("+charstr(P)+"),("+newvar+"),"+"dp;");
426   list L = imap(P,L);
427//------------------- find "best" ordering of variables  ----------------------
428   newvar = string(maxideal(1));
429   if ( o != 0 )
430   {
431      list ordevar = valvars(L[1],a,L[2],b);
432      intvec v = ordevar[1];
433      newvar=string(sort(maxideal(1),v)[1]);
434//------------ create new ring with "best" ordering of variables --------------
435      changevar("r0",newvar);
436      list L = imap(r1,L);
437      kill r1;
438      def r1 = r0;
439      kill r0;
440   }
441//----------------- h==0: eliminate remaining vars directly -------------------
442   if ( h == 0 )
443   {
444      L[1] = eliminate(L[1],L[2]);
445      def r2 = r1;
446   }
447   else
448//------- h!=0: homogenize and compute Hilbert-series using hilbvec ----------
449   {
450      intvec hi = hilbvec(L[1]);         // Hilbert-series of i
451      execute("ring r2=("+charstr(P)+"),("+varstr(basering)+",@homo),dp;");
452      list L = imap(r1,L);
453      L[1] = homog(L[1],@homo);          // @homo = homogenizing var
454//---- use Hilbert-series to eliminate variables with Hilbert-driven std -----
455      L[1] = eliminate(L[1],L[2],hi);
456      L[1]=subst(L[1],@homo,1);          // dehomogenize by setting @homo=1
457   }
458   if ( m != 0 )                         // compute minbase
459   {
460      if ( #[1] != 0 ) { L[1] = minbase(L[1]); }
461   }
462   def id = L[1];
463   setring P;
464   return(imap(r2,id));
465}
466example
467{ "EXAMPLE:"; echo = 2;
468   ring s=31991,(e,f,x,y,z,t,u,v,w,a,b,c,d),dp;
469   ideal i = w2+f2-1, x2+t2+a2-1,  y2+u2+b2-1, z2+v2+c2-1,
470            d2+e2-1, f4+2u, wa+tf, xy+tu+ab;
471   fastelim(i,xytua,1,1);       //with hilb,valvars
472   fastelim(i,xytua,1,0,1);     //with hilb,minbase
473}
474///////////////////////////////////////////////////////////////////////////////
475
476proc faststd (@id,string @s1,string @s2, list #)
477"USAGE:   faststd(id,s1,s2[,\"hilb\",\"sort\",\"dec\",o,\"blocks\"]);
478         id=ideal/module, s1,s2=strings (names for new ring and maped id)
479         o = string (allowed ordstring:\"lp\",\"dp\",\"Dp\",\"ls\",\"ds\",\"Ds\")
480         \"hilb\",\"sort\",\"dec\",\"block\" options for Hilbert-std, sortandmap
481COMPUTE: create a new ring (with \"best\" ordering of vars) and compute a
482         std-basis of id (hopefully faster)
483         - If say, s1=\"R\" and s2=\"j\", the new basering has name R and the
484           std-basis of the image of id in R has name j
485         - \"hilb\"  : use Hilbert-series driven std-basis computation
486         - \"sort\"  : use 'sortandmap' for a best ordering of vars
487         - \"dec\"   : order vars w.r.t. decreasing complexity (with \"sort\")
488         - \"block\" : create blockordering, each block having ordstr=o, s.t.
489                     vars of same complexity are in one block (with \"sort\")
490         - o       : defines the basic ordering of the resulting ring
491         default: o = ordering of 1-st block of basering - if it is allowed,
492                      else o=\"dp\",
493                  \"sort\", if none of the optional parameters is given
494RETURN:  nothing
495NOTE:    This proc is only useful for hard problems where other methods fail.
496         \"hilb\" is useful for hard orderings (as \"lp\") or for characteristic 0,
497         it is correct for \"lp\",\"dp\",\"Dp\" (and for blockorderings combining
498         these) but not for s-orderings or if the vars have different weights.
499         There seem to be only few cases in which \"dec\" is fast
500EXAMPLE: example faststd; shows an example.
501"
502{
503   def @P = basering;
504   int @h,@s,@n,@m,@ii = 0,0,0,0,0;
505   string @o,@va,@c = ordstr(basering),"","";
506//-------------------- prepare ordering and set options -----------------------
507   if ( @o[1]=="c" or @o[1]=="C")
508      {  @o = @o[3,2]; }
509   else
510      { @o = @o[1,2]; }
511   if( @o[1]!="d" and @o[1]!="D" and @o[1]!="l")
512      { @o="dp"; }
513
514   if (size(#) == 0 )
515      { @s = 1; }
516   for ( @ii=1; @ii<=size(#); @ii++ )
517   {
518      if ( typeof(#[@ii]) != "string" )
519      {
520         "// wrong syntax! type: help faststd";
521         return();
522      }
523      else
524      {
525         if ( #[@ii] == "hilb"  ) { @h = 1; }
526         if ( #[@ii] == "dec"   ) { @n = 1; }
527         if ( #[@ii] == "block" ) { @m = 1; }
528         if ( #[@ii] == "sort"  ) { @s = 1; }
529         if ( #[@ii]=="lp" or #[@ii]=="dp" or #[@ii]=="Dp" or #[@ii]=="ls"
530              or #[@ii]=="ds" or #[@ii]=="Ds" ) { @o = #[@ii]; }
531      }
532   }
533   if( voice==2 ) { "// choosen options, hilb sort dec block:",@h,@s,@n,@m; }
534
535//-------------------- nosort: create ring with new name ----------------------
536   if ( @s==0 )
537   {
538      execute("ring "+@s1+"=("+charstr(@P)+"),("+varstr(@P)+"),("+@o+");");
539      def @id = imap(@P,@id);
540      verbose(noredefine);
541      def @P = basering;
542      verbose(redefine);
543      kill `@s1`;
544      if ( @h==0 ) { @id = std(@id); }
545   }
546//--------- sort: create new ring with "best" ordering of variables -----------
547 proc bestorder(@id,string @s1,string @s2,int @n,string @o,int @m,int @l)
548  {
549     intvec getoption = option(get);
550     option(redSB);
551     @id = interred(sort(@id)[1]);
552     poly @p = product(maxideal(1),1..@l);
553     def i,s1,s2,n,p,o,m = @id,@s1,@s2,@n,@p,@o,@m;
554     sortandmap(i,s1,s2,n,p,0,o,m);
555     option(set,getoption);
556     keepring(basering);
557  }
558//---------------------- no hilb: compute SB directly -------------------------
559   if ( @s != 0 and @h == 0 )
560   {
561      bestorder(@id,@s1,@s2,@n,@o,@m,nvars(@P));
562      verbose(noredefine);
563      def @P = basering;
564      verbose(redefine);
565      kill `@s1`;
566      def @id = `@s2`;
567      @id = std(@id);
568   }
569//------- hilb: homogenize and compute Hilbert-series using hilbvec -----------
570// this uses another standardbasis computation
571   if ( @h != 0 )
572   {
573      execute("ring @Q=("+charstr(@P)+"),("+varstr(@P)+",@homo),("+@o+");");
574      def @id = imap(@P,@id);
575      kill @P;
576      @id = homog(@id,@homo);               // @homo = homogenizing var
577      if ( @s != 0 )
578      {
579         bestorder(@id,@s1,@s2,@n,@o,@m,nvars(@Q)-1);
580         verbose(noredefine);
581         def @Q= basering;
582         kill `@s1`;
583         def @id = `@s2`;
584         verbose(redefine);
585      }
586      intvec @hi;                     // encoding of Hilbert-series of i
587      @hi = hilbvec(@id);
588      //if ( @s!=0 ) { @hi = hilbvec(@id,"32003",ordstr(@Q)); }
589      //else { @hi = hilbvec(@id); }
590//-------------------------- use Hilbert-driven std --------------------------
591      @id = std(@id,@hi);
592      @id = subst(@id,@homo,1);             // dehomogenize by setting @homo=1
593      @va = varstr(@Q)[1,size(varstr(@Q))-6];
594      if ( @s!=0 )
595      {
596         @o = ordstr(@Q);
597         if ( @o[1]=="c" or @o[1]=="C") { @o = @o[1,size(@o)-6]; }
598         else { @o = @o[1,size(@o)-8] + @o[size(@o)-1,2]; }
599      }
600      execute("ring @P=("+charstr(@Q)+"),("+@va+"),("+@o+");");
601      def @id = imap(@Q,@id);
602   }
603   def `@s1` = @P;
604   def `@s2` = @id;
605   attrib(`@s2`,"isSB",1);
606   export(`@s2`);
607   kill @P;
608   keepring(basering);
609   if( voice==2 ) { "// basering is now "+@s1+", std-basis has name "+@s2; }
610   return();
611}
612example
613{ "EXAMPLE:"; echo = 2;
614   ring s = 0,(e,f,x,y,z,t,u,v,w,a,b,c,d),(c,lp);
615   ideal i = w2+f2-1, x2+t2+a2-1,  y2+u2+b2-1, z2+v2+c2-1,
616            d2+e2-1, f4+2u, wa+tf, xy+tu+ab;
617  option(prot); timer=1;
618   int time = timer;
619   ideal j=std(i);
620   timer-time;
621   show(R);dim(j),mult(j);
622   int time = timer;
623   faststd(i,"R","i");                      // use "best" ordering of vars
624   timer-time;
625   show(R);dim(i),mult(i);
626   setring s;time = timer;
627   faststd(i,"R","i","hilb");                // hilb-std only
628   timer-time;
629   show(R);dim(i),mult(i);
630   setring s;time = timer;
631   faststd(i,"R","i","hilb","sort");         // hilb-std,"best" ordering
632   timer-time;
633   show(R);dim(i),mult(i);
634    setring s;time = timer;
635   faststd(i,"R","i","hilb","sort","block","dec"); // hilb-std,"best",blocks
636   timer-time;
637   show(R);dim(i),mult(i);
638  setring s;time = timer;
639   timer-time;time = timer;
640   faststd(i,"R","i","sort","block","Dp"); //"best",decreasing,Dp-blocks
641   timer-time;
642   show(R);dim(i),mult(i);
643}
644///////////////////////////////////////////////////////////////////////////////
645
646proc findvars(id, list #)
647"USAGE:   findvars(id [,any] ); id=poly/ideal/vector/module/matrix, any=any type
648RETURN:  if no second argument is present: ideal of variables occuring in id,@*
649         if a second argument is given (of any type): list L with 4 entries:
650  @format
651  L[1]: ideal of variables occuring in id
652  L[2]: intvec of variables occuring in id
653  L[3]: ideal of variables not occuring in id
654  L[4]: intvec of variables not occuring in id
655  @end format
656EXAMPLE: example findvars; shows an example
657"
658{
659   int ii,n;
660   ideal found, notfound;
661   intvec f,nf;
662   n = nvars(basering);
663   ideal i = simplify(ideal(matrix(id)),10);
664   matrix M[ncols(i)][1] = i;
665   vector v = module(M)[1];
666   ideal max = maxideal(1);
667
668   for (ii=1; ii<=n; ii++)
669   {
670      if ( v != subst(v,var(ii),0) )
671      {
672         found = found+var(ii);
673         f = f,ii;
674      }
675      else
676      {
677         notfound = notfound+var(ii);
678         nf = nf,ii;
679      }
680   }
681   if ( size(f)>1 ) { f = f[2..size(f)]; }      //intvec of found vars
682   if ( size(nf)>1 ) { nf = nf[2..size(nf)]; }  //intvec of vars not found
683   if( size(#)==0 )  { return(found); }
684   if( size(#)!=0 )  { list L = found,f,notfound,nf; return(L); }
685}
686example
687{ "EXAMPLE:"; echo = 2;
688   ring s  = 0,(e,f,x,y,t,u,v,w,a,d),dp;
689   ideal i = w2+f2-1, x2+t2+a2-1;
690   findvars(i);
691   findvars(i,1);
692}
693///////////////////////////////////////////////////////////////////////////////
694
695proc hilbvec (@id, list #)
696"USAGE:   hilbvec(id[,c,o]); id=poly/ideal/vector/module/matrix, c,o=strings,@*
697          c=char, o=ordering used by @code{hilb}@*
698          (default: c=\"32003\", o=\"dp\")
699RETURN:  intvec of 1-st Hilbert-series of id, computed in char c and ordering o
700NOTE:    id must be homogeneous (i.e. all vars have weight 1)
701EXAMPLE: example hilbvec; shows an example
702"
703{
704   def @P = basering;
705   string @c,@o = "32003", "dp";
706   if ( size(#) == 1 ) {  @c = #[1]; }
707   if ( size(#) == 2 ) {  @c = #[1]; @o = #[2]; }
708   string @si = typeof(@id)+" @i = "+string(@id)+";";  //** weg
709   execute("ring @r=("+@c+"),("+varstr(basering)+"),("+@o+");");
710   //**def i = imap(P,@id);
711   execute(@si);                   //** weg
712   //show(basering);
713   @i = std(@i);
714   intvec @hi = hilb(@i,1);         // intvec of 1-st Hilbert-series of id
715   return(@hi);
716}
717example
718{ "EXAMPLE:"; echo = 2;
719   ring s   = 0,(e,f,x,y,z,t,u,v,w,a,b,c,d,H),dp;
720   ideal id = w2+f2-1, x2+t2+a2-1,  y2+u2+b2-1, z2+v2+c2-1,
721              d2+e2-1, f4+2u, wa+tf, xy+tu+ab;
722   id = homog(id,H);
723   hilbvec(id);
724}
725///////////////////////////////////////////////////////////////////////////////
726
727proc linearpart (id)
728"USAGE:   linearpart(id);  id=ideal/module
729RETURN:  generators of id of total degree <= 1
730EXAMPLE: example linearpart; shows an example
731"
732{
733   return(degreepart(id,0,1));
734}
735example
736{ "EXAMPLE:"; echo = 2;
737   ring r=0,(x,y,z),dp;
738   ideal i=1+x+x2+x3,3,x+3y+5z;
739   linearpart(i);
740   module m=[x,y,z],x*[x3,y2,z],[1,x2,z3,0,1];
741   show(linearpart(m));
742}
743///////////////////////////////////////////////////////////////////////////////
744
745proc tolessvars (id ,list #)
746"USAGE:   tolessvars(id [,s1,s2] ); id poly/ideal/vector/module/matrix,
747          s1,s2=strings@*
748          s1: name of new ring,@*
749          s2: new ordering@*
750          (default: s1=\"R(n)\" where n is the # of vars in the new ring,
751          s2=\"dp\" or \"ds\" depending whether the first block of the old
752          ordering is a p- resp. an s-ordering)
753
754CREATE:  nothing, if id contains all vars of the basering.@*
755         Else, create a ring with same char as the basering, but possibly less
756         variables (only those variables which actually occur in id) and map
757         id to the new ring, which will be the basering after the proc has
758         finished.
759DISPLAY: If printlevel >=0, display ideal of vars, which have been ommitted from
760         the old ring
761RETURN:  the original ideal id (see NOTE)
762NOTE:    You must not type, say, 'ideal id=tolessvars(id);' since the ring
763         to which 'id' would belong will only be defined by the r.h.s.. But you
764         may type 'def id=tolessvars(id);' or 'list id=tolessvars(id);'
765         since then 'id' does not a priory belong to a ring, its type will
766         be defined by the right hand side. Moreover, do not use a name which
767         occurs in the old ring, for the same reason.
768EXAMPLE: example tolessvars; shows an example
769"
770{
771//---------------- initialisation and check occurence of vars -----------------
772   int s,ii,n,fp,fs;
773   string s1,s2,newvar;
774   int pr = printlevel-voice+3;  // p = printlevel+1 (default: p=1)
775   def P = basering;
776   s2 = ordstr(P);
777
778   list L = findvars(id,1);
779   newvar = string(L[1]);    // string of new variables
780   n = size(L[1]);           // number of new variables
781   if( n == 0 )
782   {
783      dbprint( pr,"","// no variable occured in "+typeof(id)+", no change of ring!");
784      return(id);
785   }
786   if( n == nvars(P) )
787   {
788      dbprint( pr,"","// all variables occured in "+typeof(id)+", no change of ring!");
789      return(id);
790   }
791//----------------- prepare new ring, map to it and return --------------------
792   s1 = "R("+string(n)+")";
793   if ( size(#) == 0 )
794   {
795       fp = find(s2,"p");
796       fs = find(s2,"s");
797       if( fs==0 or (fs>=fp && fp!=0) ) { s2="dp"; }
798       else {  s2="ds"; }
799   }
800   if ( size(#) ==1 ) { s1=#[1]; }
801   if ( size(#) ==2 ) { s1=#[1]; s2=#[2]; }
802   //dbprint( pr,"","// variables which did not occur:",simplify(max,2) );
803   dbprint( pr,"","// variables which did not occur:",L[3] );
804
805   execute("ring "+s1+"=("+charstr(P)+"),("+newvar+"),("+s2+");");
806   def id = imap(P,id);
807   export(basering);
808   keepring (basering);
809   dbprint( pr,"// basering is now "+s1 );
810   return(id);
811}
812example
813{ "EXAMPLE:"; echo = 2;
814   ring r  = 0,(x,y,z),dp;
815   ideal i = y2-x3,x-3,y-2x;
816   def j   = tolessvars(i,"R_r","lp");
817   show(basering);
818   j;
819   kill R_r;
820}
821///////////////////////////////////////////////////////////////////////////////
822
823proc solvelinearpart (id,list #)
824"USAGE:   solvelinearpart(id [,n] );  id=ideal/module, n=integer,@*
825          (default: n=0)
826RETURN:  (interreduced) generators of id of degree <=1 in reduced triangular
827         form if n=0 [non-reduced triangular form if n!=0]
828ASSUME:  monomial ordering is a global ordering (p-ordering)
829NOTE:    may be used to solve a system of linear equations
830         see proc @code{gauss_row} from 'matrix.lib' for a different method
831WARNING: the result is very likely to be false for 'real' coefficients, use
833EXAMPLE: example solvelinearpart; shows an example
834"
835{
836   intvec getoption = option(get);
837   option(redSB);
838   if ( size(#)!=0 )
839   {
840      if(#[1]!=0) { option(noredSB); }
841   }
842   def lin = interred(degreepart(id,0,1));
843   if ( size(#)!=0 )
844   {
845      if(#[1]!=0)
846      {
847         return(lin);
848      }
849   }
850   option(set,getoption);
851   return(simplify(lin,1));
852}
853example
854{ "EXAMPLE:"; echo = 2;
855   // Solve the system of linear equations:
856   //         3x +   y +  z -  u = 2
857   //         3x +  8y + 6z - 7u = 1
858   //        14x + 10y + 6z - 7u = 0
859   //         7x +  4y + 3z - 3u = 3
860   ring r = 0,(x,y,z,u),lp;
861   ideal i= 3x +   y +  z -  u,
862           13x +  8y + 6z - 7u,
863           14x + 10y + 6z - 7u,
864            7x +  4y + 3z - 3u;
865   ideal j= 2,1,0,3;
866   j = i-j;                        // difference of 1x4 matrices
867                                   // compute reduced triangular form, setting
868   solvelinearpart(j);             // the RHS equal 0 gives the solutions!
869   solvelinearpart(j,1); "";       // triangular form, not reduced
870}
871///////////////////////////////////////////////////////////////////////////////
872
873proc sortandmap (@id,string @s1,string @s2, list #)
874"USAGE:   sortandmap(id,s1,s2[,n1,p1,n2,p2...,o1,m1,o2,m2...]);@*
875         id=poly/ideal/vector/module,@*
876         s1,s2 = strings (names for new ring and mapped id),@*
877         p1,p2,...= polynomials (product of variables),@*
878         n1,n2,...= integers,@*
879         o1,o2,...= strings,@*
880         m1,m2,...= integers@*
881         (default: p1=product of all vars, n1=0, o1=\"dp\",m1=0)
882         the last pi (containing the remaining vars) may be omitted
883CREATE:  a new ring and map id into it, the new ring has same char as basering
884         but with new ordering and vars sorted in the following manner:
885  @format
886  - each block of vars occuring in pi is sorted w.r.t. its complexity in id,
887  - ni controls the sorting in i-th block (= vars occuring in pi):
888    ni=0 (resp.!=0) means that less (resp. more) complex vars come first
889  - oi and mi define the monomial ordering of the i-th block:
890    if mi =0, oi=ordstr(i-th block)
891    if mi!=0, the ordering of the i-th block itself is a blockordering,
892      each subblock having ordstr=oi, such that vars of same complexity are
893      in one block
894  @end format
895  Note that only simple ordstrings oi are allowed:
896  \"lp\",\"dp\",\"Dp\",\"ls\",\"ds\",\"Ds\".
897RETURN:  nothing
898NOTE:    We define a variable x to be more complex than y (with respect to id)
899         if val(x) > val(y) lexicographically, where val(x) denotes the
900         valuation vector of x:@*
901         consider id as list of polynomials in x with coefficients in the
902         remaining variables. Then:@*
903         val(x) = (maximal occuring power of x,  # of all monomials in leading
904         coefficient, # of all monomials in coefficient of next smaller power
905         of x,...).
906EXAMPLE: example sortandmap; shows an example
907"
908{
909   def @P = basering;
910   int @ii,@jj;
911   intvec @v;
912   string @o;
913//----------------- find o in # and split # into 2 lists ---------------------
914   # = # +list("dp",0);
915   for ( @ii=1; @ii<=size(#); @ii++)
916   {
917      if ( typeof(#[@ii])=="string" )  break;
918   }
919   if ( @ii==1 ) { list @L1 = list(); }
920   else { list @L1 = #[1..@ii-1]; }
921   list @L2 = #[@ii..size(#)];
922   list @L = sortvars(@id,@L1);
923   string @va = string(@L[1]);
924   list @l = @L[2];   //e.g. @l[4]=intvec describing permutation of 1-st block
925//----------------- construct correct ordering with oi and mi ----------------
926   for ( @ii=4; @ii<=size(@l); @ii=@ii+4 )
927   {
928      @L2=@L2+list("dp",0);
929      if ( @L2[@ii/2] != 0)
930      {
931         @v = @l[@ii];
932         for ( @jj=1; @jj<=size(@v); @jj++ )
933         {
934           @o = @o+@L2[@ii/2 -1]+"("+string(@v[@jj])+"),";
935         }
936      }
937      else
938      {
939         @o = @o+@L2[@ii/2 -1]+"("+string(size(@l[@ii/2]))+"),";
940      }
941   }
942   @o=@o[1..size(@o)-1];
943//------------------ create new ring and make objects global -----------------
944   execute("ring "+@s1+"=("+charstr(@P)+"),("+@va+"),("+@o+");");
945   def @id = imap(@P,@id);
946   execute("def "+ @s2+"=@id;");
947   execute("export("+@s1+");");
948   execute("export("+@s2+");");
949   keepring(basering);
950   return();
951}
952example
953{ "EXAMPLE:"; echo = 2;
954   ring s = 32003,(x,y,z),dp;
955   ideal i=x3+y2,xz+z2;
956   sortandmap(i,"R_r","i");
957   // i is now an ideal in the new basering R_r
958   show(R_r);
959   kill R_r; setring s;
960   sortandmap(i,"R_r","i",1,xy,0,z,0,"ds",0,"lp",0);
961   show(R_r);
962   kill R_r;
963}
964///////////////////////////////////////////////////////////////////////////////
965
966proc sortvars (id, list #)
967"USAGE:   sortvars(id[,n1,p1,n2,p2,...]);@*
968         id=poly/ideal/vector/module,@*
969         p1,p2,...= polynomials (product of vars),@*
970         n1,n2,...=integers@*
971         (default: p1=product of all vars, n1=0)
972         the last pi (containing the remaining vars) may be omitted
973COMPUTE: sort variables with respect to their complexity in id
974RETURN:  list of two elements, an ideal and a list:
975  @format
976  [1]: ideal, variables of basering sorted w.r.t their complexity in id
977       ni controls the ordering in i-th block (= vars occuring in pi):
978       ni=0 (resp.!=0) means that less (resp. more) complex vars come first
979  [2]: a list with 4 entries for each pi:
980       ideal ai : vars of pi in correct order,
981       intvec vi: permutation vector describing the ordering in ai,
982       intmat Mi: valuation matrix of ai, the columns of Mi being the
983                  valuation vectors of the vars in ai
984       intvec wi: size of 1-st, 2-nd,... block of identical columns of Mi
985                  (vars with same valuation)
986  @end format
987NOTE:    We define a variable x to be more complex than y (with respect to id)
988         if val(x) > val(y) lexicographically, where val(x) denotes the
989         valuation vector of x:@*
990         consider id as list of polynomials in x with coefficients in the
991         remaining variables. Then:@*
992         val(x) = (maximal occuring power of x,  # of all monomials in leading
993         coefficient, # of all monomials in coefficient of next smaller power
994         of x,...).
995EXAMPLE: example sortvars; shows an example
996"
997{
998   int ii,jj,n,s;
999   list L = valvars(id,#);
1000   list L2, L3 = L[2], L[3];
1001   list K; intmat M; intvec v1,v2,w;
1002   ideal i = sort(maxideal(1),L[1])[1];
1003   for ( ii=1; ii<=size(L2); ii++ )
1004   {
1005      M = transpose(L3[2*ii]);
1006      M = M[L2[ii],1..nrows(L3[2*ii])];
1007      w = 0; s = 0;
1008      for ( jj=1; jj<=nrows(M)-1; jj++ )
1009      {
1010         v1 = M[jj,1..ncols(M)];
1011         v2 = M[jj+1,1..ncols(M)];
1012         if ( v1 != v2 ) { n=jj-s; s=s+n; w = w,n; }
1013      }
1014      w=w,nrows(M)-s; w=w[2..size(w)];
1015      K = K+sort(L3[2*ii-1],L2[ii])+list(transpose(M))+list(w);
1016   }
1017   L = i,K;
1018   return(L);
1019}
1020example
1021{ "EXAMPLE:"; echo = 2;
1022   ring s=0,(x,y,z,w),dp;
1023   ideal i = x3+y2+yw2,xz+z2,xyz-w2;
1024   sortvars(i,0,xy,1,zw);
1025}
1026///////////////////////////////////////////////////////////////////////////////
1027
1028proc valvars (id, list #)
1029"USAGE:   valvars(id[,n1,p1,n2,p2,...]);@*
1030         id=poly/ideal/vector/module,@*
1031         p1,p2,...= polynomials (product of vars),@*
1032         n1,n2,...= integers,
1033
1034         ni controls the ordering of vars occuring in pi: ni=0 (resp.!=0) means
1035         that less (resp. more) complex vars come first@*
1036         (default: p1=product of all vars, n1=0)
1037         the last pi (containing the remaining vars) may be omitted
1038COMPUTE: valuation (complexity) of variables with respect to id.@*
1039         ni controls the ordering of vars occuring in pi:@*
1040         ni=0 (resp.!=0) means that less (resp. more) complex vars come first.
1041RETURN:  list with 3 entries:
1042  @format
1043  [1]: intvec, say v, describing the permutation such that the permuted
1044       ringvariables are ordered with respect to their complexity in id
1045  [2]: list of intvecs, i-th intvec, say v(i) describing permutation
1046       of vars in a(i) such that v=v(1),v(2),...
1047  [3]: list of ideals and intmat's, say a(i) and M(i), where
1048       a(i): factors of pi,
1049       M(i): valuation matrix of a(i), such that the j-th column of M(i)
1050             is the valuation vector of j-th generator of a(i)
1051         @end format
1052NOTE:    Use @code{sortvars} in order to actually sort the variables!
1053         We define a variable x to be more complex than y (with respect to id)
1054         if val(x) > val(y) lexicographically, where val(x) denotes the
1055         valuation vector of x:@*
1056         consider id as list of polynomials in x with coefficients in the
1057         remaining variables. Then:@*
1058         val(x) = (maximal occuring power of x,  # of all monomials in leading
1059         coefficient, # of all monomials in coefficient of next smaller power
1060         of x,...).
1061EXAMPLE: example valvars; shows an example
1062"
1063{
1064//---------------------------- initialization ---------------------------------
1065   int ii,jj,kk,n;
1066   list L;                    // list of valuation vectors in one block
1067   intvec vec;                // describes permutation of vars (in one block)
1068   list blockvec;             // i-th element = vec of i-th block
1069   intvec varvec;             // result intvector
1070   list Li;                   // result list of ideals
1071   list LM;                   // result list of intmat's
1072   intvec v,w,s;              // w valuation vector for one variable
1073   matrix C;                  // coefficient matrix for different variables
1074   ideal i = simplify(ideal(matrix(id)),10);
1075
1076//---- for each pii in # create ideal a(ii) intvec v(ii) and list L(ii) -------
1077// a(ii) = ideal of vars in product, v(ii)[j]=k <=> a(ii)[j]=var(k)
1078
1079   v = 1..nvars(basering);
1080   int l = size(#);
1081   if ( l >= 2 )
1082   {
1083      ideal m=maxideal(1);
1084      for ( ii=2; ii<=l; ii=ii+2 )
1085      {
1086         int n(ii) = #[ii-1];
1087         ideal a(ii);
1088         intvec v(ii);
1089         for ( jj=1; jj<=nvars(basering); jj++ )
1090         {
1091            if ( #[ii]/var(jj) != 0)
1092            {
1093               a(ii) = a(ii) + var(jj);
1094               v(ii)=v(ii),jj;
1095               m[jj]=0;
1096               v[jj]=0;
1097            }
1098         }
1099         v(ii)=v(ii)[2..size(v(ii))];
1100      }
1101      if ( size(m)!=0 )
1102      {
1103         l = 2*(l/2)+2;
1104         ideal a(l) = simplify(m,2);
1105         intvec v(l) = compress(v);
1106         int n(l);
1107         if ( size(#)==l-1 ) { n(l) = #[l-1]; }
1108      }
1109   }
1110   else
1111   {
1112      l = 2;
1113      ideal a(2) = maxideal(1);
1114      intvec v(2) = v;
1115      int n(2);
1116      if ( size(#)==1 ) { n(2) = #[1]; }
1117   }
1118//------------- start loop to order variables in each a(ii) -------------------
1119
1120   for ( kk=2; kk<=l; kk=kk+2 )
1121   {
1122      L = list();
1123      n = 0;
1124//---------------- get valuation of all variables in a(kk) --------------------
1125      for ( ii=1; ii<=size(a(kk)); ii++ )
1126      {
1127         C = coeffs(i,a(kk)[ii]);
1128         w = nrows(C); // =(maximal occuring power of a(kk)[ii])+1
1129         for ( jj=w[1]; jj>1; jj-- )
1130         {
1131            s = size(C[jj,1..ncols(C)]);
1132            w[w[1]-jj+2] = sum(s);
1133         }
1134         // w[1] should represent the maximal occuring power of a(kk)[ii] so it
1135         // has to be decreased by 1 since otherwise the constant term is also
1136         // counted
1137         w[1]=w[1]-1;
1138
1139         L[ii]=w;
1140         n = size(w)*(size(w) > n) + n*(size(w) <= n);
1141      }
1142      intmat M(kk)[size(a(kk))][n];
1143      for ( ii=1; ii<=size(a(kk)); ii++ )
1144      {
1145         if ( n==1 ) { w = L[ii]; M(kk)[ii,1] = w[1]; }
1146         else  { M(kk)[ii,1..n] = L[ii]; }
1147      }
1148      LM[kk-1] = a(kk);
1149      LM[kk] = transpose(compress(M(kk)));
1150//------------------- compare valuation and insert in vec ---------------------
1151      vec = sort(L)[2];
1152      if ( n(kk) != 0 ) { vec = vec[size(vec)..1]; }
1153      blockvec[kk/2] = vec;
1154      vec = sort(v(kk),vec)[1];
1155      varvec = varvec,vec;
1156   }
1157   varvec = varvec[2..size(varvec)];
1158   list result = varvec,blockvec,LM;
1159   return(result);
1160}
1161example
1162{ "EXAMPLE:"; echo = 2;
1163   ring s=0,(x,y,z,a,b),dp;
1164   ideal i=ax2+ay3-b2x,abz+by2;
1165   valvars (i,0,xyz);
1166}
1167///////////////////////////////////////////////////////////////////////////////
1168/*
1169
1170 ring s=31991,(e,f,x,y,z,t,u,v,w,a,b,c,d),dp;
1171 ring s=31991,(x,y,z,t,u,v,w,a,b,c,d,f,e,h),dp; //standard
1172 ring s1=31991,(y,u,b,c,a,z,t,x,v,d,w,e,f,h),dp; //gut
1173v;
117413,12,11,10,8,7,6,5,4,3,2,1,9,14
1175print(matrix(sort(maxideal(1),v)));
1176f,e,w,d,x,t,z,a,c,b,u,y,v,h
1177print(matrix(maxideal(1)));
1178y,u,b,c,a,z,t,x,v,d,w,e,f,h
1179v0;
118014,9,12,11,10,8,7,6,5,4,3,2,1,13
1181print(matrix(sort(maxideal(1),v0)));
1182h,v,e,w,d,x,t,z,a,c,b,u,y,f
1183v1;v2;
11849,12,11,10,8,7,6,5,4,3,2,1,13,14
118513,12,11,10,8,7,6,5,4,3,2,1,9,14
1186
1187Ev. Gute Ordnung fuer i:
1188========================
1190mit ar=(ar1,...,ark), k=size(i)
1191    arj in K[..x^..]
1192d=deg_x(i) := max{deg_x(i[k]) | k=1..size(i)}
1194x>y  <==
1195  1. deg_x(i)>deg_y(i)
1196  2. "=" in 1. und size_x lexikographisch
1197
1198hier im Beispiel:
1199f: 5,1,0,1,2
1200
1201u: 3,1,4
1202
1203y: 3,1,3
1204b: 3,1,3
1205c: 3,1,3
1206a: 3,1,3
1207z: 3,1,3
1208t: 3,1,3
1209
1210x: 3,1,2
1211v: 3,1,2
1212d: 3,1,2
1213w: 3,1,2
1214e: 3,1,2
1215probier mal:
1216 ring s=31991,(f,u,y,z,t,a,b,c,v,w,d,e,h),dp; //standard
1217
1218*/
Note: See TracBrowser for help on using the repository browser.