Changeset 199ae7 in git


Ignore:
Timestamp:
Dec 26, 2008, 2:49:57 PM (14 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')
Children:
d72b11bc8b23f633cdb4f322bbbbab31c23597cb
Parents:
565e866c54dc28cc8085355e58a8d9ba2b7e0d2c
Message:
incremental basis


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

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    r565e86 r199ae7  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.cc,v 1.13 2008-11-27 17:17:32 ederc Exp $ */
     4/* $Id: f5gb.cc,v 1.14 2008-12-26 13:49:29 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    2323#include "f5gb.h"
    2424#include "lpolynomial.h"
    25 #include "lplist.h"
     25#include "lists.h"
     26
     27
     28/*
     29=======================
     30static/global variables
     31=======================
     32*/
     33static poly ONE = one_poly();
     34
     35
     36/*
     37================================================
     38computation of ONE polynomial as global variable
     39================================================
     40*/
     41poly one_poly() {
     42    poly one = pInit();
     43    pSetCoeff(one,nInit(1));
     44    return one;
     45}
     46
     47/*
     48====================================================================
     49sorting ideals by decreasing total degree "left" and "right" are the
     50pointer of the first and last polynomial in the considered ideal
     51====================================================================
     52*/
     53void qsortDegree(poly* left, poly* right) {
     54    poly* ptr1 = left;
     55    poly* ptr2 = right;
     56    poly p1,p2;
     57    p2 = *(left + (right - left >> 1));
     58    do {
     59            while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)) {
     60                    ptr1++;
     61            }
     62            while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)) {
     63                    ptr2--;
     64            }
     65            if(ptr1 > ptr2) {
     66                    break;
     67            }
     68            p1    = *ptr1;
     69            *ptr1 = *ptr2;
     70            *ptr2 = p1;
     71    } while(++ptr1 <= --ptr2);
     72
     73    if(left < ptr2) {
     74            qsortDegree(left,ptr2);
     75    }
     76    if(ptr1 < right) {
     77            qsortDegree(ptr1,right);
     78    }
     79}
     80
     81
     82/*
     83==================================================
     84computes incrementally gbs of subsets of the input
     85gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
     86==================================================
     87*/
     88 
     89LList* F5inc(long i, poly* f_i, LList* g_prev) {
     90    LList* g_curr       =   g_prev;
     91    LNode* prev_last    =   g_prev->getLast(); //tags the end of g_prev->only 1 list for g_prev & g_curr
     92    g_curr->append(&ONE,&i,f_i);
     93   
     94    return g_curr;
    2695
    2796
    2897
    29 /*2
    30 * sorting ideals by decreasing total degree
    31 * "left" and "right" are the pointer of the first
    32 * and last polynomial in the considered ideal
    33 */
    34 void qsort_degree(poly* left, poly* right)
    35 {
    36         poly* ptr1 = left;
    37         poly* ptr2 = right;
    38         poly p1,p2;
    39         p2 = *(left + (right - left >> 1));
    40         do{
    41                 while(pTotaldegree(*ptr1, currRing) < pTotaldegree(p2, currRing)){
    42                         ptr1++;
    43                 }
    44                 while(pTotaldegree(*ptr2, currRing) > pTotaldegree(p2,currRing)){
    45                         ptr2--;
    46                 }
    47                 if(ptr1 > ptr2){
    48                         break;
    49                 }
    50                 p1    = *ptr1;
    51                 *ptr1 = *ptr2;
    52                 *ptr2 = p1;
    53         } while(++ptr1 <= --ptr2);
    5498
    55         if(left < ptr2){
    56                 qsort_degree(left,ptr2);
    57         }
    58         if(ptr1 < right){
    59                 qsort_degree(ptr1,right);
    60         }
    6199}
    62100
    63 
    64 /*2
    65 * computes incrementally gbs of subsets of the input
    66 * gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1}
    67  
    68 LPoly *f5_inc(LPoly* lp, LPoly* g_prev)
    69 {
    70         long length = 1;
    71        
    72         while(g_prev->getNext() != NULL) {
    73                 length++;
    74                 g_prev++;
    75         }
    76         Print("Laenge der Liste: %d\n",length);
    77         /*critpair *critpairs = new critpair[length];
    78         * int i = 1;
    79         *
    80         * while(g_prev->getNext()->getNext() != NULL) {
    81         *        critpairs[i] = {lp, g_prev, critpairs[i+1]};
    82         *        i++;
    83         *        g_prev++;
    84         * }
    85         * *critpairs[length] = {lp, g_prev+length-1, NULL};
    86         *
    87         * return lp;
    88        
    89 }   
    90 
     101/*
     102==========================================================================
     103MAIN:computes a gb of the ideal i in the ring r with our f5 implementation
     104==========================================================================
    91105*/
    92 // generating the list lp of ideal generators and test if 1 is in lp
    93 bool generate_input_list(LPoly* lp, ideal id, poly ONE)
    94 {
    95         long j;
    96         for(j=0; j<IDELEMS(id)-1; j++){
    97 
    98                 lp[j].setPoly(id->m[j]);
    99                
    100                 if(pComparePolys(lp[j].getPoly(), ONE)){
    101                         Print("1 in GB\n");
    102                         return(1);
    103                 }
    104                
    105                 lp[j].setIndex(j+1);
    106                 lp[j].setTerm(ONE);
    107                 lp[j].setDel(false);
    108                 lp[j].setNext(&lp[j+1]);
    109                 Print("Labeled Polynomial %ld: ",j+1);
    110                 Print("Label Term: ");
    111                 pWrite(lp[j].getTerm());
    112                 Print("Index: %ld\n", lp[j].getIndex());
    113                 Print("Delete? %d\n", lp[j].getDel());
    114                 pWrite(lp[j].getPoly());
    115                 Print("NEUNEUNEU\n\n");
    116         }
    117         return(0);
    118 }
    119 
    120 
    121 /*2
    122 * computes a gb of the ideal i in the ring r with our f5
    123 * implementation
    124 */
    125 ideal F5main(ideal i, ring r) {
    126 
    127     long j;
    128     LPoly * lp = new LPoly;
     106ideal F5main(ideal id, ring r) {
     107    long i,j;
     108    LPoly* lp = new LPoly;
    129109    // definition of one-polynomial as global constant ONE
    130     poly one = pInit();
    131     pSetCoeff(one, nInit(1));
    132     static const poly ONE = one;
     110    //poly one = pInit();
     111    //pSetCoeff(one, nInit(1));
     112    //static poly ONE = one;
    133113   
    134     //
    135     for(j=0; j<IDELEMS(i); j++) {
    136         if(NULL != i->m[j]) {
    137             if(pComparePolys(i->m[j],ONE)) {
     114    for(j=0; j<IDELEMS(id); j++) {
     115        if(NULL != id->m[j]) {
     116            if(pComparePolys(id->m[j],ONE)) {
    138117                Print("One Polynomial in Input => Computations stopped\n");
    139                 return(i);
     118                ideal id_new = idInit(1,1);
     119                id_new->m[0] = ONE;
     120                return(id_new);
    140121            }   
    141122        }
    142123    }
    143124   
    144     i = kInterRed(i,0); 
    145     qsort_degree(&i->m[0],&i->m[IDELEMS(i)-1]);
    146     idShow(i);
    147            
     125    id = kInterRed(id,0); 
     126    qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
     127    idShow(id);
     128    i = 1;
     129    //lp->setIndex(&i);
     130    //lp->setTerm(&ONE);
     131    //lp->setPoly(&id->m[0]);
     132    //lp->set(ONE,1,ONE);   
    148133    /* if(generate_input_list(lp,iTmp,ONE)) {
    149134            Print("One Polynomial in Input => Computations stopped");
    … …  
    153138    }
    154139    */
    155     Print("Es klappt!\nWIRKLICH!\n");
    156140    // only for debugging
    157     lp->get();
    158     //return(i);
    159     LpList lp_list;
    160     while(NULL != lp->getNext()) {
    161         lp_list.insert(lp);
    162         lp = lp->getNext();
     141    long k = 1;
     142    LList* g_prev = new LList(lp);
     143    //LList* g_curr = new LList;
     144    //LNode* current = new LNode;
     145    g_prev->append(&ONE,&k,&id->m[2]);
     146    i = g_prev->getLength();
     147    Print("%ld\n\n",i);
     148    LPoly* current = g_prev->getFirst()->getLPoly();
     149    if(pComparePolys(current->getPoly(), id->m[0])) {
     150        Print("Yes!\n");
    163151    }
    164     lp_list.get();
    165     return i;
     152    //current = g_prev->getFirst();
     153    //current++;
     154    //Print("Term: %ld\n\n",current->get()->getTerm);
     155    /*for(i=2; i<IDELEMS(id); i++) {
     156        g_curr = F5inc(i,g_prev);
     157        if(g_curr->poly_test(ONE)) {
     158            Print("One Polynomial in Input => Computations stopped\n");
     159            ideal id_new = idInit(1,1);
     160            id_new->m[0] = ONE;
     161            return(id_new);               
     162        }
     163    }
     164    */       
     165    return(id);
    166166
    167167

  • kernel/f5gb.h

    r565e86 r199ae7  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.12 2008-11-27 17:18:05 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.13 2008-12-26 13:49:57 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    1111#ifdef HAVE_F5
    1212#include "lpolynomial.h"
    13 #include "lplist.h"
     13#include "lists.h"
    1414
    1515
    16 // sort polynomials in ideal i by decreasing total degree
    17  void qsort_degree(poly* left, poly* right);
     16/*
     17================================================
     18computation of ONE polynomial as global variable
     19================================================
     20*/
     21poly one_poly();
    1822
    1923
    20 // generating the list lp of ideal generators and
    21 // test if 1 is in lp(return 1) or not(return 0)
    22  bool generate_input_list(LPoly* lp, ideal id, poly one);
    23 
    24 /* computes incrementally gbs of subsets of the input
    25    gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} 
     24/*
     25======================================================
     26sort polynomials in ideal i by decreasing total degree
     27======================================================
    2628*/
    27 // lpoly* f5_inc(lpoly* lp, lpoly* g_prev);
     29void qsort_degree(poly* left, poly* right);
    2830
    2931
    30 // main function of our f5 implementation
     32/*
     33==============================================
     34generating the list lp of ideal generators and
     35test if 1 is in lp(return 1) or not(return 0)
     36==============================================
     37*/
     38void generate_input_list(LPoly* lp, ideal id, poly one);
     39
     40
     41/*
     42==================================================
     43computes incrementally gbs of subsets of the input
     44gb{f_m} -> gb{f_m,f_(m-1)} -> gb{f_m,...,f_1} 
     45==================================================
     46*/
     47LList* F5inc(const long i, LList* g_prev);
     48
     49
     50/*
     51======================================
     52main function of our f5 implementation
     53======================================
     54*/
    3155ideal F5main(ideal i, ring r);
     56
     57
    3258#endif
    3359#endif
Note: See TracChangeset for help on using the changeset viewer.