source: git/kernel/gfan.cc @ 54248e

spielwiese
Last change on this file since 54248e was 54248e, checked in by Martin Monerjan, 14 years ago
Got methods printNormal() and setFacetNormal(intvec *iv) of class facet to work. Initialisation of rings needs more work. This rev will not compile git-svn-id: file:///usr/local/Singular/svn/trunk@11593 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 10.3 KB
Line 
1/*
2Compute the Groebner fan of an ideal
3$Author: monerjan $
4$Date: 2009-03-26 10:30:21 $
5$Header: /exports/cvsroot-2/cvsroot/kernel/gfan.cc,v 1.22 2009-03-26 10:30:21 monerjan Exp $
6$Id: gfan.cc,v 1.22 2009-03-26 10:30:21 monerjan Exp $
7*/
8
9#include "mod2.h"
10
11#ifdef HAVE_GFAN
12
13#include "kstd1.h"
14#include "intvec.h"
15#include "polys.h"
16#include "ideals.h"
17#include "kmatrix.h"
18#include "iostream.h"   //deprecated
19
20//Hacks for different working places
21#define ITWM
22
23#ifdef UNI
24#include "/users/urmel/alggeom/monerjan/cddlib/include/setoper.h" //Support for cddlib. Dirty hack
25#include "/users/urmel/alggeom/monerjan/cddlib/include/cdd.h"
26#endif
27
28#ifdef HOME
29#include "/home/momo/studium/diplomarbeit/cddlib/include/setoper.h"
30#include "/home/momo/studium/diplomarbeit/cddlib/include/cdd.h"
31#endif
32
33#ifdef ITWM
34#include "/u/slg/monerjan/cddlib/include/setoper.h"
35#include "/u/slg/monerjan/cddlib/include/cdd.h"
36#endif
37
38#ifndef gfan_DEBUG
39#define gfan_DEBUG
40#endif
41
42//#include gcone.h
43
44/**
45*\brief Class facet
46*       Implements the facet structure
47*
48*/
49class facet
50{
51        private:
52                /** inner normal, describing the facet uniquely  */
53                intvec *fNormal;               
54        public:
55                /** The default constructor. Do I need a constructor of type facet(intvec)? */
56                facet()                 
57                {
58                        // Pointer to next facet.  */
59                        /* Defaults to NULL. This way there is no need to check explicitly */
60                        this->next=NULL; 
61                }
62               
63                /** The default destructor */
64                ~facet(){;}
65               
66                /** Stores the facet normal \param intvec*/
67                void setFacetNormal(intvec *iv){
68                        fNormal = iv;
69                        //return;
70                }
71               
72                /** Method to print the facet normal*/
73                void printNormal()
74                {
75                        fNormal->show();
76                }
77               
78                bool isFlippable;       //flippable facet? Want to have cone->isflippable.facet[i]
79                bool isIncoming;        //Is the facet incoming or outgoing?
80                facet *next;            //Pointer to next facet
81};
82
83/**
84*\brief Class gcone
85*       Implements the cone structure
86*/
87/*class gcone
88finally this should become s.th. like gconelib.{h,cc} to provide an API
89*/
90class gcone
91{
92        private:
93                int numFacets;          //#of facets of the cone
94
95        public:
96                gcone()
97                {
98                        this->next=NULL;
99                        this->facetPtr=NULL;
100                }
101                gcone(int);             //constructor with dimension
102                ~gcone();               //destructor
103                facet *facetPtr;        //Will hold the adress of the first facet
104                poly gcMarkedTerm;      //marked terms of the cone's Groebner basis
105                ideal gcBasis;          //GB of the cone
106                gcone *next;            //Pointer to *previous* cone in search tree
107       
108                void flip();            //Compute "the other side"
109                void remRedFacets();    //Remove redundant facets of the cone NOT NEEDED since this is already done by cddlib while compunting the normals
110               
111                ideal GenGrbWlk(ideal, ideal);  //Implementation of the Generic Groebner Walk. Needed for a) Computing the sink and b) finding search facets
112               
113
114};//class gcone
115
116ideal getGB(ideal inputIdeal)
117{
118        #ifdef gfan_DEBUG
119        cout << "Computing a groebner basis..." << endl;
120        #endif
121
122        ideal gb;
123        gb=kStd(inputIdeal,NULL,testHomog,NULL); //Possible to call without testHomog/isHomog?
124        idSkipZeroes(gb); //Get rid of zero entries
125
126        return gb;
127}
128
129/**
130*\brief Compute the representation of a cone
131*
132*       Detailed description goes here
133*
134*\param An ideal
135*
136*\return A pointer to a facet
137*/
138/****** getConeNormals computes the inequalities ***/
139/*INPUT_TYPE: ideal                             */
140/*RETURN_TYPE: pointer to first facet           */
141/************************************************/
142facet *getConeNormals(ideal I)
143{
144        #ifdef gfan_DEBUG
145        cout << "*** Computing Inequalities... ***" << endl;
146        #endif
147
148        //All variables go here - except ineq matrix and *v, see below
149        int lengthGB=IDELEMS(I);        // # of polys in the groebner basis
150        int pCompCount;                 // # of terms in a poly
151        poly aktpoly;
152        int numvar = pVariables;        // # of variables in a polynomial (or ring?)
153        int leadexp[numvar];            // dirty hack of exp.vects
154        int aktexp[numvar];
155        int cols,rows;                  // will contain the dimensions of the ineq matrix - deprecated by
156        dd_rowrange ddrows;
157        dd_colrange ddcols;
158        dd_rowset ddredrows;            // # of redundant rows in ddineq
159        dd_rowset ddlinset;             // the opposite
160        dd_rowindex ddnewpos;           // all to make dd_Canonicalize happy
161        dd_NumberType ddnumb=dd_Real;   //Number type
162        dd_ErrorType dderr=dd_NoError;  //
163        // End of var declaration
164
165        cout << "The Groebner basis has " << lengthGB << " elements" << endl;
166        cout << "The current ring has " << numvar << " variables" << endl;
167        cols = numvar;
168
169        //Compute the # inequalities i.e. rows of the matrix
170        rows=0; //Initialization
171        for (int ii=0;ii<IDELEMS(I);ii++)
172        {
173                aktpoly=(poly)I->m[ii];
174                rows=rows+pLength(aktpoly)-1;
175        }
176        cout << "rows=" << rows << endl;
177        cout << "Will create a " << rows << " x " << cols << " matrix to store inequalities" << endl;
178
179        dd_rowrange aktmatrixrow=0;     // needed to store the diffs of the expvects in the rows of ddineq
180        dd_set_global_constants();
181        ddrows=rows;
182        ddcols=cols;
183        dd_MatrixPtr ddineq;            //Matrix to store the inequalities
184        ddineq=dd_CreateMatrix(ddrows,ddcols+1); //The first col has to be 0 since cddlib checks for additive consts there
185
186        // We loop through each g\in GB and compute the resulting inequalities
187        for (int i=0; i<IDELEMS(I); i++)
188        {
189                aktpoly=(poly)I->m[i];          //get aktpoly as i-th component of I
190                pCompCount=pLength(aktpoly);    //How many terms does aktpoly consist of?
191                cout << "Poly No. " << i << " has " << pCompCount << " components" << endl;
192
193                int *v=(int *)omAlloc((numvar+1)*sizeof(int));
194                pGetExpV(aktpoly,v);    //find the exp.vect in v[1],...,v[n], use pNext(p)
195               
196                //Store leadexp for aktpoly
197                for (int kk=0;kk<numvar;kk++)
198                {
199                        leadexp[kk]=v[kk+1];
200                        //printf("Leadexpcomp=%i\n",leadexp[kk]);
201                        //Since we need to know the difference of leadexp with the other expvects we do nothing here
202                        //but compute the diff below
203                }
204
205               
206                while (pNext(aktpoly)!=NULL) //move to next term until NULL
207                {
208                        aktpoly=pNext(aktpoly);
209                        pSetm(aktpoly);         //doesn't seem to help anything
210                        pGetExpV(aktpoly,v);
211                        for (int kk=0;kk<numvar;kk++)
212                        {
213//The ordering somehow gets lost here but this is acceptable, since we are only interested in the inequalities
214                                aktexp[kk]=v[kk+1];
215                                //printf("aktexpcomp=%i\n",aktexp[kk]);
216                                //ineq[aktmatrixrow][kk]=leadexp[kk]-aktexp[kk];        //dito
217                                dd_set_si(ddineq->matrix[(dd_rowrange)aktmatrixrow][kk+1],leadexp[kk]-aktexp[kk]); //because of the 1st col being const 0
218                        }
219                        aktmatrixrow=aktmatrixrow+1;
220                }//while
221
222        } //for
223
224        //Maybe add another row to contain the constraints of the standard simplex?
225
226        #ifdef gfan_DEBUG
227        cout << "The inequality matrix is" << endl;
228        dd_WriteMatrix(stdout, ddineq);
229        #endif
230
231        // The inequalities are now stored in ddineq
232        // Next we check for superflous rows
233        ddredrows = dd_RedundantRows(ddineq, &dderr);
234        if (dderr!=dd_NoError)                  // did an error occur?
235        {
236                 dd_WriteErrorMessages(stderr,dderr);   //if so tell us
237        } else
238        {
239                cout << "Redundant rows: ";
240                set_fwrite(stdout, ddredrows);          //otherwise print the redundant rows
241        }//if dd_Error
242
243        //Remove reduntant rows here!
244        dd_MatrixCanonicalize(&ddineq, &ddlinset, &ddredrows, &ddnewpos, &dderr);
245        ddrows = ddineq->rowsize;       //Size of the matrix with redundancies removed
246        ddcols = ddineq->colsize;
247        #ifdef gfan_DEBUG
248        cout << "Having removed redundancies, the normals now read:" << endl;
249        dd_WriteMatrix(stdout,ddineq);
250        cout << "Rows = " << ddrows << endl;
251        cout << "Cols = " << ddcols << endl;
252        #endif
253
254        /*dd_PolyhedraPtr ddpolyh;
255        dd_MatrixPtr G;
256        ddpolyh=dd_DDMatrix2Poly(ddineq, &dderr);
257        G=dd_CopyGenerators(ddpolyh);
258        printf("\nSpanning vectors = rows:\n");
259        dd_WriteMatrix(stdout, G);
260        */
261       
262       
263        /*Write the normals into class facet*/
264        #ifdef gfan_DEBUG
265        cout << "Creating list of normals" << endl;
266        #endif
267        /*The pointer *fRoot should be the return value of this function*/
268        facet *fRoot = new facet();             //instantiate new facet with intvec with numvar rows, one column and initial values all 0
269        facet *fAct;                    //instantiate pointer to active facet
270        fAct = fRoot;           //This does not seem to do the trick. fRoot and fAct have to point to the same adress!
271        std::cout << "fRoot = " << fRoot << ", fAct = " << fAct << endl;
272        //fAct = fRoot;                 //Let fAct point to fRoot
273        for (int kk = 0; kk<ddrows; kk++)
274        {
275                intvec *load = new intvec(numvar);      //intvec to store a single facet normal that will then be stored via setFacetNormal
276                for (int jj = 1; jj <ddcols; jj++)
277                {
278                        double *foo;
279                        foo = (double*)ddineq->matrix[kk][jj];  //get entry from actual position
280#ifdef gfan_DEBUG
281                        std::cout << "fAct is " << *foo << " at " << fAct << std::endl;
282#endif
283                        /*next two lines commented out. How to store values into intvec? */
284                        (*load)[jj-1] = (int)*foo;              //store typecasted entry at pos jj-1 of load
285                        //fAct->setFacetNormal(load);
286                        //check for flipability here
287                        if (jj<ddcols)                          //Is this facet NOT the last facet? Writing while instead of if is a really bad idea :)
288                        {
289                                fAct->next = new facet();       //If so: instantiate new facet. Otherwise this->next=NULL due to the constructor
290                                fAct = fAct->next;              //scary :)
291                        }
292                }//for jj<ddcols
293                /*Now load should be full and we can call setFacetNormal*/
294                fAct->setFacetNormal(load);
295                fAct->printNormal();
296        }
297        /*
298        Now we should have a concatenated list containing the facet normals of those facets that are
299                -irredundant
300                -flipable
301        Adressing is done via *fRoot
302        But since we did this in a function probably most if not all is lost after the return. So implement this as a method of gcone
303        */
304       
305        //ddineq->representation=dd_Inequality;         //We want our LP to be Ax>=0
306        //Clean up but don't delete the return value! (Whatever it will turn out to be)
307        dd_FreeMatrix(ddineq);
308        set_free(ddredrows);
309        free(ddnewpos);
310        set_free(ddlinset);
311        dd_free_global_constants();
312
313        return fRoot;
314}
315
316ideal gfan(ideal inputIdeal)
317{
318        int numvar = pVariables; 
319       
320        #ifdef gfan_DEBUG
321        cout << "Now in subroutine gfan" << endl;
322        #endif
323        ring rootRing;  // The ring associated to the target ordering
324        rRingOrder_t t=ringorder_dp;
325       
326        ideal res;
327        matrix ineq; //Matrix containing the boundary inequalities
328        facet *fRoot;
329       
330       
331        rootRing=rCopy0(currRing);
332        rootRing=rInit(0,numvar,t);
333        rComplete(rootRing);
334        rChangeCurrRing(rootRing);
335        cout << "The current ring is " << endl;
336        rWrite(rootRing);
337       
338        gcone *gcRoot = new gcone();    //Instantiate the sink
339        gcone *gcAct;
340        gcAct = gcRoot;
341
342       
343        /*
344        1. Select target order, say dp.
345        2. Compute GB of inputIdeal wrt target order -> newRing, setCurrRing etc...
346        3. getConeNormals
347        */
348        res=getGB(inputIdeal);
349        fRoot=getConeNormals(res);
350        cout << fRoot << endl;
351        return res;
352}
353/*
354Since gfan.cc is #included from extra.cc there must not be a int main(){} here
355*/
356#endif
Note: See TracBrowser for help on using the repository browser.