ideal.h

Go to the documentation of this file.

/* 
 * Copyright (C) 2015 Antoine Joux, Vanessa Vitse and Titouan Coladon
 * 
 * This file is part of openf4.
 * 
 * openf4 is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * openf4 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with openf4.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef OPENF4_IDEAL_H
#define OPENF4_IDEAL_H

#include "global.h"
#include <iostream>
#include "matrix.h"
#include "avl-monomial.h"
#include "avl-polynomial.h"
#include "avl-critical-pair.h"

namespace F4
{
    struct Stat
    {
        int _nbCp; 
        int _nbCpDeg; 
        int _cmptGenPurg; 
        int _cmptNewGen; 
        clock_t _timePurgeCp; 
        clock_t _timeAddCp; 
        clock_t _timeMajBasis; 
        Stat():_nbCp(0), _nbCpDeg(0), _cmptGenPurg(0), _cmptNewGen(0), _timePurgeCp(0), _timeAddCp(0), _timeMajBasis(0)
        {
        }
    };
    
    template <typename Element>
    class Ideal
    {
        public:
            
            /* Constructor */
            
            Ideal(std::vector<Polynomial<Element>> & polynomialArray, int nbVariable, int capacity=100000, int degree=0);
            
            
            /* Destructor */
            
            ~Ideal();
            
            
            /* Miscellaneous */
            
            void printInfo() const;
            
            void printReducedGroebnerBasis(bool printBasis=false) const;
            
            std::vector<std::string> getReducedGroebnerBasis() const;
            
            void printReducedGroebnerBasis(string const filename, int64_t modulo) const;
            
            void printMonomialAvl();
            
            void printTaggedPolynomialAvl() const;
            
            void printMatrix (Matrix<Element> & mat, int *tabMon, int *sigma, string const & filename);
            
            
            /* Algorithms */
            
            int simplify (Monomial const & u, int numList);
            
            void update(int index, bool purge, Stat & stat);
            
            void appendMatrixF4 (CriticalPair<Element> & p, int & h, int & nbPiv);
            
            double transform(Matrix<Element> & mat, int *tabMon, int nbPiv, int *tau, int *sigma, int *startTail, int *endCol);
            
            Polynomial<Element> buildPolynomial (Element * row, int *tabMon, int width, int start, int *tau);
            
            void buildPolynomial (Polynomial<Element> & res, Element * row, int *tabMon, int width, int start, int *tau);
            
            void preprocessing(int & width, int & height, int & nbPiv);
            
            bool postprocessing(Matrix<Element> & matrix, int * tabMon, int * sigma, int * tau, int height, int width, int heightReal, int nbPiv, Stat & stat);
            
            
            /* F4 Algorithm */
            
            int f4();
            
            
            
        private:
            std::vector<Polynomial<Element>> _polynomialArray; 
            int _nbVariable; 
            int _numPol; 
            int _numTot; 
            int _numGen; 
            std::vector<int> _total; 
            std::vector<int> _basis; 
            std::vector<TaggedPolynomial<Element>> _taggedPolynomialArray; 
            MonomialArray _monomialArray; 
            AvlCriticalPair<Element> _criticalPairSet; 
            vector<CriticalPair<Element> *> _cpSet0; 
            vector<CriticalPair<Element> *> _cpSet1; 
            vector<CriticalPair<Element> *> _cpSet2; 
            vector<CriticalPair<Element>> _cpArray; 
            AvlMonomial _matMons; 
            AvlPolynomial _matPols; 
    };
}

#include "../src/ideal.inl"
#endif // OPENF4_IDEAL_H