Aberth-Ehrlich method for polynomial root-finding. More...

#include <complex>
#include <lds/lds.hpp>
#include <utility>
#include <vector>

Include dependency graph for aberth.hpp:

This graph shows which files directly or indirectly include this file:

Namespaces
namespace	ginger
	Options for convergence-based algorithms.

Functions
template<unsigned long N, unsigned long Base = 2>
constexpr auto	make_vdc_table () -> std::array< double, N >
	Helper to generate a constexpr table of VdCorput<Base> values.

double	vdc2_table (unsigned long index)
	Access the precomputed VdCorput base-2 table.

auto	make_circle_table () noexcept -> std::array< std::array< double, 2 >, VDC_TABLE_SIZE >
	Helper to generate the precomputed Circle base-2 table.

auto	make_cos_pi_vdc2_table () noexcept -> std::array< double, VDC_TABLE_SIZE >
	Helper to generate the precomputed cos(pi * vdc2_table[i]) table.

constexpr double	cos_pi_vdc2 (unsigned long index)
	Access the precomputed cos(pi * vdc2_table[i]) value.

constexpr double	circle2_table_x (unsigned long index)
	Access the precomputed Circle base-2 table x-coordinate.

constexpr double	circle2_table_y (unsigned long index)
	Access the precomputed Circle base-2 table y-coordinate.

auto	horner_eval_c (const std::vector< double > &coeffs, const std::complex< double > &zval) -> std::complex< double >

auto	horner_eval_f (const std::vector< double > &coeffs, const double &zval) -> double

auto	initial_aberth (const std::vector< double > &coeffs) -> std::vector< std::complex< double > >
	Initial guess for the Aberth-Ehrlich method.

auto	aberth (const std::vector< double > &coeffs, std::vector< std::complex< double > > &zs, const ginger::Options &options) -> std::pair< unsigned int, bool >
	Single-threading Aberth-Ehrlich method.

auto	initial_aberth_autocorr (const std::vector< double > &coeffs) -> std::vector< std::complex< double > >
	Initial guess for the Aberth-Ehrlich method (specifically for auto-correlation functions)

auto	aberth_autocorr (const std::vector< double > &coeffs, std::vector< std::complex< double > > &zs, const ginger::Options &options) -> std::pair< unsigned int, bool >
	Single-threading Aberth-Ehrlich method (specifically for auto-correlation functions)

auto	poly_from_roots (const std::vector< std::complex< double > > &zs) -> std::vector< double >
	Reconstruct a monic polynomial from its complex roots.

auto	leja_order (const std::vector< std::complex< double > > &points) -> std::vector< std::complex< double > >
	Leja ordering of complex points.

auto	poly_from_autocorr_roots (const std::vector< std::complex< double > > &zs) -> std::vector< double >
	Reconstruct a monic polynomial from its autocorrelation roots.

Variables
constexpr const auto	VDC_TABLE_SIZE = 1000UL
	Size of the precomputed VdCorput base-2 table.

constexpr std::array< double, VDC_TABLE_SIZE >	VDC_TABLE_2 = make_vdc_table<VDC_TABLE_SIZE, 2>()
	Precomputed table of VdCorput sequence values (base 2)

Detailed Description

Aberth-Ehrlich method for polynomial root-finding.

Function Documentation

◆ aberth()

auto aberth	(	const std::vector< double > &	coeffs,
		std::vector< std::complex< double > > &	zs,
		const ginger::Options &	options
	)		-> std::pair< unsigned int, bool >

extern

Single-threading Aberth-Ehrlich method.

The aberth function is an implementation of the Aberth-Ehrlich method for finding the roots of a polynomial.

Aberth's method iteratively improves root estimates for a polynomial \(P(x)\):

\[ x_k^{(i+1)} = x_k^{(i)} - \frac{P(x_k)}{P'(x_k)}\Bigg/ \left(1 - \frac{P(x_k)}{P'(x_k)}\sum_{j \ne k}\frac{1}{x_k - x_j}\right) \]

where the sum is over all other root approximations. The method is robust but requires complex arithmetic even if the polynomial is real. This is because it starts with complex initial approximations.

Parameters

[in]	coeffs	The `coeffs` parameter is a vector representing the coefficients of a polynomial. Each element of the vector corresponds to a term in the polynomial, starting from the highest degree term and ending with the constant term. For example, if the polynomial is `3x^2 + 2x + 1`, the coefficients vector would be `{3, 2, 1}`.
[in,out]	zs	`zs` is a vector of complex numbers representing the initial guesses for the roots of the polynomial. The function will update these values iteratively to converge to the actual roots.
[in]	options	The `options` parameter is an object of type `Options` that contains the maximum number of iterations (`max_iters`) and the tolerance (`tolerance`). These options control the convergence criteria for the Aberth-Ehrlich method.

Returns: The aberth function returns a std::pair<unsigned int, bool>. The first element of the pair represents the number of iterations performed, and the second element represents whether the method converged to a solution within the specified tolerance.

◆ aberth_autocorr()

auto aberth_autocorr	(	const std::vector< double > &	coeffs,
		std::vector< std::complex< double > > &	zs,
		const ginger::Options &	options
	)		-> std::pair< unsigned int, bool >

extern

Single-threading Aberth-Ehrlich method (specifically for auto-correlation functions)

The aberth_autocorr function is an implementation of the Aberth-Ehrlich method for finding the roots of a palindromic (auto-correlation) polynomial.

Aberth's method is a method for finding the roots of a polynomial that is robust but requires complex arithmetic even if the polynomial is real. This is because it starts with complex initial approximations.

Parameters

[in]	coeffs	The `coeffs` parameter is a vector representing the coefficients of a polynomial. Each element of the vector corresponds to a term in the polynomial, starting from the highest degree term and ending with the constant term. For example, if the polynomial is `3x^2 + 2x + 1`, the coefficients vector would be `{3, 2, 1}`.
[in,out]	zs	`zs` is a vector of complex numbers representing the initial guesses for the roots of the polynomial. The function will update these values iteratively to converge to the actual roots.
[in]	options	The `options` parameter is an object of type `Options` that contains the maximum number of iterations (`max_iters`) and the tolerance (`tolerance`). These options control the convergence criteria for the Aberth-Ehrlich method.

Returns: The aberth_autocorr function returns a std::pair<unsigned int, bool>. The first element of the pair represents the number of iterations performed, and the second element represents whether the method converged to a solution within the specified tolerance.

◆ circle2_table_x()

constexpr double circle2_table_x ( unsigned long index )

constexpr

Access the precomputed Circle base-2 table x-coordinate.

Parameters

index Index into the table

Returns: The circle point x-coordinate at the given index

◆ circle2_table_y()

constexpr double circle2_table_y ( unsigned long index )

constexpr

Access the precomputed Circle base-2 table y-coordinate.

Parameters

index Index into the table

Returns: The circle point y-coordinate at the given index

◆ cos_pi_vdc2()

constexpr double cos_pi_vdc2 ( unsigned long index )

constexpr

Access the precomputed cos(pi * vdc2_table[i]) value.

Parameters

index Index into the table

Returns: The cos(pi * vdc_value) at the given index

◆ horner_eval_c()

auto horner_eval_c	(	const std::vector< double > &	coeffs,
		const std::complex< double > &	zval
	)		-> std::complex<double>

inline

The function horner_eval_c is implementing the Horner's method for evaluating a polynomial at a given point.

Parameters

[in]	coeffs	The `coeffs` parameter is a vector representing the coefficients of a polynomial. Each element of the vector corresponds to a term in the polynomial, starting from the highest degree term and ending with the constant term.
[in]	z

Returns: Tp

*        coeffs[0]      coeffs[1]      coeffs[2]                 coeffs[n-1]    coeffs[n]
*     +-----------> + -----------> + -----------> + ... + -----------> + --------->
*     |             |              |              |                   |            |
*     |    z       v    z         v    z         v                   v    z       v    z
*     +---> [x] --> +---> [x] --> +---> [x] --> +---> ... ----> +---> [x] --> +---> [x] --> result
*           |                    |              |                           |              |
*           +---------------------              +---------------------------+              |
*           |                                   |                                        |
*           +------------------------------------+----------------------------------------+
*
* P(x) = coeffs[0]*x^n + coeffs[1]*x^(n-1) + ... + coeffs[n-1]*x + coeffs[n]
*

◆ horner_eval_f()

auto horner_eval_f	(	const std::vector< double > &	coeffs,
		const double &	zval
	)		-> double

inline

The function horner_eval_f is implementing the Horner's method for evaluating a polynomial at a given point.

Parameters

[in]	coeffs	The `coeffs` parameter is a vector representing the coefficients of a polynomial. Each element of the vector corresponds to a term in the polynomial, starting from the highest degree term and ending with the constant term.
[in]	z

Returns: Tp

◆ initial_aberth()

auto initial_aberth ( const std::vector< double > & coeffs ) -> std::vector< std::complex< double > >

extern

Initial guess for the Aberth-Ehrlich method.

The initial_aberth function calculates the initial values for the Aberth-Ehrlich method for finding the roots of a polynomial.

\( z_k = R \cdot e^{2\pi i \cdot \phi_2(k)}, \quad k = 0,\dots,n-1 \) where \( R \) is estimated from the polynomial coefficients.

Parameters

[in] coeffs The coeffs parameter is a vector of doubles that represents the coefficients of a polynomial.

Returns: The function initial_aberth returns a vector of Complex numbers.

◆ initial_aberth_autocorr()

auto initial_aberth_autocorr ( const std::vector< double > & coeffs ) -> std::vector< std::complex< double > >

extern

Initial guess for the Aberth-Ehrlich method (specifically for auto-correlation functions)

The initial_aberth_autocorr function calculates the initial values for the Aberth-Ehrlich method for finding the roots of a palindromic (auto-correlation) polynomial.

\( z_k = e^{2\pi i \cdot \phi_2(k)}, \quad k = 0,\dots,\lfloor n/2 \rfloor \) where the roots are distributed on the unit circle.

Parameters

[in] coeffs The coeffs parameter is a vector of doubles that represents the coefficients of a polynomial.

Returns: The function initial_aberth_autocorr returns a vector of Complex numbers.

◆ leja_order()

auto leja_order ( const std::vector< std::complex< double > > & points ) -> std::vector< std::complex< double > >

extern

Leja ordering of complex points.

Reorders complex points using the greedy Leja algorithm: starts with the smallest-magnitude point, then iteratively selects the remaining point that maximizes the minimum Euclidean distance to all already-selected points. This ordering reduces numerical error when reconstructing polynomials from roots.

\[ p_0 = \arg\min_{z \in S} |z|, \qquad p_k = \arg\max_{z \in S_k} \min_{j < k} |z - p_j| \]

Parameters

[in] points Input vector of complex numbers

Returns: std::vector<std::complex<double>> Reordered points in Leja sequence

◆ make_circle_table()

auto make_circle_table ( ) -> std::array<std::array<double, 2>, VDC_TABLE_SIZE>

inlinenoexcept

Helper to generate the precomputed Circle base-2 table.

Mapped from VDC_TABLE_2 to the unit circle. Not constexpr: std::cos/stdsin lack portable constexpr support in C++20.

Returns: std::array<std::array<double, 2>, VDC_TABLE_SIZE> of unit-circle points

◆ make_cos_pi_vdc2_table()

auto make_cos_pi_vdc2_table ( ) -> std::array<double, VDC_TABLE_SIZE>

inlinenoexcept

Helper to generate the precomputed cos(pi * vdc2_table[i]) table.

Returns: std::array<double, VDC_TABLE_SIZE> of cos(pi * vdc_value) values

◆ make_vdc_table()

template<unsigned long N, unsigned long Base = 2>

constexpr auto make_vdc_table ( ) -> std::array<double, N>

constexpr

Helper to generate a constexpr table of VdCorput<Base> values.

Template Parameters

N	Number of values to generate
Base	Base of the van der Corput sequence

Returns: std::array<double, N> with precomputed sequence values

◆ poly_from_autocorr_roots()

auto poly_from_autocorr_roots ( const std::vector< std::complex< double > > & zs ) -> std::vector< double >

extern

Reconstruct a monic polynomial from its autocorrelation roots.

Auto-correlation (palindromic) polynomials have roots in reciprocal pairs. The aberth_autocorr functions find the degree/2 "independent" roots. This function adds the reciprocal of each root (1/z) to get the full set of degree roots, then reconstructs with Leja ordering.

\[ P(x) = \prod_{k=1}^{n} (x - r_k)(x - r_k^{-1}) = x^{2n} + a_{2n-1}x^{2n-1} + \cdots + a_0 \]

Parameters

[in] zs Roots found by aberth_autocorr or aberth_autocorr_mt

Returns: std::vector<double> Monic polynomial coefficients (highest degree first)

◆ poly_from_roots()

auto poly_from_roots ( const std::vector< std::complex< double > > & zs ) -> std::vector< double >

extern

Reconstruct a monic polynomial from its complex roots.

Builds the monic polynomial whose roots are the given complex numbers:

\[ P(x) = \prod_{k=1}^{n} (x - z_k) = x^n + a_{n-1}x^{n-1} + \cdots + a_0 \]

Uses Leja ordering for numerical stability.

Parameters

[in] zs Vector of complex roots

Returns: std::vector<double> Monic polynomial coefficients (highest degree first)

◆ vdc2_table()

double vdc2_table ( unsigned long index )

inline

Access the precomputed VdCorput base-2 table.

Parameters

index Index into the table

Returns: The VDC value at the given index

Variable Documentation

◆ VDC_TABLE_2

constexpr std::array<double, VDC_TABLE_SIZE> VDC_TABLE_2 = make_vdc_table<VDC_TABLE_SIZE, 2>()

constexpr

Precomputed table of VdCorput sequence values (base 2)

Generated at compile-time using VdCorput<2>

◆ VDC_TABLE_SIZE

constexpr const auto VDC_TABLE_SIZE = 1000UL

constexpr

Size of the precomputed VdCorput base-2 table.

Namespaces

Functions

Variables

Detailed Description

Function Documentation

◆ aberth()

◆ aberth_autocorr()

◆ circle2_table_x()

◆ circle2_table_y()

◆ cos_pi_vdc2()

◆ horner_eval_c()

◆ horner_eval_f()

◆ initial_aberth()

◆ initial_aberth_autocorr()

◆ leja_order()

◆ make_circle_table()

◆ make_cos_pi_vdc2_table()

◆ make_vdc_table()

◆ poly_from_autocorr_roots()

◆ poly_from_roots()

◆ vdc2_table()

Variable Documentation

◆ VDC_TABLE_2

◆ VDC_TABLE_SIZE