LMCAS::anonymous_namespace{solver_groebner_system.cpp} 命名空间参考

类
class	PolynomialSystemSearch

类型定义
using	Expressions = std::vector<std::shared_ptr<SymbolicExpr>>
using	PolynomialSolution = std::map<std::string, SymbolicExpr>
using	PolynomialSolutions = std::vector<PolynomialSolution>

函数
std::shared_ptr< SymbolicExpr >	clear_denominators (const SymbolicExpr &equation, Expressions &constraints, ComputationContext &context)
Result< groebner_detail::Poly >	convert_basis_polynomial (const SymbolicExpr &polynomial, const std::vector< std::string > &variables, groebner_detail::PolyContext &conversion, ComputationContext &context, std::shared_ptr< SymbolicExpr > &simplified)
PolynomialSystemResult	filter_denominators (PolynomialSolutions candidates, const Expressions &constraints, ComputationContext &context)
Result< Expressions >	simplified_basis (const std::vector< SymbolicExpr > &equations, const std::vector< std::string > &variables, ComputationContext &context)
PolynomialSystemResult	solve_polynomial_system_impl (const std::vector< SymbolicExpr > &equations, const std::vector< std::string > &variables, ComputationContext &context)
PolynomialSystemResult	solve_single_equation (const SymbolicExpr &equation, const std::string &variable, ComputationContext &context)
std::shared_ptr< SymbolicExpr >	substitute_solution (const std::shared_ptr< SymbolicExpr > &expression, const PolynomialSolution &solution, ComputationContext &context)
Result< void >	validate_basis_input (const std::vector< SymbolicExpr > &equations, const std::vector< std::string > &variables, groebner_detail::PolyContext &conversion, ComputationContext &context)

类型定义说明

Expressions

using LMCAS::anonymous_namespace{solver_groebner_system.cpp}::Expressions = std::vector<std::shared_ptr<SymbolicExpr>>

在文件 solver_groebner_system.cpp 第 21 行定义.

PolynomialSolution

using LMCAS::anonymous_namespace{solver_groebner_system.cpp}::PolynomialSolution = std::map<std::string, SymbolicExpr>

在文件 solver_groebner_system.cpp 第 19 行定义.

PolynomialSolutions

using LMCAS::anonymous_namespace{solver_groebner_system.cpp}::PolynomialSolutions = std::vector<PolynomialSolution>

在文件 solver_groebner_system.cpp 第 20 行定义.

函数说明

clear_denominators()

std::shared_ptr< SymbolicExpr > LMCAS::anonymous_namespace{solver_groebner_system.cpp}::clear_denominators	(	const SymbolicExpr &	equation,
		Expressions &	constraints,
		ComputationContext &	context )

在文件 solver_groebner_system.cpp 第 23 行定义.

                                                                                         {
 
    detail::RewriteBudget transform_budget(context, (context).limits().max_recursion_depth,
                                            (context).limits().max_ast_nodes, "transform");
    if (!detail::node(equation)) return nullptr;
    std::vector<std::shared_ptr<const SymbolicNode>> factors;
    Expressions local_constraints;
    if (!collect_denominator_factors(detail::node(equation), factors, local_constraints)) {
        return nullptr;
    }
    auto cleared = to_ptr(equation);
    if (factors.empty()) {
        cleared = detail::make_expression_ptr(detail::normalize_node(detail::node(cleared), transform_budget));
    } else if (auto sum = std::dynamic_pointer_cast<const AddNode>(detail::node(cleared))) {
        std::vector<std::shared_ptr<const SymbolicNode>> terms;
        terms.reserve(sum->operands().size());
        for (const auto& term : sum->operands()) {
            auto product = multiply_no_expand(term, factors);
            terms.push_back(detail::node(product));
        }
        cleared = detail::make_expression_ptr(detail::make_node<AddNode>(terms));
    } else {
        cleared = multiply_no_expand(detail::node(cleared), factors);
    }
    if (!cleared || !detail::node(cleared) || !is_polynomial_node(detail::node(cleared))) {
        return nullptr;
    }
    for (const auto& constraint : local_constraints) constraints.push_back(constraint);
    return cleared;
}

引用了 clear_denominators(), LMCAS::solver_detail::collect_denominator_factors(), LMCAS::context, LMCAS::solver_detail::is_polynomial_node(), LMCAS::detail::make_expression_ptr(), LMCAS::detail::make_node(), LMCAS::solver_detail::multiply_no_expand(), LMCAS::detail::node(), LMCAS::detail::normalize_node() , 以及 LMCAS::solver_detail::to_ptr().

被这些函数引用 clear_denominators() , 以及 solve_polynomial_system_impl().

函数调用图:

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

convert_basis_polynomial()

Result< groebner_detail::Poly > LMCAS::anonymous_namespace{solver_groebner_system.cpp}::convert_basis_polynomial	(	const SymbolicExpr &	polynomial,
		const std::vector< std::string > &	variables,
		groebner_detail::PolyContext &	conversion,
		ComputationContext &	context,
		std::shared_ptr< SymbolicExpr > &	simplified )

在文件 solver_groebner_system.cpp 第 120 行定义.

                                                 {
    detail::RewriteBudget transform_budget(context, (context).limits().max_recursion_depth,
                                            (context).limits().max_ast_nodes, "transform");
    constexpr const char* operation = "solve_polynomial_system";
    auto budget = context.consume_steps(1, operation);
    if (!budget) return Result<groebner_detail::Poly>::failure(budget.error());
    simplified = detail::make_expression_ptr(detail::normalize_node(detail::node(polynomial), transform_budget));
    if (!simplified) return Result<groebner_detail::Poly>::failure(
        CasErrc::Inconclusive, "basis polynomial cannot be converted", operation);
    groebner_detail::PolyBuilder builder(variables, conversion, true);
    detail::node(simplified)->accept(builder);
    if (builder.failed) return Result<groebner_detail::Poly>::failure(
        CasErrc::Inconclusive, "basis polynomial cannot be converted", operation);
    return builder.get_result();
} catch (const CasError& error) {
    return Result<groebner_detail::Poly>::failure(error);
} catch (const std::bad_alloc&) {
    return Result<groebner_detail::Poly>::failure(CasErrc::ResourceLimit, "allocation failed", "solve_polynomial_system");
} catch (const std::length_error& error) {
    return Result<groebner_detail::Poly>::failure(CasErrc::ResourceLimit, error.what(), "solve_polynomial_system");
} catch (const std::exception& error) {
    return Result<groebner_detail::Poly>::failure(CasErrc::InternalInvariant, error.what(), "solve_polynomial_system");
}

引用了 LMCAS::SymbolicNode::accept(), LMCAS::context, convert_basis_polynomial(), LMCAS::groebner_detail::PolyBuilder::failed, LMCAS::Result< T >::failure(), LMCAS::groebner_detail::PolyBuilder::get_result(), LMCAS::Inconclusive, LMCAS::detail::make_expression_ptr(), LMCAS::detail::node() , 以及 LMCAS::detail::normalize_node().

被这些函数引用 convert_basis_polynomial() , 以及 simplified_basis().

函数调用图:

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

filter_denominators()

PolynomialSystemResult LMCAS::anonymous_namespace{solver_groebner_system.cpp}::filter_denominators	(	PolynomialSolutions	candidates,
		const Expressions &	constraints,
		ComputationContext &	context )

在文件 solver_groebner_system.cpp 第 68 行定义.

                                                                 {
    std::optional<detail::AssumptionFacts> adapter;
    if (context.assumptions()) adapter.emplace(*context.assumptions());
    const FactsQuery& facts = adapter ? static_cast<const FactsQuery&>(*adapter) : detail::no_facts();
    PolynomialSolutions filtered;
    filtered.reserve(candidates.size());
    for (auto& solution : candidates) {
        bool valid = true;
        for (const auto& denominator : constraints) {
            auto bound = substitute_solution(denominator, solution, context);
            if (!bound) return PolynomialSystemResult::failure(CasErrc::InternalInvariant,
                "denominator substitution failed", "solve_polynomial_system");
            auto nonzero = detail::query_nonzero_value(detail::node(bound), facts, Domain::Complex, context);
            if (!nonzero) return PolynomialSystemResult::failure(nonzero.error());
            if (nonzero.value() == Tribool::False) { valid = false; break; }
            if (nonzero.value() != Tribool::True)
                return PolynomialSystemResult::failure(CasErrc::Inconclusive,
                    "candidate denominator is not proved nonzero", "solve_polynomial_system");
        }
        if (valid) filtered.push_back(std::move(solution));
    }
    return filtered;
}

引用了 LMCAS::Complex, LMCAS::context, LMCAS::denominator, LMCAS::Result< std::vector< std::map< std::string, SymbolicExpr > > >::failure(), LMCAS::False, filter_denominators(), LMCAS::Inconclusive, LMCAS::InternalInvariant, LMCAS::detail::no_facts(), LMCAS::detail::node(), LMCAS::detail::query_nonzero_value(), substitute_solution() , 以及 LMCAS::True.

被这些函数引用 filter_denominators() , 以及 solve_polynomial_system_impl().

函数调用图:

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

simplified_basis()

Result< Expressions > LMCAS::anonymous_namespace{solver_groebner_system.cpp}::simplified_basis	(	const std::vector< SymbolicExpr > &	equations,
		const std::vector< std::string > &	variables,
		ComputationContext &	context )

在文件 solver_groebner_system.cpp 第 147 行定义.

                                                                  {
    constexpr const char* operation = "solve_polynomial_system";
    groebner_detail::PolyContext conversion(variables, context);
    auto validated = validate_basis_input(equations, variables, conversion, context);
    if (!validated) return Result<Expressions>::failure(validated.error());
    auto groebner = groebner_detail::reduced_groebner_basis_impl(equations, variables, context);
    Expressions basis;
    std::vector<FGLMPoly> leading;
    basis.reserve(groebner.size());
    leading.reserve(groebner.size());
    for (const auto& polynomial : groebner) {
        std::shared_ptr<SymbolicExpr> simplified;
        auto converted = convert_basis_polynomial(polynomial, variables, conversion, context, simplified);
        if (!converted) return Result<Expressions>::failure(converted.error());
        if (simplified->is_number() && !simplified->is_zero()) return Expressions{simplified};
        if (converted.value().is_zero()) continue;
        FGLMPoly term(variables.size());
        term.add_term(converted.value().lead_monomial(), converted.value().lead_coeff());
        leading.push_back(std::move(term));
        basis.push_back(std::move(simplified));
    }
    if (!is_zero_dimensional(leading, variables.size())) {
        return Result<Expressions>::failure(CasErrc::Inconclusive,
            "polynomial system has no certified finite solution set", operation);
    }
    return basis;
}

引用了 LMCAS::basis, LMCAS::context, convert_basis_polynomial(), LMCAS::Result< T >::failure(), LMCAS::Inconclusive, LMCAS::is_zero_dimensional(), LMCAS::groebner_detail::reduced_groebner_basis_impl(), simplified_basis() , 以及 validate_basis_input().

被这些函数引用 simplified_basis() , 以及 solve_polynomial_system_impl().

函数调用图:

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

solve_polynomial_system_impl()

PolynomialSystemResult LMCAS::anonymous_namespace{solver_groebner_system.cpp}::solve_polynomial_system_impl	(	const std::vector< SymbolicExpr > &	equations,
		const std::vector< std::string > &	variables,
		ComputationContext &	context )

在文件 solver_groebner_system.cpp 第 290 行定义.

                                                                        {
    std::vector<SymbolicExpr> cleared_equations;
    Expressions constraints;
    cleared_equations.reserve(equations.size());
    for (const auto& equation : equations) {
        auto cleared = clear_denominators(equation, constraints, context);
        if (!cleared) return PolynomialSystemResult::failure(CasErrc::Inconclusive,
            "equation cannot be converted to a polynomial without losing its domain", "solve_polynomial_system");
        cleared_equations.push_back(*cleared);
    }
    if (cleared_equations.size() == 1 && variables.size() == 1) {
        auto solved = solve_single_equation(cleared_equations[0], variables[0], context);
        if (!solved) return solved;
        return filter_denominators(std::move(solved.value()), constraints, context);
    }
    auto basis = simplified_basis(cleared_equations, variables, context);
    if (!basis) return PolynomialSystemResult::failure(basis.error());
    if (basis.value().size() == 1 && basis.value().front()->is_number() &&
        !basis.value().front()->is_zero()) return PolynomialSolutions{};
    PolynomialSystemSearch search(basis.value(), variables, context);
    auto solved = search.solve(static_cast<int>(variables.size()) - 1, PolynomialSolution{});
    if (!solved) return solved;
    return filter_denominators(std::move(solved.value()), constraints, context);
}

引用了 LMCAS::basis, clear_denominators(), LMCAS::context, LMCAS::Result< std::vector< std::map< std::string, SymbolicExpr > > >::failure(), filter_denominators(), LMCAS::Inconclusive, simplified_basis(), LMCAS::anonymous_namespace{solver_groebner_system.cpp}::PolynomialSystemSearch::solve(), solve_polynomial_system_impl() , 以及 solve_single_equation().

被这些函数引用 solve_polynomial_system_impl().

函数调用图:

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

solve_single_equation()

PolynomialSystemResult LMCAS::anonymous_namespace{solver_groebner_system.cpp}::solve_single_equation	(	const SymbolicExpr &	equation,
		const std::string &	variable,
		ComputationContext &	context )

在文件 solver_groebner_system.cpp 第 93 行定义.

                                                                         {
    auto solved = solve_finite_checked(detail::make_expression_ptr(equation),
                                       variable, context, SolveOptions{});
    if (!solved) return PolynomialSystemResult::failure(solved.error());
    PolynomialSolutions solutions;
    for (const auto& root : solved.value()) solutions.push_back({{variable, *root}});
    return solutions;
}

引用了 LMCAS::context, LMCAS::Result< std::vector< std::map< std::string, SymbolicExpr > > >::failure(), LMCAS::detail::make_expression_ptr(), LMCAS::solve_finite_checked(), solve_single_equation() , 以及 LMCAS::variable.

被这些函数引用 solve_polynomial_system_impl() , 以及 solve_single_equation().

函数调用图:

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

substitute_solution()

std::shared_ptr< SymbolicExpr > LMCAS::anonymous_namespace{solver_groebner_system.cpp}::substitute_solution	(	const std::shared_ptr< SymbolicExpr > &	expression,
		const PolynomialSolution &	solution,
		ComputationContext &	context )

在文件 solver_groebner_system.cpp 第 55 行定义.

                                                                                                                    {
 
    detail::RewriteBudget transform_budget(context, (context).limits().max_recursion_depth,
                                            (context).limits().max_ast_nodes, "transform");
    auto result = expression;
    for (const auto& [name, value] : solution) {
        result = detail::make_expression_ptr(detail::substitute_node(detail::node(result), name, detail::node(value), transform_budget));
        if (!result) return nullptr;
    }
    return detail::make_expression_ptr(detail::normalize_node(detail::node(result), transform_budget));
}

引用了 LMCAS::context, LMCAS::detail::make_expression_ptr(), LMCAS::name, LMCAS::detail::node(), LMCAS::detail::normalize_node(), LMCAS::detail::substitute_node(), substitute_solution() , 以及 LMCAS::value.

被这些函数引用 filter_denominators(), LMCAS::anonymous_namespace{solver_groebner_system.cpp}::PolynomialSystemSearch::substitute_basis() , 以及 substitute_solution().

函数调用图:

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

validate_basis_input()

Result< void > LMCAS::anonymous_namespace{solver_groebner_system.cpp}::validate_basis_input	(	const std::vector< SymbolicExpr > &	equations,
		const std::vector< std::string > &	variables,
		groebner_detail::PolyContext &	conversion,
		ComputationContext &	context )

在文件 solver_groebner_system.cpp 第 104 行定义.

                                                               {
    constexpr const char* operation = "solve_polynomial_system";
    for (const auto& equation : equations) {
        auto budget = context.consume_steps(1, operation);
        if (!budget) return Result<void>::failure(budget.error());
        groebner_detail::PolyBuilder builder(variables, conversion, true);
        detail::node(equation)->accept(builder);
        if (builder.failed) return Result<void>::failure(
            CasErrc::Inconclusive, "equation is not an exact polynomial in the system variables", operation);
    }
    return Result<void>::success();
}

引用了 LMCAS::SymbolicNode::accept(), LMCAS::context, LMCAS::groebner_detail::PolyBuilder::failed, LMCAS::Result< T >::failure(), LMCAS::Inconclusive, LMCAS::detail::node(), LMCAS::Result< T >::success() , 以及 validate_basis_input().

被这些函数引用 simplified_basis() , 以及 validate_basis_input().

函数调用图:

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