algorithm_buchberger_dynamic.hpp

#ifndef __ALGORITHM_BUCHBERGER_DYNAMIC_HPP_
#define __ALGORITHM_BUCHBERGER_DYNAMIC_HPP_

/*****************************************************************************\
* This file is part of DynGB.                                                 *
*                                                                             *
* DynGB 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 2 of the License, or           *
* (at your option) any later version.                                         *
*                                                                             *
* DynGB 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 DynGB. If not, see <http://www.gnu.org/licenses/>.               *
\*****************************************************************************/

#include <set>
#include <list>
#include <iostream>

using std::list;
using std::cout; using std::endl;
using std::set;

#include "system_constants.hpp"

#include "fields.hpp"
#include "monomial.hpp"
#include "polynomial.hpp"
#include "critical_pair.hpp"
#include "normal_strategy.hpp"
#include "polynomial_array.hpp"
#include "polynomial_geobucket.hpp"
#include "polynomial_linked_list.hpp"
#include "polynomial_double_buffered.hpp"

#include "sugar_strategy.hpp"
#include "weighted_sugar_strategy.hpp"

#include "dynamic_engine.hpp"
using Dynamic_Engine::Dynamic_Heuristic;

/**
  @defgroup GBComputation Gr&ouml;bner basis computation
  @brief classes related directly to Gr&ouml;bner basis computation
*/

/**
  @brief Reduce the polynomial r over the basis G.
  @ingroup GBComputation
  @param sp the s-polynomial to reduce
  @param G a set of reducers, usually the generators of an ideal
  @details This is a complete reduction, not just the head,
  so the value of *sp may change.
*/
void reduce_over_basis_dynamic(
    Mutable_Polynomial **sp, const list<Abstract_Polynomial *> G
);

/**
  @ingroup GBComputation
  @author John Perry
  @date 2017
  @brief used by buchberger_dynamic() to decide which solver to use
  @details Current options include:
      - SKELETON_SOLVER use the Skeleton class for an exact skeleton
      - GLPK_SOLVER, use the GLPK_Solver for an approximate skeleton
      - PPL_SOLVER, use the PPL_Solver for an exact skeleton
      - GLPK_ORACLE_SOLVER, use the GLPK_Solver to determine quickly
        if a solution exists, and use Skeleton only when the solution
        does in fact exist (idea due to D. Lichtblau)
*/
enum DynamicSolver {
  SKELETON_SOLVER = 1,
  GLPK_SOLVER,
  PPL_SOLVER,
  GLPK_ORACLE_SOLVER
};

/**
  @brief perform a deep analysis of the input polynomials and select an ordering
    that seems advantageous
  @param F set of input polynomials
  @param mord a Monomial_Ordering; do not initialize, as this will create and
    store the ordering in the parameter
  @param solver which LP_Solver to use; this needs to be created already
*/
void initial_analysis(
    const list<Abstract_Polynomial *> & F,
    Monomial_Ordering ** mord,
    LP_Solver * solver
);

/**
  @brief implementation of the dynamic Buchberger algorithm
  @ingroup GBComputation
  @param F generators of a polynomial ideal
  @param method how to represent the S-polynomials during reduction
  @param strategy strategy to use while sorting pairs
  @param strategy_weights used by @c strategy
  @param heuristic see Dynamic_Heuristic
  @param solver how to compute possible monomial orderings (polyhedral skeleton)
  @param analyze_inputs set to @c true if you want the solver to analyze the
      inputs to find an initial ordering (see notes)
  @return a Gr&ouml;bner basis of the ideal generated by @p F
  @details Upon termination, every polynomial in the basis should be sorted
    according to the same ordering, so the eventual ordering will be listed
    there.
  @note It is highly advisable to sort @p F by increasing degree
    before passing it to this function, as the algorithm starts from the first
    polynomial. This is an effective preprocessing technique
    that is equivalent to the standard Hilbert heuristic, since a monomial of
    degree @f$ d @f$ will have Hilbert numerator @f$ \lambda^d - 1 @f$.
    The other effective heuristics (minimum critical pairs, incremental Betti
    numbers) do not make sense with an empty basis.
  @note If desired, the algorithm can analyze the inputs to find a good global
    ordering. To do this, set @p analyze_inputs to @c true. This is probably a
    waste of time input polynomials where many polynomials can be reduced by
    others, so the default is @c false.
*/
list<Abstract_Polynomial *> buchberger_dynamic(
    const list<Abstract_Polynomial *> &F,
    SPolyCreationFlags method = SPolyCreationFlags::GEOBUCKETS,
    StrategyFlags strategy = StrategyFlags::SUGAR_STRATEGY,
    WT_TYPE * strategy_weights = nullptr,
    Dynamic_Heuristic heuristic = Dynamic_Heuristic::ORD_HILBERT_THEN_DEG,
    DynamicSolver solver = SKELETON_SOLVER,
    bool analyze_inputs = false
);

/**
  @brief implementation of Gebauer-M&ouml;ller algorithm,
      adjusted for dynamic computation
  @details Based on description in Becker and Weispfenning (1993).
  @ingroup GBComputation
  @param P list of critical pairs
  @param G current basis
  @param r polynomial to add to basis (and to generate new pairs)
  @param strategy how to sort pairs
  @param ordering current ordering in the basis
*/
void gm_update_dynamic(
    list<Critical_Pair_Dynamic *> & P,
    list<Abstract_Polynomial *> & G,
    Abstract_Polynomial * r,
    StrategyFlags strategy,
    ORDERING_TYPE * ordering
);

#endif