LMCAS::multivariate_checked_detail 命名空间参考

类
struct	LinearAssignments
struct	LinearSamples

函数
static Result< void >	append_primitive_factor (MultiFactorResult &result, const MultiPoly &raw, int multiplicity)
MultiFactorCheckedResult	assemble_checked_factorization (const MultiPoly &original, const std::vector< MultiPoly > &factors, const std::vector< int > &multiplicities, Completeness completeness, std::string reason)
static Result< bool >	collect_linear_samples (const LinearSamples &input, std::vector< std::vector< Rational > > &samples)
static Result< bool >	enumerate_linear_assignments (LinearAssignments &search, size_t index)
std::optional< MultiFactorCheckedResult >	factor_evaluated_linear (const MultiPoly &original, const MultiPoly &primitive, const std::string &main_variable, ComputationContext &context)
static std::optional< MultiFactorCheckedResult >	factor_linear_assignments (const MultiPoly &original, const LinearSamples &input)
static std::optional< MultiFactorCheckedResult >	factor_linear_hensel (const MultiPoly &poly, const MultiPoly &primitive, const std::string &main_variable, const std::vector< std::string > &auxiliary_variables, const std::map< std::string, Rational > &zero_evaluation, MathResult< std::vector< Polynomial< Rational > > > &base_value, ComputationContext &context)
static MultiPoly	linear_assignment_factor (const LinearAssignments &search, size_t factor_index)
static bool	restore_specialization_unit (const MultiPoly &poly, const std::string &main_var, const std::map< std::string, Rational > &eval_points, std::vector< Polynomial< Rational > > &univariate_factors)
static Result< bool >	verify_linear_assignment (LinearAssignments &search)

---

类说明

LMCAS::multivariate_checked_detail::LinearAssignments

struct LMCAS::multivariate_checked_detail::LinearAssignments

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

LMCAS::multivariate_checked_detail::LinearAssignments 的协作图:

类成员
vector< vector< size_t > >	assignments
vector< MultiPoly >	found_factors
const LinearSamples &	input
const vector< vector< Rational > > &	samples

LMCAS::multivariate_checked_detail::LinearSamples

struct LMCAS::multivariate_checked_detail::LinearSamples

在文件 multivariate_factor_evaluation.cpp 第 33 行定义.

LMCAS::multivariate_checked_detail::LinearSamples 的协作图:

类成员
const vector< string > &	auxiliary
const vector< Rational > &	base_constants
ComputationContext &	context
const string &	main_variable
const MultiPoly &	primitive
const map< string, Rational > &	zero_evaluation

函数说明

append_primitive_factor()

Result< void > LMCAS::multivariate_checked_detail::append_primitive_factor ( MultiFactorResult & result, const MultiPoly & raw, int multiplicity )

static

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

                                                                                   {
    if (multiplicity <= 0) {
        return Result<void>::failure(CasErrc::InternalInvariant,
            "因子重数必须为正", "factor_multivariate");
    }
    if (raw.is_zero() || raw.is_constant()) return Result<void>::success();
    MultiPoly factor = raw.make_primitive();
    if (!factor.terms().empty() && factor.terms()[0].second < Rational(0)) {
        factor = factor * Rational(-1);
    }
    auto existing = std::find(result.factors.begin(), result.factors.end(), factor);
    if (existing == result.factors.end()) {
        result.factors.push_back(std::move(factor));
        result.multiplicities.push_back(multiplicity);
    } else {
        const auto index = static_cast<size_t>(existing - result.factors.begin());
        result.multiplicities[index] += multiplicity;
    }
    return Result<void>::success();
}

引用了 append_primitive_factor(), LMCAS::MultiFactorResult::factors, LMCAS::Result< T >::failure(), LMCAS::InternalInvariant, LMCAS::MultiFactorResult::multiplicities , 以及 LMCAS::Result< T >::success().

被这些函数引用 append_primitive_factor() , 以及 assemble_checked_factorization().

函数调用图:

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

assemble_checked_factorization()

MultiFactorCheckedResult LMCAS::multivariate_checked_detail::assemble_checked_factorization	(	const MultiPoly &	original,
		const std::vector< MultiPoly > &	factors,
		const std::vector< int > &	multiplicities,
		Completeness	completeness,
		std::string	reason )

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

{
    constexpr const char* operation = "factor_multivariate";
    if (original.is_zero()) {
        if (!raw_factors.empty()) {
            return MultiFactorCheckedResult::failure(
                CasErrc::InternalInvariant, "零多项式收到非空因子列表", operation);
        }
        return MultiFactorCheckedResult::success(
            MathResult<MultiFactorResult>{
                MultiFactorResult{Rational(0), {}, {}},
                completeness, std::move(reason)});
    }
 
    MultiFactorResult result;
    for (size_t i = 0; i < raw_factors.size(); ++i) {
        const int multiplicity = i < raw_multiplicities.size() ? raw_multiplicities[i] : 1;
        auto appended = append_primitive_factor(result, raw_factors[i], multiplicity);
        if (!appended) return MultiFactorCheckedResult::failure(appended.error());
    }
    MultiPoly product(Rational(1), original.variables());
    for (size_t i = 0; i < result.factors.size(); ++i) {
        for (int power = 0; power < result.multiplicities[i]; ++power) {
            product = product * result.factors[i];
        }
    }
    MultiPoly quotient = original.exact_div(product);
    if (!quotient.is_constant() || quotient.terms().empty()) {
        return MultiFactorCheckedResult::failure(
            CasErrc::InternalInvariant,
            "因子乘积与输入只差常数的不变量失效", operation);
    }
    result.constant = quotient.terms()[0].second;
    if (product * result.constant != original) {
        return MultiFactorCheckedResult::failure(
            CasErrc::InternalInvariant, "最终因子未精确重构输入", operation);
    }
    return MultiFactorCheckedResult::success(
        MathResult<MultiFactorResult>{
            std::move(result), completeness, std::move(reason)});
}

引用了 append_primitive_factor(), assemble_checked_factorization(), LMCAS::MultiFactorResult::constant, LMCAS::MultiFactorResult::factors, LMCAS::Result< MathResult< MultiFactorResult > >::failure(), LMCAS::InternalInvariant, LMCAS::MultiFactorResult::multiplicities , 以及 LMCAS::Result< MathResult< MultiFactorResult > >::success().

被这些函数引用 assemble_checked_factorization(), LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_binomial_power(), LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_common_monomial(), LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_difference_of_squares(), LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_embedded_univariate(), factor_linear_assignments(), factor_linear_hensel(), LMCAS::factor_multivariate_checked() , 以及 LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_multivariate_impl().

函数调用图:

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

collect_linear_samples()

Result< bool > LMCAS::multivariate_checked_detail::collect_linear_samples ( const LinearSamples & input, std::vector< std::vector< Rational > > & samples )

static

在文件 multivariate_factor_evaluation.cpp 第 42 行定义.

                                                                         {
    const size_t factor_count = input.base_constants.size();
    for (const auto& variable : input.auxiliary) {
        auto sample = input.zero_evaluation;
        sample[variable] = Rational(1);
        MultiPoly evaluated = input.primitive.eval(sample);
        if (evaluated.degree(input.main_variable) != input.primitive.degree(input.main_variable)) {
            return Result<bool>::success(false);
        }
        auto factored = factor_univariate_bridge_checked(evaluated.to_univariate(), input.context);
        if (!factored) { return Result<bool>::failure(factored.error()); }
        if (factored.value().value.size() != factor_count) { return Result<bool>::success(false); }
        std::vector<Rational> constants;
        for (const auto& factor : factored.value().value) {
            if (factor.degree() != 1) { return Result<bool>::success(false); }
            constants.push_back(factor.make_monic().coeffs[0]);
        }
        samples.push_back(std::move(constants));
    }
    return Result<bool>::success(true);
}

引用了 LMCAS::multivariate_checked_detail::LinearSamples::auxiliary, LMCAS::multivariate_checked_detail::LinearSamples::base_constants, collect_linear_samples(), LMCAS::multivariate_checked_detail::LinearSamples::context, LMCAS::factor_univariate_bridge_checked(), LMCAS::Result< T >::failure(), LMCAS::multivariate_checked_detail::LinearSamples::main_variable, LMCAS::multivariate_checked_detail::LinearSamples::primitive, LMCAS::Result< T >::success(), LMCAS::variable , 以及 LMCAS::multivariate_checked_detail::LinearSamples::zero_evaluation.

被这些函数引用 collect_linear_samples() , 以及 factor_linear_assignments().

函数调用图:

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

enumerate_linear_assignments()

Result< bool > LMCAS::multivariate_checked_detail::enumerate_linear_assignments ( LinearAssignments & search, size_t index )

static

在文件 multivariate_factor_evaluation.cpp 第 117 行定义.

                                                                                          {
    if (index == search.assignments.size()) { return verify_linear_assignment(search); }
    auto& permutation = search.assignments[index];
    std::sort(permutation.begin(), permutation.end());
    do {
        auto found = enumerate_linear_assignments(search, index + 1);
        if (!found || found.value()) { return found; }
    } while (std::next_permutation(permutation.begin(), permutation.end()));
    return Result<bool>::success(false);
}

引用了 LMCAS::multivariate_checked_detail::LinearAssignments::assignments, enumerate_linear_assignments(), LMCAS::Result< T >::success() , 以及 verify_linear_assignment().

被这些函数引用 enumerate_linear_assignments() , 以及 factor_linear_assignments().

函数调用图:

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

factor_evaluated_linear()

std::optional< MultiFactorCheckedResult > LMCAS::multivariate_checked_detail::factor_evaluated_linear	(	const MultiPoly &	original,
		const MultiPoly &	primitive,
		const std::string &	main_variable,
		ComputationContext &	context )

在文件 multivariate_factor_evaluation.cpp 第 182 行定义.

                                                                 {
    const auto& variables = primitive.variables();
    std::vector<std::string> auxiliary_variables;
    for (const auto& variable : variables) {
        if (variable != main_variable) { auxiliary_variables.push_back(variable); }
    }
    std::map<std::string, Rational> zero_evaluation;
    for (const auto& variable : auxiliary_variables) {
        zero_evaluation[variable] = Rational(0);
    }
    MultiPoly evaluated = primitive.eval(zero_evaluation);
    if (evaluated.degree(main_variable) != primitive.degree(main_variable)) { return std::nullopt; }
    Polynomial<Rational> base_poly = evaluated.to_univariate();
    auto base_result =
        factor_univariate_bridge_checked(base_poly, context);
    if (!base_result) {
        return MultiFactorCheckedResult::failure(base_result.error());
    }
    auto base_value = std::move(base_result.value());
    bool all_linear = base_value.value.size() > 1;
    for (const auto& factor : base_value.value) {
        all_linear = all_linear && factor.degree() == 1;
    }
    if (!all_linear) { return std::nullopt; }
    if (auxiliary_variables.size() == 1) {
        auto hensel = factor_linear_hensel(poly, primitive, main_variable,
            auxiliary_variables, zero_evaluation, base_value, context);
        if (hensel) { return hensel; }
    }
    std::vector<Rational> base_constants;
    for (const auto& factor : base_value.value) {
        base_constants.push_back(factor.make_monic().coeffs[0]);
    }
    LinearSamples input{primitive, main_variable, auxiliary_variables,
                        zero_evaluation, base_constants, context};
    return factor_linear_assignments(poly, input);
}

引用了 LMCAS::context, factor_evaluated_linear(), factor_linear_assignments(), factor_linear_hensel(), LMCAS::factor_univariate_bridge_checked(), LMCAS::Result< MathResult< MultiFactorResult > >::failure() , 以及 LMCAS::variable.

被这些函数引用 factor_evaluated_linear() , 以及 LMCAS::anonymous_namespace{multivariate_factor_checked.cpp}::factor_multivariate_impl().

函数调用图:

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

factor_linear_assignments()

std::optional< MultiFactorCheckedResult > LMCAS::multivariate_checked_detail::factor_linear_assignments ( const MultiPoly & original, const LinearSamples & input )

static

在文件 multivariate_factor_evaluation.cpp 第 128 行定义.

                                                           {
    std::vector<std::vector<Rational>> samples;
    auto collected = collect_linear_samples(input, samples);
    if (!collected) { return MultiFactorCheckedResult::failure(collected.error()); }
    if (!collected.value()) { return std::nullopt; }
    LinearAssignments search{input, samples,
        std::vector<std::vector<size_t>>(input.auxiliary.size(),
            std::vector<size_t>(input.base_constants.size())), {}};
    for (auto& assignment : search.assignments) {
        for (size_t i = 0; i < assignment.size(); ++i) assignment[i] = i;
    }
    auto found = enumerate_linear_assignments(search, 0);
    if (!found) { return MultiFactorCheckedResult::failure(found.error()); }
    if (!found.value()) { return std::nullopt; }
    return assemble_checked_factorization(original, search.found_factors,
        std::vector<int>(search.found_factors.size(), 1), Completeness::Complete, {});
}

引用了 assemble_checked_factorization(), LMCAS::multivariate_checked_detail::LinearAssignments::assignments, LMCAS::multivariate_checked_detail::LinearSamples::auxiliary, LMCAS::multivariate_checked_detail::LinearSamples::base_constants, collect_linear_samples(), LMCAS::Complete, enumerate_linear_assignments(), factor_linear_assignments(), LMCAS::Result< MathResult< MultiFactorResult > >::failure() , 以及 LMCAS::multivariate_checked_detail::LinearAssignments::found_factors.

被这些函数引用 factor_evaluated_linear() , 以及 factor_linear_assignments().

函数调用图:

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

factor_linear_hensel()

std::optional< MultiFactorCheckedResult > LMCAS::multivariate_checked_detail::factor_linear_hensel ( const MultiPoly & poly, const MultiPoly & primitive, const std::string & main_variable, const std::vector< std::string > & auxiliary_variables, const std::map< std::string, Rational > & zero_evaluation, MathResult< std::vector< Polynomial< Rational > > > & base_value, ComputationContext & context )

static

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

                                                                                          {
    constexpr const char* operation = "factor_multivariate";
    const auto& variables = primitive.variables();
    auto hensel_step = context.consume_steps(
        static_cast<size_t>(
            std::max(1, primitive.degree(auxiliary_variables[0]))),
        operation);
    if (!hensel_step) {
        return MultiFactorCheckedResult::failure(hensel_step.error());
    }
    std::vector<Polynomial<Rational>> prepared = base_value.value;
    if (!restore_specialization_unit(
            primitive, main_variable, zero_evaluation, prepared)) { return std::nullopt; }
    auto lifted = multivariate_hensel_lift(
        primitive, prepared, auxiliary_variables[0], Rational(0),
        primitive.degree(auxiliary_variables[0]));
    MultiPoly lifted_product(Rational(1), variables);
    for (const auto& factor : lifted) {
        lifted_product = lifted_product * factor;
    }
    if (lifted.size() > 1 && lifted_product == primitive) {
        const bool all_linear = std::all_of(lifted.begin(), lifted.end(),
            [](const MultiPoly& factor) { return factor.total_degree() == 1; });
        return assemble_checked_factorization(
            poly, lifted, std::vector<int>(lifted.size(), 1),
            all_linear ? Completeness::Complete : Completeness::Inconclusive,
            all_linear ? std::string{} : "提升因子的不可约性尚未证明");
    }
    return std::nullopt;
}

引用了 assemble_checked_factorization(), LMCAS::Complete, LMCAS::context, factor_linear_hensel(), LMCAS::Result< MathResult< MultiFactorResult > >::failure(), LMCAS::Inconclusive, LMCAS::multivariate_hensel_lift() , 以及 restore_specialization_unit().

被这些函数引用 factor_evaluated_linear() , 以及 factor_linear_hensel().

函数调用图:

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

linear_assignment_factor()

MultiPoly LMCAS::multivariate_checked_detail::linear_assignment_factor ( const LinearAssignments & search, size_t factor_index )

static

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

                                                                                                {
    const auto& variables = search.input.primitive.variables();
    std::vector<MultiPoly::Term> terms;
    Monomial main_monomial(variables.size(), 0);
    const size_t main_index = static_cast<size_t>(std::find(
        variables.begin(), variables.end(), search.input.main_variable) - variables.begin());
    main_monomial[main_index] = 1;
    terms.emplace_back(main_monomial, Rational(1));
    Monomial constant_monomial(variables.size(), 0);
    const auto& constant = search.input.base_constants[factor_index];
    if (!constant.is_zero()) terms.emplace_back(constant_monomial, constant);
    for (size_t variable_index = 0; variable_index < search.input.auxiliary.size(); ++variable_index) {
        Rational coefficient = search.samples[variable_index]
            [search.assignments[variable_index][factor_index]] - constant;
        if (coefficient.is_zero()) { continue; }
        Monomial monomial(variables.size(), 0);
        const size_t index = static_cast<size_t>(std::find(
            variables.begin(), variables.end(), search.input.auxiliary[variable_index]) - variables.begin());
        monomial[index] = 1;
        terms.emplace_back(std::move(monomial), coefficient);
    }
    return MultiPoly(std::move(terms), variables);
}

引用了 LMCAS::multivariate_checked_detail::LinearAssignments::assignments, LMCAS::multivariate_checked_detail::LinearSamples::auxiliary, LMCAS::multivariate_checked_detail::LinearSamples::base_constants, LMCAS::multivariate_checked_detail::LinearAssignments::input, linear_assignment_factor(), LMCAS::multivariate_checked_detail::LinearSamples::main_variable, LMCAS::multivariate_checked_detail::LinearSamples::primitive , 以及 LMCAS::multivariate_checked_detail::LinearAssignments::samples.

被这些函数引用 linear_assignment_factor() , 以及 verify_linear_assignment().

函数调用图:

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

restore_specialization_unit()

bool LMCAS::multivariate_checked_detail::restore_specialization_unit ( const MultiPoly & poly, const std::string & main_var, const std::map< std::string, Rational > & eval_points, std::vector< Polynomial< Rational > > & univariate_factors )

static

在文件 multivariate_factor_evaluation.cpp 第 12 行定义.

{
    if (univariate_factors.empty()) { return false; }
    const Polynomial<Rational> specialized = poly.eval(eval_points).to_univariate();
    if (specialized.variable_name != main_var) { return false; }
    Polynomial<Rational> product({Rational(1)}, main_var);
    for (const auto& factor : univariate_factors) {
        if (factor.variable_name != main_var || factor.is_zero()) { return false; }
        product = product * factor;
    }
    auto [unit, remainder] = specialized.div_mod(product);
    if (!remainder.is_zero() || unit.is_zero() || unit.degree() != 0) { return false; }
    if (!(product * unit == specialized)) { return false; }
    univariate_factors[0] = univariate_factors[0] * unit;
    return true;
}

引用了 LMCAS::Polynomial< CoeffType >::div_mod(), LMCAS::main_var, restore_specialization_unit(), LMCAS::unit , 以及 LMCAS::Polynomial< CoeffType >::variable_name.

被这些函数引用 factor_linear_hensel() , 以及 restore_specialization_unit().

函数调用图:

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

verify_linear_assignment()

Result< bool > LMCAS::multivariate_checked_detail::verify_linear_assignment ( LinearAssignments & search )

static

在文件 multivariate_factor_evaluation.cpp 第 96 行定义.

                                                                        {
    auto step = search.input.context.consume_steps(1, "factor_multivariate");
    if (!step) { return Result<bool>::failure(step.error()); }
    std::vector<MultiPoly> candidates;
    for (size_t i = 0; i < search.input.base_constants.size(); ++i) {
        candidates.push_back(linear_assignment_factor(search, i));
    }
    MultiPoly product(Rational(1), search.input.primitive.variables());
    for (const auto& candidate : candidates) product = product * candidate;
    MultiPoly unit;
    try {
        unit = search.input.primitive.exact_div(product);
    } catch (const std::runtime_error&) {
        return Result<bool>::success(false);
    }
    if (unit.is_zero() || !unit.is_constant() ||
        product * unit != search.input.primitive) { return Result<bool>::success(false); }
    search.found_factors = std::move(candidates);
    return Result<bool>::success(true);
}

引用了 LMCAS::multivariate_checked_detail::LinearSamples::base_constants, LMCAS::ComputationContext::consume_steps(), LMCAS::multivariate_checked_detail::LinearSamples::context, LMCAS::Result< T >::failure(), LMCAS::multivariate_checked_detail::LinearAssignments::found_factors, LMCAS::multivariate_checked_detail::LinearAssignments::input, linear_assignment_factor(), LMCAS::multivariate_checked_detail::LinearSamples::primitive, LMCAS::Result< T >::success(), LMCAS::unit , 以及 verify_linear_assignment().

被这些函数引用 enumerate_linear_assignments() , 以及 verify_linear_assignment().

函数调用图:

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