autocorr.hpp File Reference

Auto-correlation polynomial root-finding (palindromic polynomials) More...

#include <utility>
#include <vector>
#include "matrix2.hpp"
#include "rootfinding.hpp"
#include "vector2.hpp"

Include dependency graph for autocorr.hpp:

Go to the source code of this file.

Functions
auto	initial_autocorr (const std::vector< double > &coeffs) -> std::vector< Vec2 >
	Initial guess for the parallel Bairstow method (specific for auto-correlation function)
auto	pbairstow_autocorr_st (const std::vector< double > &coeffs, std::vector< Vec2 > &vrs, const Options &options) -> std::pair< unsigned int, bool >
	Multi-threading Bairstow's method (specific for auto-correlation function)
auto	pbairstow_autocorr_mt (const std::vector< double > &coeffs, std::vector< Vec2 > &vrs, const Options &options) -> std::pair< unsigned int, bool >
auto	pbairstow_autocorr (const std::vector< double > &coeffs, std::vector< Vec2 > &vrs, const Options &options) -> std::pair< unsigned int, bool >
void	extract_autocorr (Vec2 &vr)
	Extract autocorrelation quadratic factor.
auto	poly_from_autocorr_factors (const std::vector< Vec2 > &vrs) -> std::vector< double >
	Reconstruct a monic polynomial from its autocorrelation quadratic factors.

Detailed Description

Auto-correlation polynomial root-finding (palindromic polynomials)

Function Documentation

extract_autocorr()

void extract_autocorr ( Vec2 &  vr )

extern

Extract autocorrelation quadratic factor.

Converts a quadratic factor of the form \( x^2 - r x - q \) to the autocorrelation form \( (-1/q) + (r/q) x + x^2 \) where the roots appear in reciprocal pairs.

Quadratic factor relations:

\[ x^2 - r x - q = (x - a_1)(x - a_2) = x^2 - (a_1 + a_2)x + a_1 a_2 \]

\[ x^2 + r x + t = (x + a_1)(x + a_2) = x^2 + (a_1 + a_2)x + a_1 a_2 \]

For autocorrelation polynomials, the transformed factor has roots \( a_i \) and \( 1/a_i \).

Parameters

[in,out]

vr

Quadratic factor Vec2 (r, q) modified in-place

initial_autocorr()

auto initial_autocorr ( const std::vector< double > &  coeffs ) -> std::vector< Vec2 >

extern

Initial guess for the parallel Bairstow method (specific for auto-correlation function)

The function initial_autocorr calculates the initial quadratic factors for finding the roots of a palindromic (auto-correlation) polynomial.

\[ x^2 - r_k x - q_k, \quad r_k = 2\cos(2\pi\phi_2(k)), \quad q_k = -1, \quad k = 0,\dots,\lfloor n/2\rfloor \]

Parameters

[in]

coeffs

The parameter coeffs is a vector of doubles.

Returns

The function initial_autocorr returns a vector of Vec2 objects.

pbairstow_autocorr()

auto pbairstow_autocorr ( const std::vector< double > &  coeffs, std::vector< Vec2 > &  vrs, const Options &  options  ) -> std::pair<unsigned int, bool>

inline

pbairstow_autocorr_mt()

auto pbairstow_autocorr_mt ( const std::vector< double > &  coeffs, std::vector< Vec2 > &  vrs, const Options &  options  ) -> std::pair< unsigned int, bool >

extern

pbairstow_autocorr_st()

auto pbairstow_autocorr_st ( const std::vector< double > &  coeffs, std::vector< Vec2 > &  vrs, const Options &  options  ) -> std::pair< unsigned int, bool >

extern

Multi-threading Bairstow's method (specific for auto-correlation function)

The function pbairstow_autocorr implements Bairstow's method for finding the roots of a palindromic (auto-correlation) polynomial using multi-threading.

Each thread finds a quadratic factor \( x^2 - r_i x - q_i \) that respects the palindromic symmetry, where the roots appear in reciprocal pairs:

\[ \begin{bmatrix} \Delta r_i \\ \Delta q_i \end{bmatrix} = -J_i^{-1} \begin{bmatrix} P_i \\ Q_i \end{bmatrix} \]

Parameters

[in]	coeffs	polynomial
[in,out]	vrs	vector of iterates
[in]	options	maximum iterations and tolorance

Returns

std::pair<unsigned int, bool>

poly_from_autocorr_factors()

auto poly_from_autocorr_factors ( const std::vector< Vec2 > &  vrs ) -> std::vector< double >

extern

Reconstruct a monic polynomial from its autocorrelation quadratic factors.

Auto-correlation (palindromic) polynomials have roots in reciprocal pairs. Each quadratic factor \( x^2 - r_i x - q_i \) found by pbairstow_autocorr carries 2 roots. This function adds the reciprocal of each root, then reconstructs the full monic polynomial with Leja ordering for numerical accuracy.

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

Parameters

[in]

vrs

Quadratic factors from pbairstow_autocorr

Returns

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