Changeset cce6ed3 in git


Ignore:
Timestamp:
Jan 25, 2009, 6:13:06 PM (14 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
f4e338f564fc725c8dac99c44cbf3f5ec5ceacb2
Parents:
0883ed62762dee5f6c5fa37f064d3883b99dc21f
Message:
lists done, started implementing f5incremental and critpair subalgorithms


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

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    r0883ed rcce6ed3  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.cc,v 1.16 2009-01-15 17:44:23 ederc Exp $ */
     4/* $Id: f5gb.cc,v 1.17 2009-01-25 17:13:05 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    6767==================================================
    6868*/
    69 LList* F5inc(int* i, poly* f_i, LList* g_prev, poly* ONE) {
    70     LList* g_curr       =   g_prev;
    71     g_curr->insert(ONE,i,f_i);
    72    
    73     return g_curr;
     69LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE) {
     70    gPrev->insert(ONE,i,f_i);
     71    CList* critPairs    =   criticalPair(gPrev);
     72     
     73    return gPrev;
     74}
     75
     76
     77/*
     78================================================================
     79computes a list of critical pairs for the next reduction process
     80first element in gPrev is always the newest element which must
     81build critical pairs with all other elements in gPrev
     82================================================================
     83*/
     84CList* criticalPair(LList* gPrev) {
     85    poly lcm   = pInit();
     86    number n    = nInit(2);
     87    nWrite(n);
     88    pWrite(lcm);
     89    // initialization for usage in pLcm()
     90    LNode* first        =   gPrev->getFirst();
     91    LNode* l            =   gPrev->getFirst()->getNext();
     92    poly t1, t2         =   pInit();
     93    t1                  =   pHead(*first->getPoly());
     94    poly u1             =   pOne();
     95    poly u2             =   pOne();
     96    CList*  critpairs   =   NULL;
     97    // computation of critical pairs
     98    while( NULL != l) {
     99        //pWrite( *(gPrev->getFirst()->getPoly()) );
     100        //pWrite( *(l->getPoly()) );
     101        pLcm(*first->getPoly(), *l->getPoly(), t1);
     102        pWrite(t1);
     103        pWrite(u1);
     104        pWrite(u2);
     105        pSetCoeff0(lcm,n);
     106        poly p = lcm;
     107        pWrite(p);
     108        Print("%ld\n",pDeg(t1));
     109        // computing factors u1 & u2 for new labels
     110        u1  = pDivide(lcm, t1);
     111        pWrite(u1);
     112        pWrite(t1);
     113        Print("%ld\n",pDeg(t1));
     114        //pSetCoeff(u1,pGetCoeff(pOne()));
     115        pWrite(u1);
     116        t2  = pHead(*l->getPoly());
     117        pWrite(t2);
     118        // testing stuff
     119        u1 = ppMult_qq(t1,t2);
     120        pWrite(u1);
     121        pWrite(t2);
     122        Print("%ld\n",pDeg(u1));
     123        Print("%ld\n",pDeg(t2));
     124        u2  = pDivide(lcm, t2);
     125        pSetCoeff(u2, pGetCoeff(pOne()));
     126        pWrite(u2);
     127        Print("%ld\n",pDeg(u2));
     128        // testing both new labels by the F5 Criterion
     129        if(!criterion1(first, gPrev) &&
     130           !criterion1(l, gPrev)) {
     131            if(*first->getIndex() == *l->getIndex()) {
     132                if(pMult(u1, *first->getTerm()) < pMult(u2, *l->getTerm())) {
     133                    //if(!critPairs) {
     134                        CPair* cp   =   new CPair(pDeg(lcm), u1, first->getLPoly(), u2,
     135                                        l->getLPoly());                   
     136                    //}
     137                }
     138            }
     139        }
     140
     141        Print("\n");
     142        l   =   l->getNext();
     143    }
     144    return NULL;
     145}
     146
     147/*
     148========================================
     149Criterion 1, i.e. Faugere's F5 Criterion
     150========================================
     151*/
     152bool criterion1(LNode* l, LList* gPrev) {
     153    LNode* testNode =   l->getNext();
     154    while(NULL != testNode) {
     155        while(*testNode->getIndex() == *l->getIndex()) {
     156            testNode = testNode->getNext();
     157        }
     158    }
     159       
     160
     161    return true;
    74162}
    75163
    … …  
    81169ideal F5main(ideal id, ring r) {
    82170    int i,j;
    83     const int idElems = IDELEMS(id);
    84171    // 1 polynomial for defining initial labels & further tests
    85172    static poly ONE = pOne();
    86    
    87    
     173    i = 1;
     174    LList* gPrev = new LList( &ONE, &i, &id->m[0]);
     175    poly* lcm = new poly;
     176    // initialization for usage in pLcm()
     177    *lcm = pOne();
     178    pWrite(*lcm);
    88179    // definition of one-polynomial as global constant ONE
    89180    //poly one = pInit();
    … …  
    95186            if(pComparePolys(id->m[j],ONE)) {
    96187                Print("One Polynomial in Input => Computations stopped\n");
    97                 ideal id_new = idInit(1,1);
    98                 id_new->m[0] = ONE;
    99                 return(id_new);
     188                ideal idNew = idInit(1,1);
     189                idNew->m[0] = ONE;
     190                return(idNew);
    100191            }   
    101192        }
    102193    }
    103    
     194    pLcm( id->m[0], id->m[1], *lcm);
     195    Print("LCM NEU\n");
     196    //*lcm = pHead(*lcm);
     197    //pWrite(*lcm);
     198    Print("\n\n");
    104199    id = kInterRed(id,0); 
    105200    qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
    106201    idShow(id);
    107     i = 1;
     202    poly p = pHead(id->m[0]);
     203    pWrite(p);
     204    poly q = pHead(id->m[2]);
     205    pWrite(q);
     206    for(i=2; i<=IDELEMS(id); i++) {
     207        gPrev   =   F5inc( &i, &id->m[i-1], gPrev, &ONE );
     208    }
    108209    // only for debugging
    109210    //LNode* current;

  • kernel/f5gb.h

    r0883ed rcce6ed3  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.15 2009-01-15 17:44:23 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.16 2009-01-25 17:13:06 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    2121void qsort_degree(poly* left, poly* right);
    2222
    23 
    2423/*
    2524==============================================
    … …  
    3029void generate_input_list(LPoly* lp, ideal id, poly one);
    3130
    32 
    3331/*
    3432==================================================
    … …  
    3735==================================================
    3836*/
    39 LList* F5inc(const int i, LList* g_prev);
     37LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE);
    4038
     39/*
     40================================================================
     41computes a list of critical pairs for the next reduction process
     42first element in gPrev is always the newest element which must
     43build critical pairs with all other elements in gPrev
     44================================================================
     45*/
     46CList* criticalPair(LList* gPrev);
    4147
     48/*
     49========================================
     50Criterion 1, i.e. Faugere's F5 Criterion
     51========================================
     52*/
     53bool criterion1(LNode* l, LList* gPrev);
    4254/*
    4355======================================

  • kernel/lists.cc

    r0883ed rcce6ed3  
    3434    LPoly* lp = new LPoly(t,i,p);
    3535    data = lp;
    36     Print("Index angelegt?  %d\n",*(data->getIndex()));
    3736    next = NULL;
    3837}
    … …  
    6160}
    6261       
     62// insert new elemets to the list w.r.t. increasing labels
     63// only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
     64LNode* LNode::insertByLabel(LPoly* lp) {
     65    if( lp->getTerm() <= this->data->getTerm() ) {
     66        LNode* newElement   =   new LNode(lp);
     67        newElement->next    =   this;
     68        return newElement;
     69    }
     70    else {
     71        LNode* temp = this;
     72        while( NULL != temp->next ) {
     73            if( lp->getTerm() <= temp->next->data->getTerm() ) {
     74                LNode* newElement   =   new LNode(lp);
     75                newElement->next    =   temp->next;
     76                temp->next          =   newElement;
     77                return this;
     78            }
     79            else {
     80                temp = temp->next;
     81            }
     82        }
     83        LNode* newElement   =   new LNode(lp);
     84        temp->next          =   newElement;
     85        newElement->next    =   NULL;
     86        return this;
     87    }
     88}
     89
     90// deletes the first elements of the list with the same degree
     91// only used for the S-polys, which are already sorted by increasing degree by CList
     92LNode*  LNode::deleteByDeg() {
     93    return this;
     94}
     95
    6396// get next from current LNode
    6497LNode* LNode::getNext() {
    … …  
    71104}
    72105
    73 // get the address of the polynomial part of LPoly* of LNode*
     106// get the data from the LPoly saved in LNode
    74107poly* LNode::getPoly() {
    75108    return data->getPoly();
     109}
     110
     111poly* LNode::getTerm() {
     112    return data->getTerm();
     113}
     114
     115int* LNode::getIndex() {
     116    return data->getIndex();
    76117}
    77118
    … …  
    88129}
    89130
     131LNode* LNode::getNext(LNode* l) {
     132    return l->next;
     133}
    90134
    91135/*
    … …  
    97141LList::LList(LPoly* lp) {
    98142    first   = new LNode(lp);
    99     length  = 1;
    100143}
    101144
    102145LList::LList(poly* t,int* i,poly* p) {
    103146    first   = new LNode(t,i,p);
    104     length  = 1;
    105147}
    106148
    … …  
    112154void LList::insert(LPoly* lp) {
    113155    first = first->insert(lp);
    114     length++;
    115156}
    116157
    117158void LList::insert(poly* t,int* i, poly* p) {
    118159    first = first->insert(t,i,p);
    119     length++;
     160}
     161
     162void LList::insertByLabel(LPoly* lp) {
     163    first = first->insertByLabel(lp);
     164}
     165
     166void LList::deleteByDeg() {
     167    first = first->deleteByDeg();
    120168}
    121169
    … …  
    124172}
    125173
    126 int LList::getLength() const {
    127     return length;
    128 }
    129 
    130174LNode* LList::getFirst() {
    131175    return first;
    132176}
    133177
     178LNode* LList::getNext(LNode* l) {
     179    return l->getNext();
     180}
    134181
    135182/*
    … …  
    225272        else {
    226273            CNode* temp = this;
    227             while(  temp->next != NULL ) {
     274            while(  NULL != temp->next ) {
    228275                if( temp->next->data->getDeg() == c->getDeg() ) {
    229276                    if( c->getT1() <= temp->next->data->getT1() ) {
    … …  
    252299    if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
    253300        CNode* temp =   this;
    254         while( temp->next != NULL) {   
     301        while( NULL != temp->next ) {   
    255302            if( c->getDeg() < temp->next->data->getDeg() ) {
    256303                CNode* newElement   =   new CNode(c);
    … …  
    268315                else {
    269316                    temp = temp->next;
    270                     while(  temp->next != NULL ) {
     317                    while(  NULL != temp->next ) {
    271318                        if( temp->next->data->getDeg() == c->getDeg() ) {
    272319                            if( c->getT1() <= temp->next->data->getT1() ) {
    … …  
    304351}
    305352
     353// get the first elements from CList which by the above sorting have minimal degree
     354CNode* CNode::getMinDeg() {
     355    CNode* temp = this;
     356    while( NULL != temp ) {
     357        if( temp->next->data->getDeg() == this->data->getDeg() ) {
     358            temp = temp->next;
     359        }
     360        CNode* returnCNode  =   temp->next;   
     361        temp->next          =   NULL;
     362        return returnCNode;
     363    }
     364    return NULL;
     365}
     366
     367
    306368/*
    307369====================================
    … …  
    309371====================================
    310372*/
    311 
    312373CList::CList(CPair* c) {
    313374    first   = new CNode(c);
    … …  
    323384    first = first->insert(c);
    324385}
     386
     387// get the first elements from CList which by the above sorting have minimal degree
     388// returns the pointer on the first element of those
     389CNode* CList::getMinDeg() {
     390    CNode* temp     =   first;
     391    first           =   first->getMinDeg();
     392    return temp;
     393}
     394
     395
     396/*
     397====================================
     398functions working on the class RNode
     399====================================
     400*/
     401RNode::RNode(Rule* r) {
     402    data    =   r;
     403    next    =   NULL;
     404}
     405
     406RNode::~RNode() {
     407    delete  next;
     408    delete  data;
     409}
     410
     411RNode* RNode::insert(Rule* r) {
     412    RNode* newElement   =   new RNode(r);
     413    newElement->next    =   this;
     414    return newElement;
     415}
     416
     417/*
     418====================================
     419functions working on the class RList
     420====================================
     421*/
     422RList::RList(Rule* r) {
     423    first = new RNode(r);
     424}
     425
     426void RList::insert(Rule* r) {
     427    first = first->insert(r);
     428}
    325429#endif

  • kernel/lists.h

    r0883ed rcce6ed3  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lists.h,v 1.3 2009-01-15 17:44:24 ederc Exp $ */
     4/* $Id: lists.h,v 1.4 2009-01-25 17:13:06 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    2424class CNode;
    2525class CList;
    26 
     26class RList;
     27class RNode;
    2728
    2829/*
    … …  
    4142                LNode(LNode* ln);
    4243                ~LNode();
    43         // append new elements to the list from the labeled / classical polynomial view
     44        // insert new elements to the list in first place from the labeled / classical polynomial view
    4445        LNode*  insert(LPoly* lp);
    4546        LNode*  insert(poly* t, int* i, poly* p);
     47        // insert new elements to the list with resp. to increasing labels
     48        // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
     49        LNode*  insertByLabel(LPoly* lp);
     50        // deletes the first elements of the list with the same degree
    4651        // get next from current LNode
    4752        LNode*  getNext();
    48        
     53        // only used for the S-polys, which are already sorted by increasing degree by CList
     54        LNode*  deleteByDeg();
    4955        // get the LPoly* out of LNode*
    5056        LPoly*  getLPoly();
    51         // get the address of the polynomial part of LPoly* of LNode*
     57        // get the data from the LPoly saved in LNode
    5258        poly*   getPoly();
     59        poly*   getTerm();
     60        int*    getIndex();
    5361        // test if for any list element the polynomial part of the data is equal to *p
    5462        bool    polyTest(poly* p);
     63        LNode*  getNext(LNode* l);
    5564};
    5665
    … …  
    6473    private:
    6574        LNode*  first;
    66         int     length;
    6775    public:
    6876                LList(LPoly* lp);
    … …  
    7280        // insertion in front of the list
    7381        void    insert(poly* t,int* i, poly* p);
     82        void    insertByLabel(LPoly* lp);
     83        void    deleteByDeg();
    7484        bool    polyTest(poly* p);
    75         int     getLength() const;
    76         LNode*  getFirst();
     85        LNode*  getFirst();
     86        LNode*  getNext(LNode* l);
    7787};
    7888
    … …  
    115125/*
    116126=======================================
    117 CNode class (nodes for lists of CPairs)
     127class CNode (nodes for lists of CPairs)
    118128=======================================
    119129*/
    … …  
    126136                ~CNode();
    127137        CNode*  insert(CPair* c);
    128         CNode*  getLPoly() const;
     138        CNode*  getMinDeg();
     139        //CNode*  getLPoly() const;
    129140};
    130141
    131142
    132143/*
    133 =============================
    134 class CPList(lists of CPairs)
    135 =============================
     144============================
     145class CList(lists of CPairs)
     146============================
    136147*/
    137148class CList {
    … …  
    141152                CList(CPair* c);
    142153                ~CList();
    143         void    insert(CPair* c);
     154        void    insert(CPair* c);
     155        CNode*  getMinDeg();
     156
     157};
     158
     159
     160/*
     161======================================
     162class RNode (nodes for lists of Rules)
     163======================================
     164*/
     165class RNode {
     166    private:
     167        Rule*   data;
     168        RNode*  next;
     169    public:
     170                RNode(Rule* r);
     171                ~RNode();
     172        RNode*  insert(Rule* r);
     173};
     174
     175/*
     176============================
     177class RList (lists of Rules)
     178============================
     179*/
     180class RList {
     181    private:
     182        RNode*  first;
     183    public:
     184                RList(Rule* r);
     185                ~RList();
     186        void    insert(Rule* r);
    144187};
    145188#endif

  • kernel/lpolynomial.cc

    r0883ed rcce6ed3  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lpolynomial.cc,v 1.5 2009-01-15 17:44:24 ederc Exp $ */
     4/* $Id: lpolynomial.cc,v 1.6 2009-01-25 17:13:06 ederc Exp $ */
    55/*
    66* ABSTRACT: lpolynomial definition
    … …  
    8181====================================
    8282*/
    83 CPair::CPair(int degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2) {
     83CPair::CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2) {
    8484   deg  =   degree;
    8585   t1   =   term1;
    … …  
    8989}
    9090
    91 int CPair::getDeg() {
     91long CPair::getDeg() {
    9292    return deg;
    9393}
    … …  
    127127
    128128
     129/*
     130===================================
     131functions working on the class Rule
     132===================================
     133*/
     134Rule::Rule(int* i, poly* t) {
     135    index   =   i;
     136    term    =   t;
     137}
     138
     139int Rule::getIndex() {
     140    return *index;
     141}
     142
     143poly Rule::getTerm() {
     144    return *term;
     145}
    129146#endif

  • kernel/lpolynomial.h

    r0883ed rcce6ed3  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lpolynomial.h,v 1.5 2009-01-15 17:44:24 ederc Exp $ */
     4/* $Id: lpolynomial.h,v 1.6 2009-01-25 17:13:06 ederc Exp $ */
    55/*
    66* ABSTRACT: labeled polynomial interface
    … …  
    1919class LPoly;
    2020class CPair;
     21class Rule;
    2122
    2223
    2324/*
    24 =============================
    25 class of a labeled polynomial
    26 =============================
     25============================
     26class of labeled polynomials
     27============================
    2728*/
    2829class LPoly {
    … …  
    4849
    4950/*
    50 ===============================
    51 structure of the critical pairs
    52 ===============================
     51===================================
     52structure of labeled critical pairs
     53===================================
    5354*/
    5455class CPair {
    5556    private:
    56         int     deg;    // total degree of the critical pair
     57        long    deg;    // total degree of the critical pair
    5758        poly    t1;     // first term for label
    5859        LPoly*  lp1;     // first labeled poly
    … …  
    6061        LPoly*  lp2;     // second labeled poly
    6162    public:
    62                 CPair(int degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2);
    63         int     getDeg();
     63                CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2);
     64        long    getDeg();
    6465        poly    getT1();
    6566        poly    getLp1Poly();
    … …  
    7374
    7475
     76/*
     77========================================================
     78structure of rules(i.e. already computed / known labels)
     79========================================================
     80*/
     81class Rule {
     82    private:
     83        int*     index;    // index of the labeled polynomial the rule comes from
     84        poly*    term;     // term of the labeled polynomial the rule comes from
     85    public:
     86                Rule(int* i, poly* term);
     87        int     getIndex();
     88        poly    getTerm();
     89};
    7590#endif
    7691#endif
Note: See TracChangeset for help on using the changeset viewer.