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

类
struct	FactorRecursionGuard

函数
static MultiPoly	embed_univariate_factor (const Polynomial< Rational > &factor, const std::vector< std::string > &variables, const std::string &main_variable)
static MultiFactorCheckedResult	factor_binomial_power (const MultiPoly &poly, const MultiPoly &primitive, const std::string &left_variable, const std::string &right_variable, ComputationContext &context)
static MultiFactorCheckedResult	factor_common_monomial (const MultiPoly &poly, const Monomial &common_monomial, const MultiPoly &quotient, ComputationContext &context)
static MultiFactorCheckedResult	factor_difference_of_squares (const MultiPoly &poly, const std::pair< MultiPoly, MultiPoly > &difference, ComputationContext &context)
static MultiFactorCheckedResult	factor_embedded_univariate (const MultiPoly &poly, const MultiPoly &primitive, const std::string &main_variable, ComputationContext &context)
static MultiFactorCheckedResult	factor_multivariate_impl (const MultiPoly &poly, ComputationContext &context)

函数说明

embed_univariate_factor()

MultiPoly LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::embed_univariate_factor ( const Polynomial< Rational > & factor, const std::vector< std::string > & variables, const std::string & main_variable )

static

在文件 multivariate_factor_checked.cpp 第 91 行定义.

{
    size_t main_index = variables.size();
    for (size_t i = 0; i < variables.size(); ++i) {
        if (variables[i] == main_variable) {
            main_index = i;
            break;
        }
    }
    std::vector<MultiPoly::Term> terms;
    for (size_t degree = 0; degree < factor.coeffs.size(); ++degree) {
        if (factor.coeffs[degree].is_zero()) continue;
        Monomial monomial(variables.size(), 0);
        monomial[main_index] = static_cast<int>(degree);
        terms.emplace_back(std::move(monomial), factor.coeffs[degree]);
    }
    return MultiPoly(std::move(terms), variables);
}

引用了 LMCAS::Polynomial< CoeffType >::coeffs , 以及 embed_univariate_factor().

被这些函数引用 embed_univariate_factor() , 以及 factor_embedded_univariate().

函数调用图:

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

factor_binomial_power()

MultiFactorCheckedResult LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_binomial_power ( const MultiPoly & poly, const MultiPoly & primitive, const std::string & left_variable, const std::string & right_variable, ComputationContext & context )

static

在文件 multivariate_factor_checked.cpp 第 174 行定义.

                                 {
    const auto& variables = poly.variables();
    size_t left_index = 0;
    size_t right_index = 0;
    for (size_t i = 0; i < variables.size(); ++i) {
        if (variables[i] == left_variable) left_index = i;
        if (variables[i] == right_variable) right_index = i;
    }
    Monomial left_monomial(variables.size(), 0);
    Monomial right_monomial(variables.size(), 0);
    left_monomial[left_index] = 1;
    right_monomial[right_index] = 1;
    MultiPoly linear(
        std::vector<MultiPoly::Term>{
            {left_monomial, Rational(1)},
            {right_monomial, Rational(-1)}},
        variables);
    MultiPoly remaining = primitive.exact_div(linear);
    auto sub = factor_multivariate_impl(remaining, context);
    if (!sub) return sub;
    auto sub_value = std::move(sub.value());
    std::vector<MultiPoly> factors = {linear};
    std::vector<int> multiplicities = {1};
    factors.insert(factors.end(),
                   sub_value.value.factors.begin(),
                   sub_value.value.factors.end());
    multiplicities.insert(multiplicities.end(),
                          sub_value.value.multiplicities.begin(),
                          sub_value.value.multiplicities.end());
    return assemble_checked_factorization(
        poly, factors, multiplicities, sub_value.completeness,
        std::move(sub_value.reason));
}

引用了 LMCAS::multivariate_checked_detail::assemble_checked_factorization(), LMCAS::context, factor_binomial_power(), factor_multivariate_impl(), LMCAS::sub() , 以及 LMCAS::Result< T >::value().

被这些函数引用 factor_binomial_power() , 以及 factor_multivariate_impl().

函数调用图:

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

factor_common_monomial()

MultiFactorCheckedResult LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_common_monomial ( const MultiPoly & poly, const Monomial & common_monomial, const MultiPoly & quotient, ComputationContext & context )

static

在文件 multivariate_factor_checked.cpp 第 116 行定义.

                                                            {
    const auto& variables = poly.variables();
    auto sub = factor_multivariate_impl(quotient, context);
    if (!sub) return sub;
    std::vector<MultiPoly> factors;
    std::vector<int> multiplicities;
    for (size_t i = 0; i < common_monomial.size(); ++i) {
        if (common_monomial[i] <= 0) continue;
        Monomial monomial(variables.size(), 0);
        monomial[i] = 1;
        factors.emplace_back(
            std::vector<MultiPoly::Term>{{monomial, Rational(1)}},
            variables);
        multiplicities.push_back(common_monomial[i]);
    }
    auto sub_value = std::move(sub.value());
    factors.insert(factors.end(),
                   sub_value.value.factors.begin(),
                   sub_value.value.factors.end());
    multiplicities.insert(multiplicities.end(),
                          sub_value.value.multiplicities.begin(),
                          sub_value.value.multiplicities.end());
    return assemble_checked_factorization(
        poly, factors, multiplicities, sub_value.completeness,
        std::move(sub_value.reason));
}

引用了 LMCAS::multivariate_checked_detail::assemble_checked_factorization(), LMCAS::context, factor_common_monomial(), factor_multivariate_impl(), LMCAS::sub() , 以及 LMCAS::Result< T >::value().

被这些函数引用 factor_common_monomial() , 以及 factor_multivariate_impl().

函数调用图:

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

factor_difference_of_squares()

MultiFactorCheckedResult LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_difference_of_squares ( const MultiPoly & poly, const std::pair< MultiPoly, MultiPoly > & difference, ComputationContext & context )

static

在文件 multivariate_factor_checked.cpp 第 145 行定义.

                                 {
    std::vector<MultiPoly> factors;
    std::vector<int> multiplicities;
    Completeness completeness = Completeness::Complete;
    std::string reason;
    for (MultiPoly candidate :
         {difference.first + difference.second,
          difference.first - difference.second}) {
        auto sub = factor_multivariate_impl(candidate, context);
        if (!sub) return sub;
        auto sub_value = std::move(sub.value());
        if (sub_value.completeness == Completeness::Inconclusive) {
            completeness = Completeness::Inconclusive;
            if (reason.empty()) reason = sub_value.reason;
        }
        factors.insert(factors.end(),
                       sub_value.value.factors.begin(),
                       sub_value.value.factors.end());
        multiplicities.insert(
            multiplicities.end(),
            sub_value.value.multiplicities.begin(),
            sub_value.value.multiplicities.end());
    }
    return assemble_checked_factorization(
        poly, factors, multiplicities, completeness, std::move(reason));
}

引用了 LMCAS::multivariate_checked_detail::assemble_checked_factorization(), LMCAS::Complete, LMCAS::context, factor_difference_of_squares(), factor_multivariate_impl(), LMCAS::Inconclusive, LMCAS::sub() , 以及 LMCAS::Result< T >::value().

被这些函数引用 factor_difference_of_squares() , 以及 factor_multivariate_impl().

函数调用图:

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

factor_embedded_univariate()

MultiFactorCheckedResult LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_embedded_univariate ( const MultiPoly & poly, const MultiPoly & primitive, const std::string & main_variable, ComputationContext & context )

static

在文件 multivariate_factor_checked.cpp 第 211 行定义.

                                                                 {
    const auto& variables = poly.variables();
    Polynomial<Rational> univariate = primitive.to_univariate();
    auto factored =
        factor_univariate_bridge_checked(univariate, context);
    if (!factored) {
        return MultiFactorCheckedResult::failure(factored.error());
    }
    auto factor_value = std::move(factored.value());
    std::vector<MultiPoly> factors;
    factors.reserve(factor_value.value.size());
    for (const auto& factor : factor_value.value) {
        factors.push_back(embed_univariate_factor(
            factor, variables, main_variable));
    }
    return assemble_checked_factorization(
        poly, factors, std::vector<int>(factors.size(), 1),
        factor_value.completeness, std::move(factor_value.reason));
}

引用了 LMCAS::multivariate_checked_detail::assemble_checked_factorization(), LMCAS::context, embed_univariate_factor(), factor_embedded_univariate(), LMCAS::factor_univariate_bridge_checked() , 以及 LMCAS::Result< MathResult< MultiFactorResult > >::failure().

被这些函数引用 factor_embedded_univariate() , 以及 factor_multivariate_impl().

函数调用图:

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

factor_multivariate_impl()

MultiFactorCheckedResult LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_multivariate_impl ( const MultiPoly & poly, ComputationContext & context )

static

在文件 multivariate_factor_checked.cpp 第 233 行定义.

{
    constexpr const char* operation = "factor_multivariate";
    auto recursion = context.enter_recursion(operation);
    if (!recursion) return MultiFactorCheckedResult::failure(recursion.error());
    FactorRecursionGuard recursion_guard{context};
 
    if (poly.is_zero()) {
        return assemble_checked_factorization(
            poly, {}, {}, Completeness::Complete, {});
    }
    if (poly.is_constant()) {
        return assemble_checked_factorization(
            poly, {}, {}, Completeness::Complete, {});
    }
    const auto& variables = poly.variables();
    if (variables.empty()) {
        return MultiFactorCheckedResult::failure(
            CasErrc::InternalInvariant,
            "非常数多项式缺少变量表", operation);
    }
 
    std::string main_variable = variables.front();
    for (const auto& variable : variables) {
        if (poly.degree(variable) > poly.degree(main_variable)) {
            main_variable = variable;
        }
    }
    if (poly.total_degree() <= 1) {
        return assemble_checked_factorization(
            poly, {poly}, {1}, Completeness::Complete, {});
    }
 
    auto [common_monomial, quotient] =
        detail::extract_common_monomial(poly);
    const bool has_common_monomial = std::any_of(
        common_monomial.begin(), common_monomial.end(),
        [](int exponent) { return exponent > 0; });
    if (has_common_monomial) {
        return factor_common_monomial(poly, common_monomial, quotient, context);
    }
    MultiPoly primitive = poly.make_primitive();
    if (auto difference = detail::detect_difference_of_squares(primitive)) {
        return factor_difference_of_squares(poly, *difference, context);
    }
    if (auto binomial = detail::detect_binomial_power(primitive)) {
        const auto& [left, right, exponent] = *binomial;
        (void)exponent;
        return factor_binomial_power(poly, primitive, left, right, context);
    }
    if (primitive.is_univariate()) {
        return factor_embedded_univariate(poly, primitive, main_variable, context);
    }
    auto evaluated = factor_evaluated_linear(poly, primitive, main_variable, context);
    if (evaluated) return std::move(*evaluated);
    auto homogeneous =
        detail::factor_homogeneous_bivariate(primitive, context);
    if (!homogeneous) {
        return MultiFactorCheckedResult::failure(homogeneous.error());
    }
    if (homogeneous.value()) {
        auto& result = *homogeneous.value();
        return assemble_checked_factorization(
            poly, result.factors, result.multiplicities,
            Completeness::Complete, {});
    }
 
    return assemble_checked_factorization(
        poly, {poly}, {1}, Completeness::Inconclusive,
        "当前受检算法无法证明该多项式不可约");
}

引用了 LMCAS::multivariate_checked_detail::assemble_checked_factorization(), LMCAS::Complete, LMCAS::context, LMCAS::detail::detect_binomial_power(), LMCAS::detail::detect_difference_of_squares(), LMCAS::exponent, LMCAS::detail::extract_common_monomial(), factor_binomial_power(), factor_common_monomial(), factor_difference_of_squares(), factor_embedded_univariate(), LMCAS::multivariate_checked_detail::factor_evaluated_linear(), LMCAS::detail::factor_homogeneous_bivariate(), factor_multivariate_impl(), LMCAS::Result< MathResult< MultiFactorResult > >::failure(), LMCAS::Inconclusive, LMCAS::InternalInvariant, LMCAS::right , 以及 LMCAS::variable.

被这些函数引用 factor_binomial_power(), factor_common_monomial(), factor_difference_of_squares() , 以及 factor_multivariate_impl().

函数调用图:

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