LMCAS::groebner_detail 命名空间参考

命名空间
namespace	anonymous_namespace{solver_groebner_basis.cpp}
namespace	anonymous_namespace{solver_groebner_builder.cpp}
namespace	anonymous_namespace{solver_groebner_reconstruction.cpp}

类
struct	MonomialLess
struct	Poly
class	PolyBuilder
struct	PolyContext
struct	SugarPair
struct	Term

类型定义
using	Monomial = std::vector<int>
using	PolyTerms = std::map<Monomial, Rational, MonomialLess>

函数
Poly	add_poly (const Poly &a, const Poly &b)
void	align_variables (Poly &a, Poly &b)
void	buchberger (std::vector< Poly > &basis, size_t num_vars)
bool	chain_criterion (const std::vector< Poly > &basis, size_t i, size_t j, const std::set< std::pair< size_t, size_t > > &processed_pairs)
int	compute_spoly_sugar (const Poly &f, const Poly &g)
bool	coprime_leading_monomials (const Poly &f, const Poly &g)
Monomial	div_mono (const Monomial &numerator, const Monomial &denominator)
bool	divides_mono (const Monomial &a, const Monomial &b)
void	extend_variables (Poly &polynomial, size_t count)
SymbolicExpr	from_poly_ext (const Poly &polynomial, const PolyContext &context)
Monomial	lcm_mono (const Monomial &a, const Monomial &b)
Monomial	mul_mono (const Monomial &a, const Monomial &b)
Poly	mul_poly (const Poly &a, const Poly &b)
Poly	mul_poly_term (const Poly &polynomial, const Term &term)
Poly	reduce (Poly polynomial, const std::vector< Poly > &basis)
void	reduce_basis (std::vector< Poly > &basis)
std::vector< SymbolicExpr >	reduced_groebner_basis_impl (const std::vector< SymbolicExpr > &polynomials, const std::vector< std::string > &variables, ComputationContext &context)
Poly	s_poly (const Poly &f, const Poly &g)
Poly	sub_poly (const Poly &a, const Poly &b)
Poly	to_poly (const SymbolicExpr &expression, PolyContext &context)

---

类说明

LMCAS::groebner_detail::Term

struct LMCAS::groebner_detail::Term

在文件 solver_groebner_internal.hpp 第 22 行定义.

LMCAS::groebner_detail::Term 的协作图:

类成员
Rational	coeff
Monomial	mono

类型定义说明

Monomial

using LMCAS::groebner_detail::Monomial = std::vector<int>

在文件 solver_groebner_internal.hpp 第 16 行定义.

PolyTerms

using LMCAS::groebner_detail::PolyTerms = std::map<Monomial, Rational, MonomialLess>

在文件 solver_groebner_internal.hpp 第 27 行定义.

函数说明

add_poly()

Poly LMCAS::groebner_detail::add_poly	(	const Poly &	a,
		const Poly &	b )

在文件 solver_groebner_poly.cpp 第 72 行定义.

                                                {
        Poly res = a;
        for (auto const& [m, c] : b.terms) {
            res.add_term(m, c);
        }
        return res;
    }

引用了 LMCAS::a, add_poly(), LMCAS::groebner_detail::Poly::add_term(), LMCAS::b , 以及 LMCAS::c.

被这些函数引用 add_poly() , 以及 LMCAS::groebner_detail::PolyBuilder::visit().

函数调用图:

这是这个函数的调用关系图:

align_variables()

void LMCAS::groebner_detail::align_variables	(	Poly &	a,
		Poly &	b )

在文件 solver_groebner_poly.cpp 第 218 行定义.

                                       {
    if (a.num_vars < b.num_vars) {
        extend_variables(a, b.num_vars);
    } else if (b.num_vars < a.num_vars) {
        extend_variables(b, a.num_vars);
    }
}

引用了 LMCAS::a, align_variables(), LMCAS::b , 以及 extend_variables().

被这些函数引用 align_variables(), LMCAS::groebner_detail::PolyBuilder::visit() , 以及 LMCAS::groebner_detail::PolyBuilder::visit().

函数调用图:

这是这个函数的调用关系图:

buchberger()

void LMCAS::groebner_detail::buchberger	(	std::vector< Poly > &	basis,
		size_t	num_vars )

在文件 solver_groebner_basis.cpp 第 65 行定义.

                                                         {
    initialize_sugar(basis);
    auto pairs = initial_pairs(basis);
    std::set<std::pair<size_t, size_t>> processed_pairs;
    while (!pairs.empty()) {
        auto [i, j, sugar_degree] = pairs.top();
        pairs.pop();
        auto canonical_pair = i < j ? std::make_pair(i, j) : std::make_pair(j, i);
        processed_pairs.insert(canonical_pair);
        if (coprime_leading_monomials(basis[i], basis[j])) continue;
        if (chain_criterion(basis, i, j, processed_pairs)) continue;
        Poly polynomial = s_poly(basis[i], basis[j]);
        extend_variables(polynomial, num_vars);
        Poly remainder = reduce(polynomial, basis);
        if (remainder.is_zero()) continue;
        remainder.sugar = sugar_degree;
        size_t new_index = basis.size();
        basis.push_back(remainder);
        for (size_t k = 0; k < new_index; ++k) {
            pairs.push({k, new_index, compute_spoly_sugar(basis[k], basis[new_index])});
        }
    }
}

引用了 LMCAS::basis, buchberger(), chain_criterion(), compute_spoly_sugar(), coprime_leading_monomials(), extend_variables(), LMCAS::groebner_detail::Poly::is_zero(), reduce(), s_poly() , 以及 LMCAS::groebner_detail::Poly::sugar.

被这些函数引用 buchberger() , 以及 reduced_groebner_basis_impl().

函数调用图:

这是这个函数的调用关系图:

chain_criterion()

bool LMCAS::groebner_detail::chain_criterion	(	const std::vector< Poly > &	basis,
		size_t	i,
		size_t	j,
		const std::set< std::pair< size_t, size_t > > &	processed_pairs )

在文件 solver_groebner_poly.cpp 第 168 行定义.

                                                                                {
        Monomial L = lcm_mono(G[i].lead_monomial(), G[j].lead_monomial());
        for (size_t k = 0; k < G.size(); ++k) {
            if (k == i || k == j) {
                continue;
            }
            if (G[k].is_zero()) {
                continue;
            }
            if (divides_mono(G[k].lead_monomial(), L)) {
                auto pair_ik = (i < k) ? std::make_pair(i, k) : std::make_pair(k, i);
                auto pair_kj = (k < j) ? std::make_pair(k, j) : std::make_pair(j, k);
                if (processed_pairs.count(pair_ik) && processed_pairs.count(pair_kj)) {
                    return true;
                }
            }
        }
        return false;
    }

引用了 chain_criterion(), divides_mono() , 以及 lcm_mono().

被这些函数引用 buchberger() , 以及 chain_criterion().

函数调用图:

这是这个函数的调用关系图:

compute_spoly_sugar()

int LMCAS::groebner_detail::compute_spoly_sugar	(	const Poly &	f,
		const Poly &	g )

在文件 solver_groebner_poly.cpp 第 189 行定义.

                                                          {
        Monomial L = lcm_mono(f.lead_monomial(), g.lead_monomial());
 
        int deg_L = 0;
        for (int e : L) deg_L += e;
 
        int deg_lm_f = 0;
        for (int e : f.lead_monomial()) deg_lm_f += e;
 
        int deg_lm_g = 0;
        for (int e : g.lead_monomial()) deg_lm_g += e;
 
        int sugar_f = f.sugar + deg_L - deg_lm_f;
        int sugar_g = g.sugar + deg_L - deg_lm_g;
 
        return std::max(sugar_f, sugar_g);
    }

引用了 compute_spoly_sugar(), LMCAS::e(), lcm_mono(), LMCAS::groebner_detail::Poly::lead_monomial() , 以及 LMCAS::groebner_detail::Poly::sugar.

被这些函数引用 buchberger(), compute_spoly_sugar() , 以及 LMCAS::groebner_detail::anonymous_namespace{solver_groebner_basis.cpp}::initial_pairs().

函数调用图:

这是这个函数的调用关系图:

coprime_leading_monomials()

bool LMCAS::groebner_detail::coprime_leading_monomials	(	const Poly &	f,
		const Poly &	g )

在文件 solver_groebner_poly.cpp 第 154 行定义.

                                                                 {
        if (f.is_zero() || g.is_zero()) {
            return false;
        }
        const Monomial& lm_f = f.lead_monomial();
        const Monomial& lm_g = g.lead_monomial();
        for (size_t i = 0; i < lm_f.size() && i < lm_g.size(); ++i) {
            if (lm_f[i] > 0 && lm_g[i] > 0) {
                return false;
            }
        }
        return true;
    }

引用了 coprime_leading_monomials(), LMCAS::groebner_detail::Poly::is_zero() , 以及 LMCAS::groebner_detail::Poly::lead_monomial().

被这些函数引用 buchberger() , 以及 coprime_leading_monomials().

函数调用图:

这是这个函数的调用关系图:

div_mono()

Monomial LMCAS::groebner_detail::div_mono	(	const Monomial &	numerator,
		const Monomial &	denominator )

在文件 solver_groebner_poly.cpp 第 66 行定义.

                                                                {
        Monomial res(num.size());
        for (size_t i = 0; i < num.size(); ++i) res[i] = num[i] - den[i];
        return res;
    }

引用了 div_mono() , 以及 LMCAS::polynomial_solver_detail::num().

被这些函数引用 div_mono(), reduce() , 以及 s_poly().

函数调用图:

这是这个函数的调用关系图:

divides_mono()

bool LMCAS::groebner_detail::divides_mono	(	const Monomial &	a,
		const Monomial &	b )

在文件 solver_groebner_poly.cpp 第 59 行定义.

                                                            {
        for (size_t i = 0; i < a.size(); ++i) {
            if (a[i] > b[i]) return false;
        }
        return true;
    }

引用了 LMCAS::a, LMCAS::b , 以及 divides_mono().

被这些函数引用 chain_criterion(), divides_mono(), LMCAS::groebner_detail::anonymous_namespace{solver_groebner_basis.cpp}::minimal_basis() , 以及 reduce().

函数调用图:

这是这个函数的调用关系图:

extend_variables()

void LMCAS::groebner_detail::extend_variables	(	Poly &	polynomial,
		size_t	count )

在文件 solver_groebner_poly.cpp 第 207 行定义.

                                                      {
    if (polynomial.num_vars >= count) return;
    Poly extended(count);
    for (const auto& [monomial, coefficient] : polynomial.terms) {
        Monomial resized = monomial;
        resized.resize(count, 0);
        extended.add_term(resized, coefficient);
    }
    polynomial = std::move(extended);
}

引用了 LMCAS::groebner_detail::Poly::add_term(), extend_variables(), LMCAS::groebner_detail::Poly::num_vars , 以及 LMCAS::groebner_detail::Poly::terms.

被这些函数引用 align_variables(), buchberger(), LMCAS::anonymous_namespace{solver_groebner.cpp}::extend_basis(), extend_variables() , 以及 LMCAS::groebner_detail::PolyBuilder::visit().

函数调用图:

这是这个函数的调用关系图:

from_poly_ext()

SymbolicExpr LMCAS::groebner_detail::from_poly_ext	(	const Poly &	polynomial,
		const PolyContext &	context )

在文件 solver_groebner_reconstruction.cpp 第 38 行定义.

                                                        {
    if (polynomial.terms.empty()) {
        return LMCAS::detail::expression_from_node(SymbolicFactory::create_number(BigInt(0)));
    }
    std::vector<std::shared_ptr<const SymbolicNode>> terms;
    for (const auto& [monomial, coefficient] : polynomial.terms) {
        terms.push_back(term_node(monomial, coefficient, context));
    }
    if (terms.size() == 1) return LMCAS::detail::expression_from_node(terms[0]);
    return LMCAS::detail::expression_from_node(SymbolicFactory::create_add(terms));
}

引用了 LMCAS::context, LMCAS::SymbolicFactory::create_add(), LMCAS::SymbolicFactory::create_number(), LMCAS::detail::expression_from_node(), from_poly_ext() , 以及 LMCAS::groebner_detail::Poly::terms.

被这些函数引用 from_poly_ext() , 以及 LMCAS::anonymous_namespace{solver_groebner.cpp}::reconstruct_basis().

函数调用图:

这是这个函数的调用关系图:

lcm_mono()

Monomial LMCAS::groebner_detail::lcm_mono	(	const Monomial &	a,
		const Monomial &	b )

在文件 solver_groebner_poly.cpp 第 53 行定义.

                                                            {
        Monomial res(a.size());
        for (size_t i = 0; i < a.size(); ++i) res[i] = std::max(a[i], b[i]);
        return res;
    }

引用了 LMCAS::a, LMCAS::b , 以及 lcm_mono().

被这些函数引用 chain_criterion(), compute_spoly_sugar(), lcm_mono() , 以及 s_poly().

函数调用图:

这是这个函数的调用关系图:

mul_mono()

Monomial LMCAS::groebner_detail::mul_mono	(	const Monomial &	a,
		const Monomial &	b )

在文件 solver_groebner_poly.cpp 第 47 行定义.

                                                            {
        Monomial res(a.size());
        for (size_t i = 0; i < a.size(); ++i) res[i] = a[i] + b[i];
        return res;
    }

引用了 LMCAS::a, LMCAS::b , 以及 mul_mono().

被这些函数引用 mul_mono(), mul_poly() , 以及 mul_poly_term().

函数调用图:

这是这个函数的调用关系图:

mul_poly()

Poly LMCAS::groebner_detail::mul_poly	(	const Poly &	a,
		const Poly &	b )

在文件 solver_groebner_poly.cpp 第 99 行定义.

                                                {
        Poly res(a.num_vars);
        for (auto const& [ma, ca] : a.terms) {
            for (auto const& [mb, cb] : b.terms) {
                res.add_term(mul_mono(ma, mb), ca * cb);
            }
        }
        return res;
    }

引用了 LMCAS::a, LMCAS::groebner_detail::Poly::add_term(), LMCAS::b, mul_mono() , 以及 mul_poly().

被这些函数引用 mul_poly(), LMCAS::groebner_detail::PolyBuilder::visit() , 以及 LMCAS::groebner_detail::PolyBuilder::visit().

函数调用图:

这是这个函数的调用关系图:

mul_poly_term()

Poly LMCAS::groebner_detail::mul_poly_term	(	const Poly &	polynomial,
		const Term &	term )

在文件 solver_groebner_poly.cpp 第 90 行定义.

                                                     {
        Poly res(p.num_vars);
        if (t.coeff == Rational(0)) return res;
        for (auto const& [m, c] : p.terms) {
            res.add_term(mul_mono(m, t.mono), c * t.coeff);
        }
        return res;
    }

引用了 LMCAS::groebner_detail::Poly::add_term(), LMCAS::c, mul_mono(), mul_poly_term(), LMCAS::groebner_detail::Poly::num_vars, LMCAS::t , 以及 LMCAS::groebner_detail::Poly::terms.

被这些函数引用 mul_poly_term(), reduce() , 以及 s_poly().

函数调用图:

这是这个函数的调用关系图:

reduce()

Poly LMCAS::groebner_detail::reduce	(	Poly	polynomial,
		const std::vector< Poly > &	basis )

在文件 solver_groebner_poly.cpp 第 109 行定义.

                                                  {
        Poly r(p.num_vars);
 
        while (!p.is_zero()) {
            bool reduced = false;
            Monomial p_lm = p.lead_monomial();
 
            for (const auto& g : G) {
                if (divides_mono(g.lead_monomial(), p_lm)) {
 
                    Term factor;
                    factor.coeff = p.lead_coeff() / g.lead_coeff();
                    factor.mono = div_mono(p_lm, g.lead_monomial());
 
                    Poly term_g = mul_poly_term(g, factor);
                    p = sub_poly(p, term_g);
                    reduced = true;
                    break;
                }
            }
 
            if (!reduced) {
                Term lt = p.lead_term();
                r.add_term(lt.mono, lt.coeff);
 
                p.terms.erase(p.terms.begin());
            }
        }
        return r;
    }

引用了 LMCAS::groebner_detail::Term::coeff, div_mono(), divides_mono(), LMCAS::groebner_detail::Poly::is_zero(), LMCAS::groebner_detail::Poly::lead_coeff(), LMCAS::groebner_detail::Poly::lead_monomial(), LMCAS::groebner_detail::Poly::lead_term(), LMCAS::lt(), LMCAS::groebner_detail::Term::mono, mul_poly_term(), LMCAS::groebner_detail::Poly::num_vars, LMCAS::r, reduce(), sub_poly() , 以及 LMCAS::groebner_detail::Poly::terms.

被这些函数引用 buchberger(), reduce() , 以及 reduce_basis().

函数调用图:

这是这个函数的调用关系图:

reduce_basis()

void LMCAS::groebner_detail::reduce_basis

(

std::vector< Poly > &

basis

)

在文件 solver_groebner_basis.cpp 第 89 行定义.

                                          {
    auto minimal = minimal_basis(basis);
    for (size_t i = 0; i < minimal.size(); ++i) {
        std::vector<Poly> others;
        for (size_t j = 0; j < minimal.size(); ++j) {
            if (j != i) others.push_back(minimal[j]);
        }
        minimal[i] = reduce(minimal[i], others);
    }
    std::vector<Poly> reduced;
    for (const auto& polynomial : minimal) {
        if (!polynomial.is_zero()) reduced.push_back(polynomial);
    }
    for (auto& polynomial : reduced) make_monic(polynomial);
    basis = std::move(reduced);
}

引用了 LMCAS::basis, reduce() , 以及 reduce_basis().

被这些函数引用 reduce_basis() , 以及 reduced_groebner_basis_impl().

函数调用图:

这是这个函数的调用关系图:

reduced_groebner_basis_impl()

std::vector< SymbolicExpr > LMCAS::groebner_detail::reduced_groebner_basis_impl	(	const std::vector< SymbolicExpr > &	polynomials,
		const std::vector< std::string > &	variables,
		ComputationContext &	context )

在文件 solver_groebner.cpp 第 50 行定义.

                                                                            {
    PolyContext context(variables, computation);
    auto basis = convert_polynomials(polynomials, context);
    extend_basis(basis, context.ext_vars.size());
    buchberger(basis, context.ext_vars.size());
    reduce_basis(basis);
    return reconstruct_basis(basis, context);
}

引用了 LMCAS::basis, buchberger(), LMCAS::context , 以及 reduce_basis().

被这些函数引用 LMCAS::anonymous_namespace{solver_groebner_system.cpp}::simplified_basis().

函数调用图:

这是这个函数的调用关系图:

s_poly()

Poly LMCAS::groebner_detail::s_poly	(	const Poly &	f,
		const Poly &	g )

在文件 solver_groebner_poly.cpp 第 140 行定义.

                                              {
        Monomial L = lcm_mono(f.lead_monomial(), g.lead_monomial());
 
        Term t1;
        t1.mono = div_mono(L, f.lead_monomial());
        t1.coeff = Rational(1) / f.lead_coeff();
 
        Term t2;
        t2.mono = div_mono(L, g.lead_monomial());
        t2.coeff = Rational(1) / g.lead_coeff();
 
        return sub_poly(mul_poly_term(f, t1), mul_poly_term(g, t2));
    }

引用了 LMCAS::groebner_detail::Term::coeff, div_mono(), lcm_mono(), LMCAS::groebner_detail::Poly::lead_coeff(), LMCAS::groebner_detail::Poly::lead_monomial(), LMCAS::groebner_detail::Term::mono, mul_poly_term(), s_poly() , 以及 sub_poly().

被这些函数引用 buchberger() , 以及 s_poly().

函数调用图:

这是这个函数的调用关系图:

sub_poly()

Poly LMCAS::groebner_detail::sub_poly	(	const Poly &	a,
		const Poly &	b )

在文件 solver_groebner_poly.cpp 第 80 行定义.

                                                {
        Poly res = a;
        for (auto const& [m, c] : b.terms) {
 
            Rational c_neg = c * Rational(-1);
            res.add_term(m, c_neg);
        }
        return res;
    }

引用了 LMCAS::a, LMCAS::groebner_detail::Poly::add_term(), LMCAS::b, LMCAS::c , 以及 sub_poly().

被这些函数引用 reduce(), s_poly() , 以及 sub_poly().

函数调用图:

这是这个函数的调用关系图:

to_poly()

Poly LMCAS::groebner_detail::to_poly	(	const SymbolicExpr &	expression,
		PolyContext &	context )

在文件 solver_groebner_conversion.cpp 第 144 行定义.

                                                             {
        PolyBuilder b(ctx.ext_vars, ctx);
        LMCAS::detail::node(expr)->accept(b);
        return b.get_result();
    }

引用了 LMCAS::b, LMCAS::groebner_detail::PolyContext::ext_vars, LMCAS::detail::node() , 以及 to_poly().

被这些函数引用 LMCAS::anonymous_namespace{solver_groebner.cpp}::convert_polynomials() , 以及 to_poly().

函数调用图:

这是这个函数的调用关系图: