LMCAS::detail::complex_root 命名空间参考

命名空间
namespace	anonymous_namespace{complex_root_projection.cpp}
namespace	anonymous_namespace{complex_root_rectangles.cpp}
namespace	anonymous_namespace{complex_root_winding.cpp}

类
struct	CoordinateProjections
struct	RationalRectangle
struct	RectangleCount

类型定义
using	Poly = Polynomial<Rational>

函数
Poly	clear_denominators (Poly polynomial)
Result< CoordinateProjections >	coordinate_projections (const Poly &polynomial, ComputationContext &context, const std::string &operation)
Result< RectangleCount >	count_rectangle_roots (const Poly &polynomial, const RationalRectangle &rectangle, ComputationContext &context, const std::string &operation)
Result< std::vector< ComplexIsolation > >	isolate_nonreal_roots (const Poly &polynomial, std::size_t complex_count, ComputationContext &context, const std::string &operation)
int	rational_sign (const Rational &value)
Result< void >	refine_interval (const Poly &polynomial, RationalInterval &interval, ComputationContext &context, const std::string &operation)
Poly	scale_poly (Poly polynomial, const Rational &scalar)

---

类说明

LMCAS::detail::complex_root::CoordinateProjections

struct LMCAS::detail::complex_root::CoordinateProjections

在文件 complex_root_isolation.hpp 第 23 行定义.

LMCAS::detail::complex_root::CoordinateProjections 的协作图:

类成员
Poly	imaginary
Poly	real

LMCAS::detail::complex_root::RationalRectangle

struct LMCAS::detail::complex_root::RationalRectangle

在文件 complex_root_isolation.hpp 第 11 行定义.

LMCAS::detail::complex_root::RationalRectangle 的协作图:

类成员
Rational	imaginary_lower
Rational	imaginary_upper
Rational	real_lower
Rational	real_upper

LMCAS::detail::complex_root::RectangleCount

struct LMCAS::detail::complex_root::RectangleCount

在文件 complex_root_isolation.hpp 第 18 行定义.

LMCAS::detail::complex_root::RectangleCount 的协作图:

类成员
bool	boundary_clear = false
size_t	count = 0

类型定义说明

Poly

using LMCAS::detail::complex_root::Poly = Polynomial<Rational>

在文件 complex_root_isolation.hpp 第 9 行定义.

函数说明

clear_denominators()

Poly LMCAS::detail::complex_root::clear_denominators

(

Poly

polynomial

)

在文件 complex_root_projection.cpp 第 16 行定义.

                                         {
    BigInt common_denominator(1);
    for (const auto& coefficient : polynomial.coeffs) {
        common_denominator *= coefficient.get_denominator();
    }
    for (auto& coefficient : polynomial.coeffs) {
        coefficient = Rational(
            coefficient.get_numerator() *
                (common_denominator / coefficient.get_denominator()));
    }
    polynomial.trim();
    return polynomial;
}

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

被这些函数引用 clear_denominators() , 以及 LMCAS::detail::anonymous_namespace{complex_root_isolation.cpp}::isolate_unfactored().

函数调用图:

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

coordinate_projections()

Result< CoordinateProjections > LMCAS::detail::complex_root::coordinate_projections	(	const Poly &	polynomial,
		ComputationContext &	context,
		const std::string &	operation )

在文件 complex_root_projection.cpp 第 284 行定义.

                                {
    const ComplexBivariate parts = complex_bivariate_parts(polynomial);
    auto real = sylvester_resultant(
        coefficients_in_y(parts.real, "_re"),
        coefficients_in_y(parts.imaginary, "_re"),
        "_re", context, operation + ".resultant.real");
    if (!real) return Result<CoordinateProjections>::failure(real.error());
    auto imaginary = sylvester_resultant(
        coefficients_in_x(parts.real, "_im"),
        coefficients_in_x(parts.imaginary, "_im"),
        "_im", context, operation + ".resultant.imaginary");
    if (!imaginary) return Result<CoordinateProjections>::failure(imaginary.error());
    if (real.value().degree() <= 0 || imaginary.value().degree() <= 0) {
        return Result<CoordinateProjections>::failure(
            CasErrc::InternalInvariant,
            "complex coordinate resultant was identically zero", operation);
    }
    return Result<CoordinateProjections>::success(CoordinateProjections{
        real.value().square_free_part().make_monic(),
        imaginary.value().square_free_part().make_monic()});
}

引用了 LMCAS::detail::context, coordinate_projections(), LMCAS::Result< T >::error(), LMCAS::Result< T >::failure(), LMCAS::InternalInvariant, LMCAS::detail::operation, LMCAS::real(), LMCAS::Result< T >::success() , 以及 LMCAS::Result< T >::value().

被这些函数引用 coordinate_projections() , 以及 LMCAS::detail::complex_root::anonymous_namespace{complex_root_rectangles.cpp}::prepare_projection_grid().

函数调用图:

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

count_rectangle_roots()

Result< RectangleCount > LMCAS::detail::complex_root::count_rectangle_roots	(	const Poly &	polynomial,
		const RationalRectangle &	rectangle,
		ComputationContext &	context,
		const std::string &	operation )

在文件 complex_root_winding.cpp 第 232 行定义.

                                                             {
    auto step = context.consume_steps(1, operation);
    if (!step) return Result<RectangleCount>::failure(step.error());
    const auto edges = rectangle_edges(polynomial, rectangle);
    for (const auto& [real, imaginary] : edges) {
        auto clear = edge_is_clear(real, imaginary, context, operation);
        if (!clear) return Result<RectangleCount>::failure(clear.error());
        if (!clear.value()) {
            return Result<RectangleCount>::success(RectangleCount{false, 0});
        }
    }
    BigInt shear_magnitude(0);
    int shear_direction = 1;
    while (true) {
        step = context.consume_steps(1, operation);
        if (!step) return Result<RectangleCount>::failure(step.error());
        auto bits = context.require_integer_bits(shear_magnitude.bit_length(), operation);
        if (!bits) return Result<RectangleCount>::failure(bits.error());
        const Rational shear(shear_direction > 0 ? shear_magnitude : -shear_magnitude);
        if (shear_is_valid(edges, shear)) {
            return count_sheared_edges(edges, shear, polynomial.degree(), context, operation);
        }
        if (shear_direction > 0) {
            shear_direction = -1;
            if (shear_magnitude.is_zero()) shear_magnitude = BigInt(1);
        } else {
            shear_direction = 1;
            shear_magnitude += BigInt(1);
        }
    }
}

引用了 LMCAS::detail::context, count_rectangle_roots(), LMCAS::Polynomial< CoeffType >::degree(), LMCAS::Result< T >::failure(), LMCAS::detail::operation, LMCAS::real() , 以及 LMCAS::Result< T >::success().

被这些函数引用 count_rectangle_roots() , 以及 LMCAS::detail::complex_root::anonymous_namespace{complex_root_rectangles.cpp}::isolate_grid_row().

函数调用图:

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

isolate_nonreal_roots()

Result< std::vector< ComplexIsolation > > LMCAS::detail::complex_root::isolate_nonreal_roots	(	const Poly &	polynomial,
		std::size_t	complex_count,
		ComputationContext &	context,
		const std::string &	operation )

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

                                                             {
    auto prepared = prepare_projection_grid(polynomial, context, operation);
    if (!prepared) return Result<std::vector<ComplexIsolation>>::failure(prepared.error());
    auto& grid = prepared.value();
    auto conjugate = certify_conjugate_projections(grid, complex_count, context, operation);
    if (!conjugate) return Result<std::vector<ComplexIsolation>>::failure(conjugate.error());
    const Rational bound = strict_cauchy_root_bound(polynomial);
    grid.real_bands = projection_bands(grid.real_roots, bound);
    grid.imaginary_bands = projection_bands(grid.imaginary_roots, bound);
    std::vector<ComplexIsolation> roots;
    roots.reserve(complex_count);
    for (std::size_t real_index = 0; real_index < grid.real_bands.size(); ++real_index) {
        auto isolated = isolate_grid_row(polynomial, grid, real_index, roots, context, operation);
        if (!isolated) return Result<std::vector<ComplexIsolation>>::failure(isolated.error());
    }
    if (roots.size() != complex_count) {
        return Result<std::vector<ComplexIsolation>>::failure(
            CasErrc::InternalInvariant,
            "projection-band rectangles did not cover every non-real root", operation);
    }
    std::sort(roots.begin(), roots.end(),
        [](const ComplexIsolation& left, const ComplexIsolation& right) {
            if (left.real_projection.root_index != right.real_projection.root_index) {
                return left.real_projection.root_index < right.real_projection.root_index;
            }
            return left.imaginary_projection.root_index < right.imaginary_projection.root_index;
        });
    return Result<std::vector<ComplexIsolation>>::success(std::move(roots));
}

引用了 LMCAS::detail::context, LMCAS::detail::ComplexIsolation::imaginary_projection, LMCAS::InternalInvariant, isolate_nonreal_roots(), LMCAS::detail::operation, LMCAS::right, LMCAS::detail::ExactRealAlgebraic::root_index, LMCAS::roots() , 以及 LMCAS::detail::strict_cauchy_root_bound().

被这些函数引用 isolate_nonreal_roots() , 以及 LMCAS::detail::anonymous_namespace{complex_root_isolation.cpp}::isolate_unfactored().

函数调用图:

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

rational_sign()

int LMCAS::detail::complex_root::rational_sign

(

const Rational &

value

)

在文件 complex_root_rectangles.cpp 第 8 行定义.

                                         {
    if (value < Rational(0)) return -1;
    if (value > Rational(0)) return 1;
    return 0;
}

引用了 rational_sign() , 以及 LMCAS::value.

被这些函数引用 LMCAS::detail::complex_root::anonymous_namespace{complex_root_winding.cpp}::pole_index(), rational_sign() , 以及 refine_interval().

函数调用图:

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

refine_interval()

Result< void > LMCAS::detail::complex_root::refine_interval	(	const Poly &	polynomial,
		RationalInterval &	interval,
		ComputationContext &	context,
		const std::string &	operation )

在文件 complex_root_rectangles.cpp 第 14 行定义.

                                {
    auto step = context.consume_steps(1, operation);
    if (!step) return step;
    if (interval.first == interval.second) return Result<void>::success();
    const Rational midpoint =
        (interval.first + interval.second) / Rational(2);
    const Rational middle_value = polynomial.eval(midpoint);
    if (middle_value == Rational(0)) {
        interval = {midpoint, midpoint};
        return Result<void>::success();
    }
    const int lower_sign = rational_sign(polynomial.eval(interval.first));
    if (lower_sign == 0) {
        interval.second = interval.first;
    } else if (lower_sign != rational_sign(middle_value)) {
        interval.second = midpoint;
    } else {
        interval.first = midpoint;
    }
    return Result<void>::success();
}

引用了 LMCAS::detail::context, LMCAS::Polynomial< CoeffType >::eval(), LMCAS::interval(), LMCAS::detail::operation, rational_sign(), refine_interval() , 以及 LMCAS::Result< T >::success().

被这些函数引用 refine_interval(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_winding.cpp}::refine_pole_interval(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_rectangles.cpp}::refine_projection_interval() , 以及 LMCAS::detail::complex_root::anonymous_namespace{complex_root_rectangles.cpp}::separate_imaginary_axis().

函数调用图:

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

scale_poly()

Poly LMCAS::detail::complex_root::scale_poly	(	Poly	polynomial,
		const Rational &	scalar )

在文件 complex_root_projection.cpp 第 8 行定义.

                                                         {
    for (auto& coefficient : polynomial.coeffs) {
        coefficient = coefficient * scalar;
    }
    polynomial.trim();
    return polynomial;
}

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

被这些函数引用 LMCAS::detail::complex_root::anonymous_namespace{complex_root_winding.cpp}::count_sheared_edges(), LMCAS::detail::complex_root::anonymous_namespace{complex_root_projection.cpp}::resultant_determinant(), scale_poly() , 以及 LMCAS::detail::complex_root::anonymous_namespace{complex_root_winding.cpp}::shear_is_valid().

函数调用图:

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