Changeset 5a66d0 in git for Singular


Ignore:
Timestamp:
Apr 23, 2004, 4:14:48 PM (20 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'd08f5f0bb3329b8ca19f23b74cb1473686415c3a')
Children:
979aa58e6eda64d0f268299c491c22335ba45afd
Parents:
941bf901a04bf88f372b9d507a2d244f2733e050
Message:
*hannes: janet


git-svn-id: file:///usr/local/Singular/svn/trunk@7154 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
Singular
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/standard.lib

    r941bf9 r5a66d0  
    11//////////////////////////////////////////////////////////////////////////////
    2 version="$Id: standard.lib,v 1.64 2003-10-17 16:03:18 levandov Exp $";
     2version="$Id: standard.lib,v 1.65 2004-04-23 14:12:24 Singular Exp $";
    33category="Miscellaneous";
    44info="
    … …  
    66
    77PROCEDURES:
    8  stdjanet(ideal/module) Groebner basis using Janet basis computation
    98 stdfglm(ideal[,ord])   standard basis of ideal via fglm [and ordering ord]
    109 stdhilb(ideal[,h])     standard basis of ideal using the Hilbert function
    … …  
    1211 quot(any,any[,n])      quotient using heuristically chosen method
    1312 res(ideal/module,[i])  free resolution of ideal or module
    14  janet(ideal/module)    Janet basis of the ideal/module
    1513 sprintf(fmt,...)       returns fomatted string
    1614 fprintf(link,fmt,..)   writes formatted string to link
    … …  
    11091107   p=p^2;
    11101108   timeFactorize(p,2);
    1111    timeFactorize(p,20);
     1109   "ERROR: will not run currently:";
     1110   //timeFactorize(p,20);
    11121111}
    11131112
    … …  
    12291228  factorH(p);
    12301229}
    1231 
    1232 proc janet(def @i)
    1233 "SYNTAX: @code{janet (} ideal_expression @code{)} @*
    1234          @code{janet (} module_expression @code{)}
    1235 TYPE:    type of the first argument
    1236 PURPOSE: computes the Janet basis of the argument @code{I}
    1237          (ideal or module).
    1238 ASSUME: well-ordering on current ring. Computations with modules
    1239 are still under development
    1240 NOTE:  Janet basis is an involutive basis with respect to
    1241 the involutive Janet division. It is indeed a non-reduced Groebner basis.
    1242 SEE ALSO: stdjanet, std
    1243 KEYWORDS: involutive basis computations
    1244 EXAMPLE: example janet;  shows an example"
    1245 {
    1246   return(system("janet",@i,1));
    1247 }
    1248 example
    1249 { "EXAMPLE: "; echo=2;
    1250   ring r=0,(x,y,z),dp;
    1251   ideal i=x*y*z-1,x+y+z,x*y+x*z+y*z; // cyclic 3
    1252   janet(i);
    1253 }
    1254 //////////////////////////////////////////////////////////////////////////
    1255 
    1256 proc stdjanet(def @i)
    1257 "SYNTAX: @code{groebner (} ideal_expression @code{)} @*
    1258          @code{groebner (} module_expression @code{)}
    1259 TYPE:    type of the first argument
    1260 PURPOSE: computes the reduced Groebner basis of the argument @code{I} (ideal or module) via the computation of Janet basis and interreduction.
    1261 ASSUME: well-ordering on current ring. Computations with modules are
    1262 still under development.
    1263 NOTE: In order to compare the result with the one, produced by @code{std},
    1264 be sure that @code{option(prot)} is activated in the latter computation.
    1265 SEE ALSO: janet, std
    1266 KEYWORDS: involutive basis computations, groebner basis computations
    1267 EXAMPLE: example stdjanet;  shows an example"
    1268 {
    1269   return(system("janet",@i,0));
    1270 }
    1271 example
    1272 { "EXAMPLE: "; echo=2;
    1273   ring r=0,(x,y,z),dp;
    1274   ideal i=x*y*z-1,x+y+z,x*y+x*z+y*z; // cyclic 3
    1275   stdjanet(i);
    1276   option(redSB);
    1277   std(i);
    1278 }
    12791230//////////////////////////////////////////////////////////////////////////
    12801231

  • Singular/extra.cc

    r941bf9 r5a66d0  
    22*  Computer Algebra System SINGULAR      *
    33*****************************************/
    4 /* $Id: extra.cc,v 1.203 2004-04-03 17:25:02 levandov Exp $ */
     4/* $Id: extra.cc,v 1.204 2004-04-23 14:10:50 Singular Exp $ */
    55/*
    66* ABSTRACT: general interface to internals of Singular ("system" command)
    … …  
    592592   }
    593593   else
    594 /*==================== janet =============================*/
    595  if(strcmp(sys_cmd,"janet") == 0)
    596  {
    597    if ((h!=NULL) && ((h->Typ() == IDEAL_CMD) || (h->Typ()== MODUL_CMD)))
    598    {
    599      return jjJanetBasis(res,h);
    600    }
    601    else
    602    {
    603      WerrorS("ideal or module expected");
    604      return TRUE;
    605    }
    606  }
    607  else
    608594/*==================== spectrum =============================*/
    609595   #ifdef HAVE_SPECTRUM

  • Singular/iparith.cc

    r941bf9 r5a66d0  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: iparith.cc,v 1.316 2004-04-19 10:40:40 Singular Exp $ */
     4/* $Id: iparith.cc,v 1.317 2004-04-23 14:10:13 Singular Exp $ */
    55
    66/*
    … …  
    4545#include "algmap.h"
    4646#include "units.h"
     47#include "janet.h"
    4748#include "../kernel/GMPrat.h"
    4849#ifdef HAVE_FACTORY
    … …  
    220221  { "intvec",      0, INTVEC_CMD ,        ROOT_DECL_LIST},
    221222  { "jacob",       0, JACOB_CMD ,         CMD_1},
     223  { "janet",       0, JANET_CMD ,         CMD_12},
    222224  { "jet",         0, JET_CMD ,           CMD_M},
    223225  { "kbase",       0, KBASE_CMD ,         CMD_12},
    … …  
    18961898  setFlag(res,FLAG_STD);
    18971899  return FALSE;
     1900}
     1901static BOOLEAN jjJanetBasis2(leftv res, leftv u, leftv v)
     1902{
     1903  return jjStdJanetBasis(res,u,(int)v->Data());
    18981904}
    18991905static BOOLEAN jjJET_P(leftv res, leftv u, leftv v)
    … …  
    25752581,{jjINTERSECT, INTERSECT_CMD,  IDEAL_CMD,      IDEAL_CMD,  IDEAL_CMD ALLOW_PLURAL}
    25762582,{jjINTERSECT, INTERSECT_CMD,  MODUL_CMD,      MODUL_CMD,  MODUL_CMD ALLOW_PLURAL}
     2583,{jjJanetBasis2, JANET_CMD,    IDEAL_CMD,      IDEAL_CMD,  INT_CMD ALLOW_PLURAL}
    25772584,{jjJET_P,     JET_CMD,        POLY_CMD,       POLY_CMD,   INT_CMD ALLOW_PLURAL}
    25782585,{jjJET_ID,    JET_CMD,        IDEAL_CMD,      IDEAL_CMD,  INT_CMD ALLOW_PLURAL}
    … …  
    39363943,{jjJACOB_P,    JACOB_CMD,       IDEAL_CMD,      POLY_CMD       ALLOW_PLURAL}
    39373944,{mpJacobi,     JACOB_CMD,       MATRIX_CMD,     IDEAL_CMD      ALLOW_PLURAL}
     3945,{jjJanetBasis, JANET_CMD,       IDEAL_CMD,      IDEAL_CMD      ALLOW_PLURAL}
    39383946,{jjKBASE,      KBASE_CMD,       IDEAL_CMD,      IDEAL_CMD      ALLOW_PLURAL}
    39393947,{jjKBASE,      KBASE_CMD,       MODUL_CMD,      MODUL_CMD      ALLOW_PLURAL}
    … …  
    48644872,{jjHILBERT3,       HILBERT_CMD,INTVEC_CMD, MODUL_CMD,  INT_CMD,    INTVEC_CMD NO_PLURAL}
    48654873,{jjCALL3MANY,      IDEAL_CMD,  IDEAL_CMD,  DEF_CMD,    DEF_CMD,    DEF_CMD ALLOW_PLURAL}
     4874,{lInsert3,         INSERT_CMD, LIST_CMD,   LIST_CMD,   DEF_CMD,    INT_CMD ALLOW_PLURAL}
    48664875//,{jjCALL3MANY,      INTERSECT_CMD,  NONE,   DEF_CMD,    DEF_CMD,    DEF_CMD ALLOW_PLURAL}
    4867 ,{lInsert3,         INSERT_CMD, LIST_CMD,   LIST_CMD,   DEF_CMD,    INT_CMD ALLOW_PLURAL}
    48684876,{jjINTMAT3,        INTMAT_CMD, INTMAT_CMD, INTMAT_CMD, INT_CMD,    INT_CMD ALLOW_PLURAL}
    48694877,{jjCALL3MANY,      INTVEC_CMD, INTVEC_CMD, DEF_CMD,    DEF_CMD,    DEF_CMD ALLOW_PLURAL}

  • Singular/janet.cc

    r941bf9 r5a66d0  
     1#include <stdio.h>
     2#include <stdlib.h>
     3#include <string.h>
     4#include <time.h>
     5
    16#include "mod2.h"
    2 #include "febase.h"
    3 #include "janet.h"
     7#include <omalloc.h>
    48#include "polys.h"
    59#include "numbers.h"
    … …  
    711#include "ideals.h"
    812#include "subexpr.h"
     13#include "kbuckets.h"
    914#include "longrat.h"
     15
     16#if (defined(__CYGWIN__))
     17#include <ctype.h>
     18#endif
     19#include <stdarg.h>
     20
     21#include "febase.h"
     22#include "janet.h"
    1023#include "kutil.h"
    1124
     25//------GLOBALS-------
     26static int m_s,v_s,vectorized,VarN1,offset;
     27static jList *T,*Q;
     28static TreeM *G;
     29static Poly *phD;
     30static NodeM *FreeNodes;
     31static int degree_compatible;
     32static int (*ListGreatMove)(jList *,jList *,poly);
     33static int Mask[8]={0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};
     34
    1235//#define DebugPrint
    1336
    14 #define pow_(x) pTotaldegree((x))
    15 
    16 static int ProdCrit, ChainCrit;
     37//#define pow_(x) pTotaldegree((x))
     38//#define pow_(x) pDeg((x))
     39pFDegProc jDeg;
     40#define pow_(x) jDeg((x))
    1741
    1842void Debug()
    1943{
    20         LCI it=T->root;
    21 
    22         Print("T==================================\n");
    23         while (it)
    24         {
    25                 pWrite(it->info->root);
    26                 it=it->next;
    27         }
    28 
    29         it=Q->root;
    30 
    31         Print("Q==================================\n");
    32         while (it)
    33         {
    34                 if (it->info->root) pWrite(it->info->root);
    35                 else
    36                 {
    37                         Print("%d.........",it->info->prolonged);
    38                         pWrite(it->info->history);
    39                 }
    40                 it=it->next;
    41         }
    42         Print("===================================\n");
     44  LCI it=T->root;
     45
     46  Print("T==================================\n");
     47  while (it)
     48  {
     49    pWrite(it->info->root);
     50    it=it->next;
     51  }
     52
     53  it=Q->root;
     54
     55  Print("Q==================================\n");
     56  while (it)
     57  {
     58    if (it->info->root) pWrite(it->info->root);
     59    else
     60    {
     61      Print("%d.........",it->info->prolonged);
     62      pWrite(it->info->history);
     63    }
     64    it=it->next;
     65  }
     66  Print("===================================\n");
    4367}
    4468
    4569int ReducePolyLead(Poly *x,Poly *y)
    4670{
    47         if (!x->root || !y->root)
    48                 return 0;
    49 
    50 /*      poly b1=pDivide(x->root,y->root);
    51 
    52         number gcd=nGcd(pGetCoeff(x->root),pGetCoeff(y->root),currRing);
    53 
    54         number a1=nDiv(pGetCoeff(y->root),gcd);
    55         pGetCoeff(b1)=nDiv(pGetCoeff(x->root),gcd);
    56 
    57         x->root=pMult_nn(x->root,a1);
    58         nDelete(&a1);
    59 
    60         x->root=pMinus_mm_Mult_qq(x->root,b1,y->root);
    61 
    62         pDelete(&b1);*/
    63 
    64         x->root=ksOldSpolyRed(y->root,x->root,NULL);   
    65 
    66 //      if (x->root) pContent(x->root);
    67 
    68         return 1;
     71  if (!x->root || !y->root)
     72    return 0;
     73
     74/*  poly b1=pDivide(x->root,y->root);
     75
     76  number gcd=nGcd(pGetCoeff(x->root),pGetCoeff(y->root),currRing);
     77
     78  number a1=nDiv(pGetCoeff(y->root),gcd);
     79  pGetCoeff(b1)=nDiv(pGetCoeff(x->root),gcd);
     80
     81  x->root=pMult_nn(x->root,a1);
     82  nDelete(&a1);
     83
     84  x->root=pMinus_mm_Mult_qq(x->root,b1,y->root);
     85
     86  pDelete(&b1);
     87*/
     88#if 1
     89  if (x->root_b==NULL)
     90  {
     91    if (x->root_l<=0) x->root_l=pLength(x->root);
     92    x->root_b=kBucketCreate(currRing);
     93    kBucketInit(x->root_b,x->root,x->root_l);
     94  }
     95  number coef;
     96  if (y->root_l<=0) y->root_l=pLength(y->root);
     97  coef=kBucketPolyRed(x->root_b,y->root,y->root_l,NULL);
     98  nDelete(&coef);
     99  x->root=kBucketGetLm(x->root_b);
     100  if (x->root==NULL)
     101  {
     102    kBucketDestroy(&x->root_b);
     103    x->root_b=NULL;
     104    x->root_l=0;
     105  }
     106#else
     107  x->root=ksOldSpolyRed(y->root,x->root,NULL);
     108#endif
     109//  if (x->root) pContent(x->root);
     110//  if (x->root) pSimpleContent(x->root,5);
     111
     112  return 1;
    69113}
    70114
    71115int ReducePoly(Poly *x,poly from,Poly *y)
    72116{
    73         if (!x->root || !y->root)
    74                 return 0;
    75 
    76 /*      poly b1=pDivide(from,y->root);
    77 
    78         number gcd=nGcd(pGetCoeff(from),pGetCoeff(y->root),currRing);
    79 
    80         number a1=nDiv(pGetCoeff(y->root),gcd);
    81         pGetCoeff(b1)=nDiv(pGetCoeff(from),gcd);
    82 
    83         x->root=pMult_nn(x->root,a1);
    84         nDelete(&a1);*/
    85 
    86 //      x->root=pMinus_mm_Mult_qq(x->root,b1,y->root);
    87 //      pDelete(&b1);
    88 
    89         ksOldSpolyTail(y->root,x->root,from,NULL,currRing);
    90 
    91         return 1;
     117  if (!x->root || !y->root)
     118    return 0;
     119
     120/*  poly b1=pDivide(from,y->root);
     121
     122  number gcd=nGcd(pGetCoeff(from),pGetCoeff(y->root),currRing);
     123
     124  number a1=nDiv(pGetCoeff(y->root),gcd);
     125  pGetCoeff(b1)=nDiv(pGetCoeff(from),gcd);
     126
     127  x->root=pMult_nn(x->root,a1);
     128  nDelete(&a1);*/
     129
     130//  x->root=pMinus_mm_Mult_qq(x->root,b1,y->root);
     131//  pDelete(&b1);
     132
     133  ksOldSpolyTail(y->root,x->root,from,NULL,currRing);
     134  y->root_l=0;
     135
     136  return 1;
    92137}
    93138
    94139void PNF(Poly *p, TreeM *F)
    95140{
    96         Poly *f;
    97 
    98         if (!p->root) return;
    99 
    100         poly temp=p->root;
    101 
    102         while(temp->next)
    103         {
    104                 f=is_div_(F,temp->next);
    105                 if (f)
    106                 {
    107                         if (ReducePoly(p,temp,f)) //temp->next
    108                         {
    109                                 ;
    110                         }
    111                 }       
    112                 else
    113                         temp=temp->next;
    114         };
    115 
    116 //      pCleardenom(p->root);
    117         pContent(p->root);
    118         pTest(p->root);
     141  if (p->root==NULL) return;
     142
     143  Poly *f;
     144  BOOLEAN done=FALSE;
     145  poly temp=p->root;
     146
     147//  if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
     148  int count=0;
     149  poly pp=p->root;
     150  int old_size=nSize(pGetCoeff(pp));
     151  p->root_l=0;
     152  while(temp->next)
     153  {
     154    f=is_div_(F,temp->next);
     155    if (f)
     156    {
     157      if (ReducePoly(p,temp,f)) //temp->next
     158      {
     159        count++;
     160        //if (TEST_OPT_PROT) { PrintS("-"); mflush(); }
     161        if ((f!=NULL)
     162        && (count>20)
     163        && (nSize(pGetCoeff(pp))>old_size)
     164        )
     165        {
     166           //pSimpleContent(pp,2);
     167           pContent(pp);
     168           count=0;
     169         //  old_size=nSize(pGetCoeff(pp));
     170        }
     171      }
     172      done=TRUE;
     173    }
     174    else
     175      temp=temp->next;
     176   }
     177
     178  if (done) pContent(p->root);
     179  //if (done) pSimpleContent(p->root,-1);
     180  pTest(p->root);
    119181}
    120182
    121183void NFL(Poly *p, TreeM *F)
    122184{
    123         Poly *f;
    124         int g1,f1,gg;
    125 
    126 
    127         if ((f=is_div_(F,p->lead))==NULL) return;
    128 
    129         int pX=pow_(p->lead);
    130         int phX=pow_(p->history);
    131                
    132         if (pX!=phX)
    133         {
    134                 int phF=pow_(f->history);
    135                 if (!rIsPluralRing(currRing))
    136                 {
    137                    /* Product Criterion */
    138                   if (pX >= (phX+phF))
    139                   {
    140                     //            Print("ProdCrit Works!");
    141                     ProdCrit++;
    142                     pDelete(&p->root);
    143                     p->root=NULL;
    144                     return;
    145                   }
    146                 }
    147 
    148                 int gg=0; int i=0;
    149                 for(i=0; i<currRing->N;i++)
    150                 {
    151                   g1=pGetExp(p->history,i+1);
    152                   f1=pGetExp(f->history,i+1);
    153                   if (g1 > f1)  { gg=gg+g1; }
    154                   else { gg=gg+f1; }
    155                 }
    156                 if (pX > gg)
    157                 {                 
    158                   //              Print("ChainCrit Works!");
    159                   ChainCrit++;
    160                   pDelete(&p->root);
    161                   //x->root=NULL;
    162                   return;
    163                 }
    164                 int pF=pow_(f->lead);
    165 
    166                 if ((pX == pF) && (pF == phF))
    167                 {
    168                         pLmDelete(&f->history);
    169                         f->history=pCopy(p->history);
    170                 }
    171         }
    172 
    173         while(f && p->root)
    174         {
    175 //              Print("R");
    176                 if (ReducePolyLead(p,f) == 0) break;
    177                 if (p->root) f=is_div_(F,p->root);
    178         }
    179 
    180         if (!p->root)
    181                 return;
    182 
    183         InitHistory(p);
    184         InitProl(p);
    185         InitLead(p);
    186         p->changed=1;
    187 
    188 //      pCleardenom(p->root);
    189         pContent(p->root);
    190         pTest(p->root);
     185  Poly *f;
     186  int g1,f1,gg;
     187
     188  if ((f=is_div_(F,p->lead))==NULL) return;
     189
     190  int pX=pow_(p->lead);
     191  int phX=pow_(p->history);
     192
     193  if (pX!=phX)
     194  {
     195    int phF=pow_(f->history);
     196    if (pX >= (phX+phF))
     197    {
     198      pDelete(&p->root);
     199      //p->root=NULL;
     200      return;
     201    }
     202
     203/*    poly p2=pInit();
     204    pLcm(p->history,f->history,p2);
     205    pSetm(p2);
     206
     207    if (pLmCmp(p->root,p2) > 0)
     208    {
     209      pLmDelete(&p2);
     210      pDelete(&p->root);
     211      //p->root=NULL;
     212      return;
     213    }
     214
     215    pLmDelete(&p2);
     216*/
     217/*    for(int i=0, gg=0 ; i<currRing->N;i++)
     218      if ((g1=pGetExp(p->history,i+1)) > (f1=pGetExp(f->history,i+1)))
     219        gg+=g1;
     220      else gg+=f1;
     221
     222    if (pX > gg)
     223      {
     224        pDelete(&p->root);
     225        //x->root=NULL;
     226        return;
     227    }
     228*/
     229    int pF=pow_(f->lead);
     230
     231    if ((pX == pF) && (pF == phF))
     232    {
     233      pLmDelete(&f->history);
     234      f->history=pCopy(p->history);
     235    }
     236  }
     237
     238  //if (TEST_OPT_PROT) { PrintS("R"); mflush(); }
     239  int old_size, count;
     240  count=0;
     241  while(f && p->root)
     242  {
     243//    Print("R");
     244//    if (TEST_OPT_PROT) { PrintS("R"); mflush(); }
     245#if 0
     246    old_size=nSize(pGetCoeff(p->root));
     247#endif
     248    if (ReducePolyLead(p,f) == 0) break;
     249    if (p->root!=NULL)
     250    {
     251      count++;
     252#if 0
     253      if ((count>4) && (3<nSize(pGetCoeff(p->root)))
     254      && (nSize(pGetCoeff(p->root))>old_size))
     255      {
     256        pSimpleContent(p->root,old_size);
     257        count=0;
     258      }
     259#else
     260      if (count>500)
     261      {
     262        kBucketClear(p->root_b,&p->root,&p->root_l);
     263        pSimpleContent(p->root,2);
     264        kBucketInit(p->root_b,p->root,p->root_l);
     265        count=0;
     266        //Print(".");
     267      }
     268#endif
     269      f=is_div_(F,p->root);
     270    }
     271  }
     272#if 1
     273  if (p->root_b!=NULL)
     274  {
     275    kBucketClear(p->root_b,&p->root,&p->root_l);
     276    kBucketDestroy(&p->root_b);
     277    p->root_b=NULL;
     278  }
     279#endif
     280
     281  if (!p->root)
     282    return;
     283
     284  InitHistory(p);
     285  InitProl(p);
     286  InitLead(p);
     287  p->changed=1;
     288
     289  pContent(p->root);
     290  //pSimpleContent(p->root,-1);
     291  pTest(p->root);
    191292}
    192293
    193294int ValidatePoly(Poly *x, TreeM *F)
    194295{
    195         Poly *f,*g;
    196         int g1,f1;
    197 
    198         if (x->root) return 1;
    199  
    200         g=is_present(T,x->history); //it's a prolongation - do we have a parent ?
    201 
    202         if (!g)  return 0; //if not - kill him !
    203 
    204         poly lmX=pDivide(x->lead,g->root);
    205         pSetCoeff(lmX,nInit(1));
    206 
    207 /*      if ((f=is_div_(F,lmX)) != NULL)
    208         {
    209                 int pX=pow_(lmX);
    210                 int phX=pow_(x->history);
    211 
    212                 if (pX!=phX)
    213                 {
    214                         int phF=pow_(f->history);
    215                         if (pX >= (phX+phF))
    216                         {
    217                                 pLmDelete(&lmX);
    218                                 //x->root=NULL;
    219                                 return 0;
    220                         }
    221 
    222                         for(int i=0, gg=0 ; i<currRing->N;i++)
    223                                 if ((g1=pGetExp(x->history,i+1)) > (f1=pGetExp(f->history,i+1)))
    224                                         gg+=g1;
    225                                 else gg+=f1; 
    226 
    227                         if (pX > gg)
    228                         {
    229                                 pLmDelete(&lmX);
    230                                 //x->root=NULL;
    231                                 return 0;
    232                         }
    233                         int pF=pow_(f->root);
    234 
    235                         if ((pX == pF) && (pF == phF))
    236                                 f->history=x->history;
    237                 }
    238         }
    239 
    240         pLmDelete(&lmX);
    241 
    242 */      x->root=pCopy(g->root);
    243 
    244         x->root=pMult(lmX,x->root);
    245 
    246         pTest(x->root);
    247 
    248         x->prolonged=-1;
    249 
    250         return 1;
     296  Poly *f,*g;
     297  int g1,f1;
     298
     299  if (x->root) return 1;
     300
     301  g=is_present(T,x->history); //it's a prolongation - do we have a parent ?
     302
     303  if (!g)  return 0; //if not - kill him !
     304
     305  poly lmX=pDivide(x->lead,g->root);
     306  pGetCoeff(lmX)=nInit(1);
     307
     308/*  if ((f=is_div_(F,lmX)) != NULL)
     309  {
     310    int pX=pow_(lmX);
     311    int phX=pow_(x->history);
     312
     313    if (pX!=phX)
     314    {
     315      int phF=pow_(f->history);
     316      if (pX >= (phX+phF))
     317      {
     318        pLmDelete(&lmX);
     319        //x->root=NULL;
     320        return 0;
     321      }
     322
     323      for(int i=0, gg=0 ; i<currRing->N;i++)
     324        if ((g1=pGetExp(x->history,i+1)) > (f1=pGetExp(f->history,i+1)))
     325          gg+=g1;
     326        else
     327          gg+=f1;
     328
     329      if (pX > gg)
     330      {
     331        pLmDelete(&lmX);
     332        return 0;
     333      }
     334      int pF=pow_(f->root);
     335
     336      if ((pX == pF) && (pF == phF))
     337        f->history=x->history;
     338    }
     339  }
     340
     341  pLmDelete(&lmX);
     342
     343*/
     344  x->root=pCopy(g->root);
     345  x->root_l=g->root_l;
     346
     347  x->root=pMult(x->root,lmX);
     348
     349  pTest(x->root);
     350
     351  x->prolonged=-1;
     352
     353  return 1;
    251354}
    252355
    253356Poly *NewPoly(poly p)
    254357{
    255         Poly *beg=(Poly *)GCM(sizeof(Poly));
    256 
    257         beg->root=p;//(p == NULL ? pInit() : p);
    258         beg->history=NULL;//pInit();
    259         beg->lead=NULL;
    260         beg->mult=(char *)GCMA(sizeof(char)*2*offset);
    261 
    262         for (int i=0; i < currRing->N; i++)
    263         {
    264                 ClearMult(beg,i);
    265                 ClearProl(beg,i);
    266         };
    267 
    268         beg->prolonged=-1;
    269 
    270         return beg;
     358  Poly *beg=(Poly *)GCM(sizeof(Poly));
     359
     360  beg->root=p;//(p == NULL ? pInit() : p);
     361  beg->root_b=NULL;
     362  beg->root_l=0;
     363  beg->history=NULL;//pInit();
     364  beg->lead=NULL;
     365  beg->mult=(char *)GCMA(sizeof(char)*2*offset);
     366
     367  for (int i=0; i < currRing->N; i++)
     368  {
     369    ClearMult(beg,i);
     370    ClearProl(beg,i);
     371  };
     372
     373  beg->prolonged=-1;
     374
     375  return beg;
    271376}
    272377
    273378void DestroyPoly(Poly *x)
    274379{
    275         pDelete(&x->root);
    276         pDelete(&x->history);
    277         if (x->lead) pDelete(&x->lead);
    278         GCF(x->mult);
    279         GCF(x);
     380  pDelete(&x->root);
     381  pDelete(&x->history);
     382  if (x->lead) pDelete(&x->lead);
     383  GCF(x->mult);
     384  GCF(x);
    280385}
    281386
    282387void ControlProlong(Poly *x)
    283388{
    284         for (int i = 0; i< offset; i++)
    285         {
    286                 (x->mult+offset)[i]&=~((x->mult)[i]);
    287 //              if (!GetMult(x,i) && !GetProl(x,i))
    288 //                      ProlVar(x,i);
    289         }
     389  for (int i = 0; i< offset; i++)
     390  {
     391    (x->mult+offset)[i]&=~((x->mult)[i]);
     392//    if (!GetMult(x,i) && !GetProl(x,i))
     393//      ProlVar(x,i);
     394  }
    290395}
    291396
    292397void InitHistory(Poly *p)
    293398{
    294         if (p->history) pDelete(&p->history);
    295         p->history=pLmInit(p->root);
    296         p->changed=0;
     399  if (p->history) pLmDelete(&p->history);
     400  p->history=pLmInit(p->root);
     401  p->changed=0;
    297402}
    298403
    299404void InitLead(Poly *p)
    300405{
    301         if (p->lead) pDelete(&p->lead);
    302         p->lead=pLmInit(p->root);
    303         p->prolonged=-1;
     406  if (p->lead) pLmDelete(&p->lead);
     407  p->lead=pLmInit(p->root);
     408  p->prolonged=-1;
    304409}
    305410
    306411void InitProl(Poly *p)
    307412{
    308         memset(p->mult+offset,0,sizeof(char)*offset);
     413  memset(p->mult+offset,0,sizeof(char)*offset);
    309414}
    310415
    311416int GetMult(Poly *x,int i)
    312417{
    313         return x->mult[i/8] & Mask[i%8];
     418  return x->mult[i/8] & Mask[i%8];
    314419}
    315420
    316421void SetMult(Poly *x,int i)
    317422{
    318         x->mult[i/8] |= Mask[i%8];
     423  x->mult[i/8] |= Mask[i%8];
    319424}
    320425
    321426void ClearMult(Poly *x,int i)
    322427{
    323         x->mult[i/8] &= ~Mask[i%8];
     428  x->mult[i/8] &= ~Mask[i%8];
    324429}
    325430
    326431int GetProl(Poly *x, int i)
    327432{
    328         return (x->mult+offset)[i/8] & Mask[i%8];
     433  return (x->mult+offset)[i/8] & Mask[i%8];
    329434}
    330435
    331436void SetProl(Poly *x, int i)
    332437{
    333         (x->mult+offset)[i/8] |= Mask[i%8];
     438  (x->mult+offset)[i/8] |= Mask[i%8];
    334439}
    335440
    336441void ClearProl(Poly *x, int i)
    337442{
    338         (x->mult+offset)[i/8] &= ~Mask[i%8];
     443  (x->mult+offset)[i/8] &= ~Mask[i%8];
    339444}
    340445
    341446int LengthCompare(poly p1,poly p2)
    342447{
    343         do
    344         {
    345                 if (p1 == NULL) return 1;
    346                 if (p2 == NULL) return 0;
    347                 pIter(p1);
    348                 pIter(p2);
    349         }while(p1 && p2);
    350         return 1;
     448  do
     449  {
     450    if (p1 == NULL) return 1;
     451    if (p2 == NULL) return 0;
     452    pIter(p1);
     453    pIter(p2);
     454  }while(p1 && p2);
     455  return 1;
    351456}
    352457
    353458int ProlCompare(Poly *item1, Poly *item2)
    354459{
    355         switch(pLmCmp(item1->lead,item2->lead))
    356         {
    357                 case -1:
    358                         return 1;
    359 
    360                 case 1:
    361                         return 0;
    362 
    363                 default:
    364                         return LengthCompare(item1->root,item2->root);
    365         }
     460  switch(pLmCmp(item1->lead,item2->lead))
     461  {
     462    case -1:
     463      return 1;
     464
     465    case 1:
     466      return 0;
     467
     468    default:
     469      if ((item1->root_l<=0)||(item2->root_l<=0))
     470        return LengthCompare(item1->root,item2->root);
     471      return item1->root_l<=item2->root_l;
     472  }
    366473}
    367474
    368475void ProlVar(Poly *temp,int i)
    369476{
    370         Poly *Pr;
    371 
    372         if (!GetProl(temp,i) && !GetMult(temp,i))
    373         {
    374                 Pr=NewPoly();
    375                 SetProl(temp,i);
    376 
    377                 Pr->prolonged=i;
    378                 Pr->history=pLmInit(temp->history);
    379                 Pr->lead=pLmInit(temp->lead);
    380                 pIncrExp(Pr->lead,i+1);
    381                 pSetm(Pr->lead);
    382                 InitProl(temp);
    383 
    384                 Pr->changed=0;
    385 //              pTest(Pr->root);
    386                 InsertInCount(Q,Pr);
    387         }
     477  Poly *Pr;
     478
     479  if (!GetProl(temp,i) && !GetMult(temp,i))
     480  {
     481    Pr=NewPoly();
     482    SetProl(temp,i);
     483
     484    Pr->prolonged=i;
     485    Pr->history=pLmInit(temp->history);
     486    Pr->lead=pLmInit(temp->lead);
     487    pIncrExp(Pr->lead,i+1);
     488    pSetm(Pr->lead);
     489     InitProl(temp);
     490
     491     Pr->changed=0;
     492//    pTest(Pr->root);
     493      InsertInCount(Q,Pr);
     494   }
    388495}
    389496
    390497void DestroyListNode(ListNode *x)
    391498{
    392         DestroyPoly(x->info);
    393         GCF(x);
     499  DestroyPoly(x->info);
     500  GCF(x);
    394501}
    395502
    396503ListNode* CreateListNode(Poly *x)
    397504{
    398         ListNode* ret=(ListNode *)GCM(sizeof(ListNode));
    399         ret->info=x;
    400         ret->next=NULL;
    401         return ret;
     505  ListNode* ret=(ListNode *)GCM(sizeof(ListNode));
     506  ret->info=x;
     507  ret->next=NULL;
     508  return ret;
    402509}
    403510
    … …  
    405512Poly *FindMinList(jList *L)
    406513{
    407         LI min=&(L->root);
    408         LI l;
    409         LCI xl;
    410         Poly *x;
    411 
    412         if (degree_compatible)
    413         {
    414                 while ((*min) && ((*min)->info->root == NULL))
    415                         min=&((*min)->next);           
    416         }
    417 
    418         if (!(*min)) return NULL;
    419 
    420         l=&((*min)->next);
    421  
    422         while (*l)
    423         {
    424                 if ((*l)->info->root != NULL)
    425                 {
    426                         if (ProlCompare((*l)->info,(*min)->info))
    427                                 min=l;
    428                 }
    429                
    430                 l=&((*l)->next);
    431         }
    432         x=(*min)->info;
    433         xl=*min;
    434         *min=(*min)->next;
    435         GCF(xl);
    436  
    437         return x;
     514  LI min=&(L->root);
     515  LI l;
     516  LCI xl;
     517  Poly *x;
     518
     519  if (degree_compatible)
     520  {
     521    while ((*min) && ((*min)->info->root == NULL))
     522      min=&((*min)->next);
     523  }
     524
     525  if (!(*min)) return NULL;
     526
     527  l=&((*min)->next);
     528
     529  while (*l)
     530  {
     531    if ((*l)->info->root != NULL)
     532    {
     533      if (ProlCompare((*l)->info,(*min)->info))
     534        min=l;
     535    }
     536
     537    l=&((*l)->next);
     538  }
     539  x=(*min)->info;
     540  xl=*min;
     541  *min=(*min)->next;
     542  GCF(xl);
     543
     544  return x;
    438545}
    439546
    440547void InsertInList(jList *x,Poly *y)
    441548{
    442         ListNode *ins;
    443         LI ix=&(x->root);
    444 
    445         while (*ix)
    446         {
    447                 if (pLmCmp(y->lead,(*ix)->info->lead) == -1)
    448                         ix=(ListNode **)&((*ix)->next);
    449                 else
    450                         break;
    451         }
    452 
    453         ins=CreateListNode(y);
    454         ins->next=(ListNode *)(*ix);
    455         *ix=ins;
    456         return;
     549  ListNode *ins;
     550  LI ix=&(x->root);
     551
     552  while (*ix)
     553  {
     554    if (pLmCmp(y->lead,(*ix)->info->lead) == -1)
     555      ix=(ListNode **)&((*ix)->next);
     556    else
     557      break;
     558  }
     559
     560  ins=CreateListNode(y);
     561  ins->next=(ListNode *)(*ix);
     562  *ix=ins;
     563  return;
    457564}
    458565
    459566void InsertInCount(jList *x,Poly *y)
    460567{
    461         ListNode *ins;
    462         LI ix=&(x->root);
    463  
    464         ins=CreateListNode(y);
    465         ins->next=(ListNode *)(*ix);
    466         *ix=ins;
    467         return;
     568  ListNode *ins;
     569  LI ix=&(x->root);
     570
     571  ins=CreateListNode(y);
     572  ins->next=(ListNode *)(*ix);
     573  *ix=ins;
     574  return;
    468575}
    469576
    470577int ListGreatMoveOrder(jList *A,jList *B,poly x)
    471578{
    472         LCI y=A->root;
    473 
    474         if (!y || pLmCmp(y->info->lead,x) < 0) return 0;
    475 
    476         while(y && pLmCmp(y->info->lead,x) >= 0)
    477         {
    478                 InsertInCount(B,y->info);
    479                 A->root=y->next;
    480                 GCF(y);
    481                 y=A->root;
    482         }
    483  
    484         return 1;
     579  LCI y=A->root;
     580
     581  if (!y || pLmCmp(y->info->lead,x) < 0) return 0;
     582
     583  while(y && pLmCmp(y->info->lead,x) >= 0)
     584  {
     585    InsertInCount(B,y->info);
     586    A->root=y->next;
     587    GCF(y);
     588    y=A->root;
     589  }
     590
     591  return 1;
    485592}
    486593
    487594int ListGreatMoveDegree(jList *A,jList *B,poly x)
    488595{
    489         LCI y=A->root;
    490         int pow_x=pow_(x);
    491 
    492         if (!y || pow_(y->info->lead) <= pow_x) return 0;
    493 
    494         while(y && pow_(y->info->lead) > pow_x)
    495         {
    496                 InsertInCount(B,y->info);
    497                 A->root=y->next;
    498                 GCF(y);
    499                 y=A->root;
    500         }
    501  
    502         return 1;
     596  LCI y=A->root;
     597  int pow_x=pow_(x);
     598
     599  if (!y || pow_(y->info->lead) <= pow_x) return 0;
     600
     601  while(y && pow_(y->info->lead) > pow_x)
     602  {
     603    InsertInCount(B,y->info);
     604    A->root=y->next;
     605    GCF(y);
     606    y=A->root;
     607  }
     608
     609  return 1;
    503610}
    504611
    505612int CountList(jList *Q)
    506613{
    507         int i=0;
    508         LCI y=Q->root;
    509  
    510         while(y)
    511         {
    512                 i++;
    513                 y=y->next;
    514         }
    515  
    516         return i;
     614  int i=0;
     615  LCI y=Q->root;
     616
     617  while(y)
     618  {
     619    i++;
     620    y=y->next;
     621  }
     622
     623  return i;
    517624}
    518625
    519626void NFListQ()
    520627{
    521         LCI ll;
    522         int p,p1;
    523         LI l;
    524  
    525         do
    526         {
    527                 if (!Q->root) break;
    528 
    529                 ll=Q->root;
    530  
    531                 p=pow_(Q->root->info->lead);
    532  
    533                 while (ll)
    534                 {
    535                         int ploc=pow_(ll->info->lead);
    536                         if (ploc < p) p=ploc;
    537                         ll=ll->next;
    538                 }
    539  
    540                 p1=1;
    541 
    542                 l=&(Q->root);
    543  
    544                 while (*l)
    545                 { 
    546 //                      Print("*");
    547                         int ploc=pow_((*l)->info->lead);
    548 
    549                         if (ploc == p)
    550                         {
    551                                 if (!ValidatePoly((*l)->info,G))
    552                                 {
    553                                         ll=(*l);
    554                                         *l=(*l)->next;
    555                                         DestroyListNode(ll);
    556                                         continue;
    557                                 };
    558 
    559                                 (*l)->info->changed=0;
    560 //                              Print("!");
    561                                 NFL((*l)->info,G);
     628  LCI ll;
     629  int p,p1;
     630  LI l;
     631
     632  do
     633  {
     634    if (!Q->root) break;
     635
     636    ll=Q->root;
     637
     638    p=pow_(Q->root->info->lead);
     639
     640    while (ll)
     641    {
     642      int ploc=pow_(ll->info->lead);
     643      if (ploc < p) p=ploc;
     644      ll=ll->next;
     645    }
     646
     647    p1=1;
     648
     649    l=&(Q->root);
     650
     651    while (*l)
     652    {
     653//      Print("*");
     654      int ploc=pow_((*l)->info->lead);
     655
     656      if (ploc == p)
     657      {
     658        if (!ValidatePoly((*l)->info,G))
     659        {
     660          ll=(*l);
     661          *l=(*l)->next;
     662          DestroyListNode(ll);
     663          continue;
     664        };
     665
     666        (*l)->info->changed=0;
     667//        Print("!");
     668        NFL((*l)->info,G);
    562669//                                Print("$");
    563                                 if (!(*l)->info->root)
    564                                 {
    565                                         ll=(*l);
    566                                         *l=(*l)->next;
    567                                         DestroyListNode(ll);
    568                                         continue;
    569                                 };
    570                                 p1=0;
    571                         }
    572 
    573                         l=&((*l)->next);
    574                 }
    575         }while(p1);
    576 //      Print("\n");
     670        if (!(*l)->info->root)
     671        {
     672          ll=(*l);
     673          *l=(*l)->next;
     674          DestroyListNode(ll);
     675          continue;
     676        };
     677        p1=0;
     678      }
     679
     680      l=&((*l)->next);
     681    }
     682  }while(p1);
     683//  Print("\n");
    577684}
    578685
    … …  
    580687void ForEachPNF(jList *x,int i)
    581688{
    582         LCI y=x->root;
    583 
    584         while(y)
    585         {
    586                 if (pow_(y->info->root) == i) PNF(y->info,G);
    587                 y=y->next;
    588         }
     689  LCI y=x->root;
     690
     691  while(y)
     692  {
     693    if (pow_(y->info->root) == i) PNF(y->info,G);
     694    y=y->next;
     695  }
    589696}
    590697
    591698void ForEachControlProlong(jList *x)
    592699{
    593         LCI y=x->root;
    594 
    595         while(y)
    596         {
    597                 ControlProlong(y->info);
    598                 y=y->next;
    599         }
     700  LCI y=x->root;
     701
     702  while(y)
     703  {
     704    ControlProlong(y->info);
     705    y=y->next;
     706  }
    600707}
    601708
    602709void DestroyList(jList *x)
    603710{
    604         LCI y=x->root,z;
    605 
    606         while(y)
    607         {
    608                 z=y->next;
    609                 DestroyPoly(y->info);
    610                 GCF(y);
    611                 y=z;
    612         }
    613 
    614         GCF(x);
     711  LCI y=x->root,z;
     712
     713  while(y)
     714  {
     715    z=y->next;
     716    DestroyPoly(y->info);
     717    GCF(y);
     718    y=z;
     719  }
     720
     721  GCF(x);
    615722}
    616723
    617724Poly* is_present(jList *F,poly x)
    618725{
    619         LCI iF=F->root;
    620         while(iF)
    621                 if (pLmCmp(iF->info->root,x) == 0)
    622                         return iF->info;
    623                 else iF=iF->next;
    624 
    625         return NULL;
     726  LCI iF=F->root;
     727  while(iF)
     728    if (pLmCmp(iF->info->root,x) == 0)
     729      return iF->info;
     730    else iF=iF->next;
     731
     732  return NULL;
    626733}
    627734
    628735int GB_length()
    629736{
    630         LCI iT=T->root;
    631         int l=0;
    632  
    633         while(iT)
    634         {
    635                 if (pow_(iT->info->lead) == pow_(iT->info->history))
    636                         ++l;
    637                 iT=iT->next;
    638         }
    639        
    640         return l;
     737  LCI iT=T->root;
     738  int l=0;
     739
     740  while(iT)
     741  {
     742    if (pow_(iT->info->lead) == pow_(iT->info->history))
     743      ++l;
     744    iT=iT->next;
     745  }
     746
     747  return l;
    641748}
    642749
    … …  
    645752NodeM* create()
    646753{
    647         NodeM *y;
    648 
    649         if (FreeNodes == NULL)
    650         {
    651                 y=(NodeM *)GCM(sizeof(NodeM));
    652         }
    653         else
    654         {
    655                 y=FreeNodes;
    656                 FreeNodes=FreeNodes->left;
    657         }
    658        
    659         y->left=y->right=NULL;
    660         y->ended=NULL;
    661         return y;
     754  NodeM *y;
     755
     756  if (FreeNodes == NULL)
     757  {
     758    y=(NodeM *)GCM(sizeof(NodeM));
     759  }
     760  else
     761  {
     762    y=FreeNodes;
     763    FreeNodes=FreeNodes->left;
     764  }
     765
     766  y->left=y->right=NULL;
     767  y->ended=NULL;
     768  return y;
    662769}
    663770
    664771void DestroyFreeNodes()
    665772{
    666         NodeM *y;
    667    
    668         while((y=FreeNodes)!=NULL)
    669         {
    670                 FreeNodes=FreeNodes->left;
    671                 GCF(y);
    672         }
     773  NodeM *y;
     774
     775  while((y=FreeNodes)!=NULL)
     776  {
     777    FreeNodes=FreeNodes->left;
     778    GCF(y);
     779  }
    673780}
    674781
    675782static void go_right(NodeM *current,poly_function disp)
    676783{
    677         if (current)
    678         {
    679                 go_right(current->left,disp);
    680                 if (current->ended) disp(current->ended);
    681                 go_right(current->right,disp);
    682         }
     784  if (current)
     785  {
     786    go_right(current->left,disp);
     787    if (current->ended) disp(current->ended);
     788    go_right(current->right,disp);
     789  }
    683790}
    684791
    685792void ForEach(TreeM *t,poly_function disp)
    686793{
    687         go_right(t->root,disp);
     794  go_right(t->root,disp);
    688795}
    689796
    690797void DestroyTree(NodeM *G)
    691798{
    692         if (G)
    693         {
    694                 DestroyTree(G->left);
    695                 DestroyTree(G->right);
    696                 G->left=FreeNodes;
    697                 FreeNodes=G;
    698         }
     799  if (G)
     800  {
     801    DestroyTree(G->left);
     802    DestroyTree(G->right);
     803    G->left=FreeNodes;
     804    FreeNodes=G;
     805  }
    699806}
    700807
    701808void Define(TreeM **G)
    702809{
    703         *G=(TreeM *)GCM(sizeof(TreeM));
    704         (*G)->root=create();
     810  *G=(TreeM *)GCM(sizeof(TreeM));
     811  (*G)->root=create();
    705812}
    706813
    … …  
    708815{
    709816
    710         if (pow_(m2) == 0 && pow_(m1)) return 0;
    711 
    712         for(int k=from; k < currRing->N; k++)
    713                 if (pGetExp(m1,k+1) < pGetExp(m2,k+1)) return 0;
    714 
    715         return 1;
     817  if (pow_(m2) == 0 && pow_(m1)) return 0;
     818
     819  for(int k=from; k < currRing->N; k++)
     820    if (pGetExp(m1,k+1) < pGetExp(m2,k+1)) return 0;
     821
     822  return 1;
    716823}
    717824
    718825void div_l(poly item, NodeM *x,int from)
    719826{
    720         if (x && !temp_l)
    721         { 
    722                 div_l(item,x->left,from);
    723                 if ((x->ended) && sp_div(item,x->ended->root,from))
    724                 {
    725                         temp_l=x->ended;
    726                         return;
    727                 };
    728                 div_l(item,x->right,from);
    729         }
     827  if (x && !temp_l)
     828  {
     829    div_l(item,x->left,from);
     830    if ((x->ended) && sp_div(item,x->ended->root,from))
     831    {
     832      temp_l=x->ended;
     833      return;
     834    };
     835    div_l(item,x->right,from);
     836  }
    730837}
    731838
    732839Poly* is_div_upper(poly item, NodeM *x,int from)
    733840{
    734         temp_l=NULL;
    735         div_l(item,x,from);
    736         return temp_l;
     841  temp_l=NULL;
     842  div_l(item,x,from);
     843  return temp_l;
    737844}
    738845
    739846Poly* is_div_(TreeM *tree, poly item)
    740847{
    741         int power_tmp,i,i_con=currRing->N-1;
    742         NodeM *curr=tree->root;
    743 
    744         if (!curr) return NULL;
    745         if (pow_(item) == 0) return NULL;
    746 
    747         for ( ; i_con>=0 && !pGetExp(item,i_con+1) ; i_con--)
    748                 ;
    749 
    750         for (i=0; i <= i_con ; i++)
    751         {
    752                 power_tmp=pGetExp(item,i+1);
    753 
    754                 while (power_tmp)
    755                 {
    756                         if (curr->ended) return curr->ended;
    757 
    758                         if (!curr->left)
    759                         {
    760                                 if (curr->right)
    761                                         return is_div_upper(item,curr->right,i); //??????
    762                                 return NULL;
    763                         };
    764      
    765                         curr=curr->left;
    766                         power_tmp--;
    767                 };
    768 
    769                 if (curr->ended) return curr->ended;
    770 
    771                 if (!curr->right) return NULL;
    772 
    773                 curr=curr->right;
    774         }
    775 
    776         if (curr->ended) return curr->ended;
    777         else return NULL;
     848  int power_tmp,i,i_con=currRing->N-1;
     849  NodeM *curr=tree->root;
     850
     851  if (!curr) return NULL;
     852  if (pow_(item) == 0) return NULL;
     853
     854  for ( ; i_con>=0 && !pGetExp(item,i_con+1) ; i_con--)
     855    ;
     856
     857  for (i=0; i <= i_con ; i++)
     858  {
     859    power_tmp=pGetExp(item,i+1);
     860
     861    while (power_tmp)
     862    {
     863      if (curr->ended) return curr->ended;
     864
     865      if (!curr->left)
     866      {
     867        if (curr->right)
     868          return is_div_upper(item,curr->right,i); //??????
     869        return NULL;
     870      }
     871
     872      curr=curr->left;
     873      power_tmp--;
     874    }
     875
     876    if (curr->ended) return curr->ended;
     877
     878    if (!curr->right) return NULL;
     879
     880    curr=curr->right;
     881  }
     882
     883  if (curr->ended) return curr->ended;
     884  else return NULL;
    778885}
    779886
    780887static void ClearMultiplicative(NodeM *xx,int i)
    781888{
    782         if (!xx) return;
    783  
    784         while (xx->left)
    785         {
    786                 ClearMultiplicative(xx->right, i);
    787                 xx = xx->left;
    788         }
    789         if ((xx->ended) && (GetMult(xx->ended,i)))
    790         {
    791                 ClearMult(xx->ended,i);
    792                 ProlVar(xx->ended,i);
    793         }
    794         else
    795                 ClearMultiplicative(xx->right,i);
     889  if (!xx) return;
     890
     891  while (xx->left)
     892  {
     893    ClearMultiplicative(xx->right, i);
     894    xx = xx->left;
     895  }
     896  if ((xx->ended) && (GetMult(xx->ended,i)))
     897  {
     898    ClearMult(xx->ended,i);
     899    ProlVar(xx->ended,i);
     900  }
     901  else
     902    ClearMultiplicative(xx->right,i);
    796903}
    797904//======================================================
    … …  
    800907 int power_tmp,i,i_con=currRing->N-1;
    801908 NodeM *curr=(*tree)->root;
    802  
     909
    803910 for ( ; (i_con>=0) && !pGetExp(item->root,i_con+1) ; i_con--)
    804911  SetMult(item,i_con);
    805  
     912
    806913 for (i = 0; i<= i_con; i++)
    807914 //<=
    … …  
    814921  {
    815922   if (!curr->left)
    816    {   
     923   {
    817924     SetMult(item,i);
    818925     ClearMultiplicative(curr->right,i);
    … …  
    838945void Initialization(char *Ord)
    839946{
    840   ProdCrit=0;
    841   ChainCrit=0;
    842947  offset=(currRing->N % 8 == 0) ? (currRing->N/8)*8 : (currRing->N/8+1)*8;
    843948  if (strstr(Ord,"dp\0") || strstr(Ord,"Dp\0"))
    844949  {
    845950    degree_compatible=1;
     951    jDeg=pDeg;
    846952    ListGreatMove=ListGreatMoveDegree;
    847953  }
    … …  
    849955  {
    850956    degree_compatible=0;
     957    jDeg=pTotaldegree;
    851958    ListGreatMove=ListGreatMoveOrder;
    852959  }
    853  
     960
    854961  Define(&G);
    855962};
    … …  
    866973void Q2TG()
    867974{
    868         LCI t;
    869         Poly *x;
    870 
    871         while (Q->root)
     975  LCI t;
     976  Poly *x;
     977
     978  while (Q->root)
     979  {
     980    t=Q->root;
     981    x=t->info;
     982    insert_(&G,x);
     983    InsertInList(T,x);
     984    Q->root=t->next;
     985    GCF(t);
     986  }
     987}
     988
     989int ComputeBasis(jList *_T,jList *_Q)
     990{
     991  int gb_l,i,ret_value=1;
     992
     993  T=_T; Q=_Q;
     994
     995//  Debug();
     996
     997  while((h=FindMinList(Q))!=NULL)
     998  {
     999//        Print("New element\n");
     1000//  Debug();
     1001
     1002        if (!degree_compatible)
    8721003        {
    873                 t=Q->root;
    874                 x=t->info;
    875                 insert_(&G,x);
    876                 InsertInList(T,x);
    877                 Q->root=t->next;
    878                 GCF(t);
     1004          if (!ValidatePoly(h,G))
     1005          {
     1006            DestroyPoly(h);
     1007            continue;
     1008          }
     1009
     1010          h->changed=0;
     1011
     1012          NFL(h,G);
     1013
     1014          if (!h->root)
     1015          {
     1016            DestroyPoly(h);
     1017            continue;
     1018          }
    8791019        }
    880 }
    881 
    882 int ComputeBasis(jList *_T, jList *_Q)
    883 {
    884   int gb_l,i,ret_value=1;
    885 
    886   T=_T; Q=_Q;
    887 
    888   //  Debug();
    889 
    890   while( (h=FindMinList(Q)) != NULL )
    891   {
    892  
    893     //  Print("New element\n");
    894     //  Debug();
    895 
    896     if (!degree_compatible)
    897     {
    898       if (!ValidatePoly(h,G))
    899       {
    900         DestroyPoly(h);
    901         continue;
    902       };
    903      
    904       h->changed=0;
    905      
    906       NFL(h,G);
    907      
    908       if (!h->root)
    909       {
    910         DestroyPoly(h);
    911         continue;
    912       };
    913     }
    914 
    915     if (h->root)
    916     {
    917       if (pIsConstant(h->root))
    918       {
    919         // WarnS("Constant in basis\n");
    920         return 0;
    921       }
    922      
    923       if (h->changed && ListGreatMove(T,Q,h->root))
    924       {
    925         // Print("<-\n");
    926         DestroyTree(G->root);
    927         G->root=create();
    928         T2G();
    929       }
    930     }
    931    
    932     //  Print("PNF\n");
    933     PNF(h,G);
    934     if (TEST_OPT_PROT)
    935     {
    936       Print("s%d",pow_(h->root));
    937     }
    938     insert_(&G,h);
    939     InsertInList(T,h);
    940    
    941     //  Print("For each PNF\n");
    942     if (degree_compatible)
    943       ForEachPNF(T,pow_(h->root));
    944    
    945     //  Print("Control of prolongations\n");
    946     if (h->changed)
    947       ForEachControlProlong(T);
    948     else
    949       ControlProlong(h);
    950    
    951     //  Debug();
    952    
    953     //  Print("NFListQ\n");
    954     if (degree_compatible)
    955       NFListQ();
    956     //Debug();
    957   }
    958  
    959   //    gb_l=GB_length();
    960  
    961   if (TEST_OPT_PROT)
    962   {
    963     Print("\nLength of Janet basis: %d", CountList(T));
    964     Print("\nproduct criterion:%d chain criterion:%d\n", ProdCrit, ChainCrit);
    965     //    Print("Length of Groebner basis:    %d\n",gb_l);
    966   }
    967  
    968   DestroyTree(G->root);
    969   GCF(G);
    970   DestroyFreeNodes();
    971  
    972   return 1;
     1020
     1021        if (h->root)
     1022        {
     1023          if (pIsConstant(h->root))
     1024          {
     1025            WarnS("Constant in basis\n");
     1026            return 0;
     1027          }
     1028
     1029          if (h->changed && ListGreatMove(T,Q,h->root))
     1030          {
     1031//      Print("<-\n");
     1032            DestroyTree(G->root);
     1033            G->root=create();
     1034            T2G();
     1035          }
     1036        }
     1037
     1038//  Print("PNF\n");
     1039        PNF(h,G);
     1040//        Print("{%d}\n",pow_(h->root));
     1041        insert_(&G,h);
     1042        InsertInList(T,h);
     1043
     1044//  Print("For each PNF\n");
     1045        if (degree_compatible)
     1046            ForEachPNF(T,pow_(h->root));
     1047
     1048//  Print("Control of prolongations\n");
     1049        if (h->changed)
     1050            ForEachControlProlong(T);
     1051        else
     1052            ControlProlong(h);
     1053
     1054//  Debug();
     1055
     1056//  Print("NFListQ\n");
     1057        if (degree_compatible)
     1058            NFListQ();
     1059//Debug();
     1060    }
     1061
     1062//    gb_l=GB_length();
     1063
     1064    Print("Length of Janet basis: %d\n",CountList(T));
     1065//    Print("Length of Groebner basis:    %d\n",gb_l);
     1066
     1067    DestroyTree(G->root);
     1068    GCF(G);
     1069    DestroyFreeNodes();
     1070
     1071    return 1;
    9731072}
    9741073

  • Singular/janet.h

    r941bf9 r5a66d0  
    22#define __JANET_INTERFACE__
    33
    4 #include "febase.h"
    5 #include "polys.h"
    6 #include "numbers.h"
    7 #include "ring.h"
    8 #include "ideals.h"
    9 #include "subexpr.h"
    10 #include "longrat.h"
    11 
    12 #include <stdio.h>
    13 #include <stdlib.h>
    14 #include <string.h>
    15 #include <time.h>
    16 #include <omalloc.h>
     4#include "structs.h"
    175
    186#define GCM(sz) omAlloc((sz))
    197#define GCMA(sz) omAlloc((sz))
    20 #define GCR(x,y) omRealloc((x),(y))
    218#define GCF(x) omFree((x))
    22 
    23 #if (defined(__CYGWIN__))
    24 #include <ctype.h>
    25 #endif
    26 #include <stdarg.h>
    279
    2810#define ListNode struct LISTNODE
    … …  
    3012#define NodeM struct NODEM
    3113
    32 static int Mask[8]={0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};
    33 
    3414typedef struct
    3515{
    36         poly root; //poly for parent, NULL for prol
    37         poly history; //parent
    38         poly lead; //leading monomial for prolongation
    39         char *mult; //[multi].[prol]
    40         int changed;
    41         int prolonged; //number of prolonged variable for prolongation, otherwise = -1;
     16  poly root; //poly for parent, NULL for prol
     17  kBucket_pt root_b;
     18  int root_l;
     19  poly history; //parent
     20  poly lead; //leading monomial for prolongation
     21  char *mult; //[multi].[prol]
     22  int changed;
     23  int prolonged; //number of prolonged variable for prolongation, otherwise = -1;
    4224} Poly;
    4325
    … …  
    6951typedef ListNode** LI;
    7052
    71 //------GLOBALS-------
    72 static int m_s,v_s,vectorized,VarN1,offset;
    73 static jList *T,*Q;
    74 
    75 static TreeM *G;
    76 
    77 static Poly *phD;
    78 static NodeM *FreeNodes;
    79 
    8053//-------FUNCS----------
    8154Poly* FindMinList(jList *);
    … …  
    8861Poly* NewPoly(poly p=NULL);
    8962void DestroyPoly();
    90 
    91 static int degree_compatible;
    9263
    9364void NFL(Poly *,TreeM *);
    … …  
    11182int ProlCompare(Poly *, Poly *);
    11283int ValidatePoly(Poly *,TreeM *);
    113 static int (*ListGreatMove)(jList *,jList *,poly);
    11484int ListGreatMoveDegree(jList *,jList *,poly);
    11585int ListGreatMoveOrder(jList *,jList *,poly);
    … …  
    12595void DestroyListNode(ListNode *x);
    12696void DestroyFreeNodes();
     97
    12798BOOLEAN jjJanetBasis(leftv res, leftv v);
     99BOOLEAN jjStdJanetBasis(leftv res, leftv v,int flag); // 0: JB, 1: SB
     100
    128101#endif //JANET_INTERFACE

  • Singular/wrapper.cc

    r941bf9 r5a66d0  
     1#include <string.h>
    12#include "mod2.h"
     3#include "febase.h"
     4#include "polys.h"
     5#include "kstd1.h"
     6#include "subexpr.h"
     7#include "ideals.h"
     8#include "ring.h"
    29#include "janet.h"
    3 #include "kstd1.h"
    4 #include "ipid.h"
    510
    611#define pow_(x) pTotaldegree((x))
    … …  
    1015extern void Initialization(char *);
    1116
     17BOOLEAN jInitBasis(ideal v, jList **TT,jList **QQ)
     18{
     19  if (pOrdSgn==-1)
     20  {
     21    WerrorS("janet only for well-orderings");
     22    return TRUE;
     23  }
     24
     25  Initialization(rOrdStr(currRing));
     26
     27  jList *Q=(jList *)GCM(sizeof(jList));
     28  Q->root=NULL;
     29
     30  jList *T=(jList *)GCM(sizeof(jList));
     31  T->root=NULL;
     32
     33  for (int i=0; i < v->idelems(); i++)
     34  {
     35    if (v->m[i]!=NULL)
     36    {
     37      Poly *beg=NewPoly(pCopy(v->m[i]));
     38
     39      InitHistory(beg);
     40      InitProl(beg);
     41      InitLead(beg);
     42
     43      InsertInCount(Q,beg);
     44    }
     45  }
     46
     47  BOOLEAN r= !(ComputeBasis(T,Q));
     48  *TT=T;
     49  *QQ=Q;
     50  return r;
     51}
     52
     53BOOLEAN jjStdJanetBasis(leftv res, leftv v, int flag)
     54{
     55  ideal result;
     56  int dpO;
     57
     58  jList *T;
     59  jList *Q;
     60  ideal I=(ideal)v->Data();
     61  BOOLEAN is_zero=TRUE;
     62  for (int i=0; i < I->idelems(); i++)
     63  {
     64    if ((I->m[i]!=NULL)&& (pIsConstant(I->m[i])))
     65    {
     66      goto zero;
     67    }
     68    else
     69     is_zero=FALSE;
     70  }
     71  if (is_zero)
     72    goto zero;
     73  if (!jInitBasis(I,&T,&Q))
     74  {
     75    dpO=(strstr(rOrdStr(currRing),"dp")!=NULL);
     76    int ideal_length;
     77    if (flag==1)
     78      ideal_length= dpO ? GB_length() : CountList(T);
     79    else
     80      ideal_length=CountList(T);
     81
     82    result=idInit(ideal_length,1);
     83
     84    int ideal_index=0;
     85
     86    LCI iT=T->root;
     87
     88    while(iT)
     89    {
     90      pTest(iT->info->root);
     91      if ((flag==1) && dpO)
     92      {
     93        //if (pow_(iT->info->lead) == pow_(iT->info->history))
     94        if (pDeg(iT->info->lead) == pDeg(iT->info->history))
     95        {
     96          result->m[ideal_length-ideal_index-1]=pCopy(iT->info->root);
     97          if (!nGreaterZero(pGetCoeff(iT->info->root)))
     98            result->m[ideal_length-ideal_index-1]
     99                                  =pNeg(result->m[ideal_length-ideal_index-1]);
     100
     101          ideal_index++;
     102        }
     103      }
     104      else
     105      {
     106        result->m[ideal_length-ideal_index-1]=pCopy(iT->info->root);
     107        if (!nGreaterZero(pGetCoeff(iT->info->root)))
     108          result->m[ideal_length-ideal_index-1]
     109                                  =pNeg(result->m[ideal_length-ideal_index-1]);
     110
     111        ideal_index++;
     112      }
     113      iT=iT->next;
     114    }
     115  }
     116
     117  if ((flag==1) && (!dpO))
     118  {
     119    //Print ("interred\n");
     120    result=kInterRed(result);
     121    idSkipZeroes(result);
     122  }
     123  res->data = (char *)result;
     124  res->rtyp = IDEAL_CMD;
     125
     126  DestroyList(Q);
     127  DestroyList(T);
     128
     129  return FALSE;
     130
     131zero:
     132  result=idInit(1,1);
     133  if (!is_zero) result->m[0]=pOne();
     134  res->data = (char *)result;
     135  res->rtyp = IDEAL_CMD;
     136  return FALSE;
     137}
     138
    12139BOOLEAN jjJanetBasis(leftv res, leftv v)
    13140{
    14         Initialization(rOrdStr(currRing));
    15 
    16           jList *Q=(jList *)GCM(sizeof(jList));
    17         Q->root=NULL;
    18                
    19         jList *T=(jList *)GCM(sizeof(jList));
    20         T->root=NULL;
    21 
    22         ideal input = (ideal)(v->Data());
    23         /* the second arg is an integer, defining what to return:
    24          0 (default case) = Groebner basis,
    25          1                = Janet basis.
    26         */
    27         int doJanet;
    28         if ((v->next!=NULL) && (v->next->Typ() == INT_CMD))
    29         {
    30           doJanet = (int)v->next->CopyD();
    31           //          Print("doJanet:%d\n",doJanet);
    32         }               
    33         else
    34         {
    35           doJanet = 0;
    36         }
    37         ideal result;
    38         int dpO = !doJanet; /* compatibility */
    39 
    40         for (int i=0; i < input->idelems(); i++)       
    41         {
    42           /* nonzero constant check */
    43           if (pIsConstant(input->m[i])) { goto zero; }
    44           Poly *beg=NewPoly(pCopy(input->m[i]));
    45           InitHistory(beg);
    46           InitProl(beg);
    47           InitLead(beg);
    48           InsertInCount(Q,beg);
    49         }
    50 
    51         if (ComputeBasis(T,Q))
    52         {
    53           //                dpO=(strstr(rOrdStr(currRing),"dp")!=NULL);
    54           int ideal_length= dpO ? GB_length() : CountList(T);
    55           result=idInit(ideal_length,1);
    56           int ideal_index=0;
    57          
    58           LCI iT=T->root;
    59          
    60           while (iT)
    61           {
    62 #ifdef PDEBUG                 
    63             pTest(iT->info->root);
    64 #endif
    65             if (!(dpO && (pow_(iT->info->lead) != pow_(iT->info->history))))
    66             {
    67               result->m[ideal_length-ideal_index-1]=pCopy(iT->info->root);
    68               if (!nGreaterZero(pGetCoeff(iT->info->root)))
    69               {
    70                 result->m[ideal_length-ideal_index-1]=pNeg(result->m[ideal_length-ideal_index-1]);
    71               }
    72               ideal_index++;
    73             }   
    74             iT=iT->next;
    75           }
    76         }
    77         else
    78         {
    79 zero:
    80           result=idInit(1,1);
    81           result->m[0]=pOne();       
    82         }
    83        
    84         /* now we make the basis shorter... getting Groebner */
    85         if (!doJanet) /* if (!dpO) */
    86         {
    87           if (TEST_OPT_PROT)
    88           {
    89             Print ("interred\n");
    90           }
    91           result=kInterRed(result);
    92           idSkipZeroes(result);
    93         }
    94         res->data = (char *)result;
    95         res->rtyp = v->Typ();
    96         if (!doJanet) setFlag(res,FLAG_STD);
    97 
    98         DestroyList(Q);
    99         DestroyList(T);
    100        
    101         return FALSE;
     141  return jjStdJanetBasis(res,v,0);
    102142}
Note: See TracChangeset for help on using the changeset viewer.