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

#include <complex>
#include <utility>
#include <vector>

Include dependency graph for aberth.hpp:

Functions
double	vdc2_table (unsigned long index)
	van der Corput sequence value for a given index

double	cos_pi_vdc2 (unsigned long index)
	Cosine of pi times van der Corput value.

double	circle2_table_x (unsigned long index)
	Circle sequence X-coordinate for an index.

double	circle2_table_y (unsigned long index)
	Circle sequence Y-coordinate for an index.

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 Options &options) -> std::pair< unsigned int, bool >
	Single-threading Aberth-Ehrlich method.

auto	aberth_mt (const std::vector< double > &coeffs, std::vector< std::complex< double > > &zs, const Options &options) -> std::pair< unsigned int, bool >
	Multi-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 Options &options) -> std::pair< unsigned int, bool >
	Single-threading Aberth-Ehrlich method (specifically for auto-correlation functions)

auto	aberth_autocorr_mt (const std::vector< double > &coeffs, std::vector< std::complex< double > > &zs, const Options &options) -> std::pair< unsigned int, bool >
	Multi-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.

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 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 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.

◆ aberth_autocorr_mt()

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

extern

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

The aberth_autocorr_mt function is a multi-threaded 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_mt 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_mt()

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

extern

Multi-threading Aberth-Ehrlich method.

The aberth_mt function is a multi-threaded implementation of the Aberth-Ehrlich method for finding the roots of a polynomial.

Multi-threaded variant of the Aberth-Ehrlich method:

\[ 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) \]

Each root is updated in parallel using separate threads.

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_mt 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()

double circle2_table_x ( unsigned long index )

extern

Circle sequence X-coordinate for an index.

\( x = \cos(2\pi \cdot \phi_2(\text{index})) \)

Parameters

[in] index Sequence index

Returns: double X-coordinate on the unit circle

◆ circle2_table_y()

double circle2_table_y ( unsigned long index )

extern

Circle sequence Y-coordinate for an index.

\( y = \sin(2\pi \cdot \phi_2(\text{index})) \)

Parameters

[in] index Sequence index

Returns: double Y-coordinate on the unit circle

◆ cos_pi_vdc2()

double cos_pi_vdc2 ( unsigned long index )

extern

Cosine of pi times van der Corput value.

\( \cos(\pi \cdot \phi_2(\text{index})) \)

Parameters

[in] index Sequence index

Returns: double cos(pi * vdc2_table(index))

◆ 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

◆ 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 )

extern

van der Corput sequence value for a given index

\( \phi_2(n) = \sum_{k=0}^{\infty} a_k(n) \, 2^{-k-1} \) where \( a_k(n) \) are the binary digits of \( n \).

Parameters

[in] index Sequence index

Returns: double The van der Corput value

Functions

Detailed Description

Function Documentation

◆ aberth()

◆ aberth_autocorr()

◆ aberth_autocorr_mt()

◆ aberth_mt()

◆ circle2_table_x()

◆ circle2_table_y()

◆ cos_pi_vdc2()

◆ initial_aberth()

◆ initial_aberth_autocorr()

◆ leja_order()

◆ poly_from_autocorr_roots()

◆ poly_from_roots()

◆ vdc2_table()