ginger package

Submodules

ginger.aberth module

Aberth-Ehrlich method for simultaneous polynomial root-finding.

Aberth’s method (Ehrlich, 1967; Aberth, 1973) combines Newton’s method with an implicit deflation strategy to compute all roots of a polynomial simultaneously with cubic convergence. The correction formula is:

zᵢ’ = zᵢ - P(zᵢ) / P’(zᵢ)

P’(zᵢ) = P₁(zᵢ) - Σⱼ₌ᵢ P(zᵢ) / (zᵢ - zⱼ)

where P₁(z) is the derivative of P(z).

This module provides:

aberth — single-threaded Aberth method aberth_mt — multithreaded version aberth_autocorr — variant for autocorrelation (palindromic) polynomials initial_aberth — LDS-based initial guess generation poly_from_roots — reconstruct polynomial from roots (Leja ordering)

ginger.aberth.aberth(coeffs: ~typing.Sequence[float], zs: ~typing.List[complex], options: ~ginger.rootfinding.Options = <ginger.rootfinding.Options object>) → Tuple[List[complex], int, bool]

Aberth-Ehrlich simultaneous root-finding (single-threaded).

Combines Newton’s method with an implicit deflation strategy. Each root estimate \(z_i\) is updated by the correction:

\[z_i' = z_i - \frac{P(z_i)}{P'(z_i)}\]

where the derivative is modified by all other root estimates:

\[\begin{split}P'(z_i) = P_1(z_i) - \sum_{\substack{j=1\\j\neq i}}^n \frac{P(z_i)}{z_i - z_j}\end{split}\]

Here \(P_1(z)\) is the ordinary derivative of \(P(z)\). Convergence is cubic.

Parameters:

• coeffs – Polynomial coefficients in descending order

• zs – Initial root guesses

• options – Algorithm configuration

Returns:

Tuple of (final roots, iterations performed, converged)

Examples

>>> h = [5.0, 2.0, 9.0, 6.0, 2.0]
>>> z0s = initial_aberth(h)
>>> opt = Options()
>>> opt.tolerance = 1e-8
>>> zs, niter, found = aberth(h, z0s, opt)
>>> found
True

>>> h = [1.0, -1.0, -1.0, 1.0]
>>> z0s = initial_aberth(h)
>>> zs, niter, found = aberth(h, z0s)
>>> found
True

ginger.aberth.aberth_autocorr(coeffs: ~typing.Sequence[float], zs: ~typing.List[complex], options: ~ginger.rootfinding.Options = <ginger.rootfinding.Options object>) → Tuple[List[complex], int, bool]

Aberth method for palindromic (autocorrelation) polynomials.

Same as aberth() but additionally accounts for reciprocal root pairs \(z\) and \(1/\bar{z}\) in the correction:

\[\begin{split}P'(z_i) = P_1(z_i) - \sum_{\substack{j=1\\j\neq i}}^n \left(\frac{P(z_i)}{z_i - z_j} + \frac{P(z_i)}{z_i - 1/z_j}\right)\end{split}\]

This preserves the reciprocal-root structure of autocorrelation (palindromic) polynomials.

Parameters:

• coeffs – Polynomial coefficients in descending order

• zs – Initial root guesses

• options – Algorithm configuration

Returns:

Tuple of (refined roots, iterations, converged)

Examples

>>> h = [5.0, 2.0, 9.0, 6.0, 2.0]
>>> z0s = initial_aberth_autocorr(h)
>>> zs, niter, found = aberth_autocorr(h, z0s)
>>> opt = Options()
>>> opt.tolerance = 1e-8
>>> zs, niter, found = aberth_autocorr(h, z0s, opt)

ginger.aberth.aberth_autocorr_job(coeffs: Sequence[float], i: int, zsc: List[complex]) → Tuple[float, int, complex]

Worker for multithreaded autocorrelation Aberth — updates a single root.

Evaluates polynomial and derivative at zi, applies corrections from all other roots and their reciprocals, returns the updated value.

Parameters:

• coeffs – Polynomial coefficients in descending order

• i – Index of the root to update

• zsc – Current list of root estimates

Returns:

Tuple of (residual at zi, root index, new root estimate)

ginger.aberth.aberth_autocorr_mt(coeffs: ~typing.Sequence[float], zs: ~typing.List[complex], options: ~ginger.rootfinding.Options = <ginger.rootfinding.Options object>) → Tuple[List[complex], int, bool]

Multithreaded autocorrelation Aberth method.

Parallelizes root updates across threads, accounting for reciprocal root pairs in the correction step.

Parameters:

• coeffs – Polynomial coefficients in descending order

• zs – Initial root guesses

• options – Algorithm configuration

Returns:

Tuple of (refined roots, iterations, converged)

ginger.aberth.aberth_mt(coeffs: ~typing.Sequence[float], zs: ~typing.List[complex], options: ~ginger.rootfinding.Options = <ginger.rootfinding.Options object>) → Tuple[List[complex], int, bool]

Multithreaded Aberth method using ThreadPoolExecutor.

Parallelizes root updates across available CPUs while checking convergence in the main thread.

Parameters:

• coeffs – Polynomial coefficients in descending order

• zs – Initial root guesses

• options – Algorithm configuration

Returns:

Tuple of (refined roots, iterations, converged)

ginger.aberth.horner_backward(coeffs1: List, degree: int, alpha: complex) → complex

Backward Horner evaluation for root refinement.

Evaluates polynomial at x = α using coefficients in reverse order, modifying them in-place to center around α.

Parameters:

• coeffs1 – Polynomial coefficients in descending order (modified in-place)

• degree – Degree of the polynomial

• alpha – Center point for evaluation

Returns:

Value of the polynomial at α

Examples

>>> coeffs = [1.0, -6.7980, 2.9948, -0.043686, 0.000089248]
>>> degree = len(coeffs) - 1
>>> alpha = 6.3256
>>> p_eval = horner_backward(coeffs, degree, alpha)
>>> -p_eval * pow(alpha, 5)
-0.013355264987140483
>>> coeffs[3]
0.006920331351966613

ginger.aberth.initial_aberth(coeffs: Sequence[float]) → List[complex]

Generate initial root guesses using a low-discrepancy sequence.

The center \(c\) and radius \(R\) are derived from the coefficients:

\[\begin{split}c &= -\frac{a_1}{n a_0} \\[4pt] R &= \sqrt[n]{-P(c)} \\[4pt] z_i &= c + R \cdot (\cos\theta_i + i\sin\theta_i)\end{split}\]

where \(\theta_i = 2\pi v_i\) with \(v_i\) from a van der Corput sequence for low-discrepancy angular spacing.

Parameters:

coeffs – Polynomial coefficients in descending order

Returns:

Initial root guesses as complex numbers

Examples

>>> h = [5.0, 2.0, 9.0, 6.0, 2.0]
>>> z0s = initial_aberth(h)

ginger.aberth.initial_aberth_autocorr(coeffs: Sequence[float]) → List[complex]

Generate initial guesses for autocorrelation (palindromic) polynomials.

Adjusts radius to keep initial guesses within the unit circle, matching the reciprocal-root structure of autocorrelation polynomials.

Parameters:

coeffs – Polynomial coefficients in descending order

Returns:

Initial root guesses

Examples

>>> h = [5.0, 2.0, 9.0, 6.0, 2.0]
>>> z0s = initial_aberth_autocorr(h)

ginger.aberth.initial_aberth_autocorr_orig(coeffs: Sequence[float]) → List[complex]

Original trigonometric initial guess generator for autocorrelation polynomials.

Parameters:

coeffs – Polynomial coefficients in descending order

Returns:

Initial root guesses

Examples

>>> h = [5.0, 2.0, 9.0, 6.0, 2.0]
>>> z0s = initial_aberth_autocorr_orig(h)

ginger.aberth.initial_aberth_orig(coeffs: Sequence[float]) → List[complex]

Original trigonometric initial guess generator.

Places roots equally spaced around a circle with angular offset of 0.25 radians to avoid alignment with coordinate axes.

Parameters:

coeffs – Polynomial coefficients in descending order

Returns:

Initial root guesses as complex numbers

Examples

>>> h = [5.0, 2.0, 9.0, 6.0, 2.0]
>>> z0s = initial_aberth_orig(h)

ginger.aberth.leja_order(points: List[complex]) → List[complex]

Greedy Leja ordering for numerical stability.

Starts with \(p_0 = \arg\min |p|\), then iteratively selects:

\[p_k = \arg\max_{p \in \text{remaining}} \min_{q \in \text{selected}} |p - q|\]

This maximizes the minimum distance between successive points, improving numerical stability in polynomial reconstruction.

Parameters:

points – Input complex points

Returns:

Reordered points in Leja sequence

Examples

>>> pts = [1+0j, -1+0j, 0+1j, 0-1j]
>>> ordered = leja_order(pts)
>>> len(ordered)
4

ginger.aberth.poly_from_autocorr_roots(zs: List[complex]) → List[float]

Reconstruct a monic polynomial from autocorrelation roots.

Palindromic polynomials have roots in reciprocal pairs. This function adds 1/z for each root, then reconstructs via poly_from_roots().

Parameters:

zs – Roots from aberth_autocorr or aberth_autocorr_mt

Returns:

Monic polynomial coefficients (highest degree first)

Examples

>>> zs = [0.5+0.5j, 0.5-0.5j]
>>> coeffs = poly_from_autocorr_roots(zs)
>>> len(coeffs)
5

ginger.aberth.poly_from_roots(zs: List[complex]) → List[float]

Reconstruct a monic polynomial from its roots.

Orders roots with Leja ordering for stability, then convolves factors:

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

The coefficients are computed by repeated convolution, i.e.: starting from \([1]\), for each root \(r\):

\[c_{k+1} \leftarrow c_{k+1} - r \cdot c_k\]

Parameters:

zs – Roots of the polynomial

Returns:

Monic polynomial coefficients (highest degree first)

Examples

>>> coeffs = poly_from_roots([1+0j, -1+0j])
>>> coeffs
[1.0, 0.0, -1.0]

ginger.autocorr module

Bairstow root-finding specialized for autocorrelation (palindromic) polynomials.

Autocorrelation polynomials have symmetric coefficients and roots that come in reciprocal conjugate pairs. The algorithms in this module exploit this structure by processing only half the roots and handling reciprocal pairs in the suppression step.

Key functions:

pbairstow_autocorr — parallel Bairstow solver for palindromic polynomials initial_autocorr — generate initial guesses with reciprocal root structure extract_autocorr — normalize quadratic factors to unit-circle roots poly_from_autocorr_factors — reconstruct polynomial from autocorr factors

ginger.autocorr.extract_autocorr(vr: Vector2) → Vector2

Normalize quadratic factors to keep roots within the unit circle.

Given a quadratic \(x^2 - r x - q\), computes its roots and replaces any root \(|z| > 1\) with its reciprocal \(1/z\). The normalized factor is recovered from the adjusted roots via Vieta:

\[r' = z_1' + z_2',\qquad q' = -z_1' z_2'\]

where \(z_k' = z_k\) if \(|z_k| \le 1\), else \(z_k' = 1/z_k\).

Parameters:

vr – Quadratic coefficients \((r, q)\)

Returns:

Normalized quadratic with \(|z_k| \le 1\)

Examples

>>> vr = Vector2(5, -6)
>>> vr_new = extract_autocorr(vr)
>>> print(vr_new)
<0.8333333333333333, -0.16666666666666666>

ginger.autocorr.initial_autocorr(coeffs: List[float]) → List[Vector2]

Generate initial quadratic-factor estimates for autocorrelation polynomials.

For palindromic polynomials, roots come in reciprocal pairs. The radius is derived from the constant term and adjusted to focus on roots outside the unit circle:

\[\begin{split}R &= \sqrt[n]{|a_n|},\qquad R \leftarrow \max(R, 1/R) \\[4pt] \theta_k &= \frac{k\pi}{m},\qquad m = n/2 \\[4pt] (r_k, q_k) &= \bigl(2R\cos\theta_k,\; -R^2\bigr)\end{split}\]

Parameters:

coeffs – Polynomial coefficients in descending order

Returns:

Initial quadratic factors as Vector2 \((r,q)\)

Examples

>>> h = [10.0, 34.0, 75.0, 94.0, 150.0, 94.0, 75.0, 34.0, 10.0]
>>> vrs = initial_autocorr(h)

ginger.autocorr.pbairstow_autocorr(coeffs: ~typing.List[float], vrs: ~typing.List[~ginger.vector2.Vector2], options: ~ginger.rootfinding.Options = <ginger.rootfinding.Options object>) → Tuple[List[Vector2], int, bool]

Parallel Bairstow method for autocorrelation (palindromic) polynomials.

Handles reciprocal root pairs by applying suppression against both each root factor and its reciprocal.

Parameters:

• coeffs – Polynomial coefficients (degree must be even)

• vrs – Initial quadratic factor estimates

• options – Algorithm control parameters

Returns:

Tuple of (updated factors, iterations, converged)

Examples

>>> h = [10.0, 34.0, 75.0, 94.0, 150.0, 94.0, 75.0, 34.0, 10.0]
>>> vrs = initial_autocorr(h)
>>> vrs, niter, found = pbairstow_autocorr(h, vrs)
>>> found
True

ginger.autocorr.poly_from_autocorr_factors(vrs: List[Vector2]) → List[float]

Reconstruct a monic polynomial from autocorrelation quadratic factors.

Extracts all roots from each quadratic factor, adds reciprocals (for the palindromic structure), then reconstructs via aberth.poly_from_roots() with Leja ordering.

Parameters:

vrs – Quadratic factors from pbairstow_autocorr

Returns:

Monic polynomial coefficients (highest degree first)

Examples

>>> vrs = [Vector2(0.0, 1.0)]  # x^2 - 1 => roots 1, -1 => +reciprocals
>>> coeffs = poly_from_autocorr_factors(vrs)
>>> len(coeffs)
5

ginger.matrix2 module

2x2 matrix operations for polynomial root-finding algorithms.

This module provides the Matrix2 class which represents a 2x2 matrix with two Vector2 objects as rows. It is primarily used in Bairstow’s method for computing the adjustments to root estimates via matrix-vector operations and determinant calculations.

The matrix is stored in row-major order:

[[x.x, x.y],

[y.x, y.y]]

Example

>>> from ginger.vector2 import Vector2
>>> m = Matrix2(Vector2(1.0, 2.0), Vector2(3.0, 4.0))
>>> print(m.det())
-2.0

class ginger.matrix2.Matrix2(x: Vector2, y: Vector2)

Bases: object

A 2x2 matrix used in Bairstow’s correction step.

Each row is a Vector2. Provides matrix-vector multiplication (mdot()) and determinant (det()) for solving the 2x2 linear system in root estimate refinement.

x

The first row

Type:

Vector2

y

The second row

Type:

Vector2

Example

>>> m = Matrix2(Vector2(1.0, 2.0), Vector2(3.0, 4.0))
>>> print(m.mdot(Vector2(5.0, 6.0)))
<17.0, 39.0>
>>> print(m.det())
-2.0

det() → float

Matrix determinant.

\[\begin{split}\det\begin{bmatrix} a & b \\ c & d \end{bmatrix} = ad - bc\end{split}\]

Examples

>>> m = Matrix2(Vector2(1.0, 2.0), Vector2(3.0, 4.0))
>>> print(m.det())
-2.0

mdot(rhs: Vector2) → Vector2

Matrix-vector multiplication \(\mathbf{M} \cdot \mathbf{v}\).

\[\begin{split}\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} a_{11} v_1 + a_{12} v_2 \\ a_{21} v_1 + a_{22} v_2 \end{bmatrix}\end{split}\]

Parameters:

rhs – Right-hand side vector

Returns:

Result of matrix-vector product

Examples

>>> m = Matrix2(Vector2(1.0, 2.0), Vector2(3.0, 4.0))
>>> print(m.mdot(Vector2(5.0, 6.0)))
<17.0, 39.0>

property x: Vector2

First row of the matrix.

Examples

>>> m = Matrix2(Vector2(1.0, 2.0), Vector2(3.0, 4.0))
>>> print(m.x)
<1.0, 2.0>

property y: Vector2

Second row of the matrix.

Examples

>>> m = Matrix2(Vector2(1.0, 2.0), Vector2(3.0, 4.0))
>>> print(m.y)
<3.0, 4.0>

ginger.rootfinding module

Parallel Bairstow root-finding for real-coefficient polynomials.

This module implements a parallel version of Bairstow’s method for finding all roots of a polynomial simultaneously. The algorithm factors the polynomial into quadratic factors (x² - r·x - q), using suppression to decouple root estimates, enabling parallel refinement.

Key functions:

pbairstow_even — main parallel Bairstow solver initial_guess — generate starting estimates from coefficients suppress — decouple interference between root factors horner — evaluate polynomial against quadratic factor roots_from_quadratic — extract two roots from a quadratic factor

class ginger.rootfinding.Options

Bases: object

Configuration parameters for iterative root-finding algorithms.

max_iters

Maximum number of iterations (default 2000)

Type:

int

tolerance

Global convergence tolerance (default 1e-12)

Type:

float

tol_ind

Per-root convergence tolerance (default 1e-15)

Type:

float

max_iters: int = 2000

tol_ind: float = 1e-15

tolerance: float = 1e-12

ginger.rootfinding.delta(vA: Vector2, vr: Vector2, vp: Vector2) → Vector2

Calculate adjustment vector for Bairstow’s method.

Solves the 2×2 linear system to find the optimal adjustment to current quadratic factor estimates \((r,q)\):

\[\begin{split}\begin{bmatrix} r p + s & p \\ q p & s \end{bmatrix} \begin{bmatrix} \Delta r \\ \Delta q \end{bmatrix} = \begin{bmatrix} A \\ B \end{bmatrix}\end{split}\]

where \((p,s) = (r_i - r_j,\; q_i - q_j)\) is the difference between two factor estimates, and \((A,B)\) is the remainder from polynomial division.

Parameters:

• vA – Residual vector \((A,B)\) from polynomial division

• vr – Current root estimate \((r,q)\)

• vp – Suppression vector \((p,s) = \mathbf{vr}_i - \mathbf{vr}_j\)

Returns:

Correction vector \((\Delta r, \Delta q)\)

Examples

>>> d = delta(Vector2(1, 2), Vector2(-2, 0), Vector2(4, 5))
>>> print(d)
<0.2, 0.4>

ginger.rootfinding.find_rootq(vr: Vector2) → Tuple[float | complex, float | complex]

Solve \(x^2 - r x - q = 0\) using Vieta’s formula.

Uses the alternative (Citardauq) formula to avoid catastrophic cancellation when \(|r|\) is large:

\[\begin{split}x_1 &= \frac{r}{2} + \operatorname{sgn}\!\left(\frac{r}{2}\right) \sqrt{\left(\frac{r}{2}\right)^2 + q} \\[4pt] x_2 &= -\frac{q}{x_1} \qquad\text{(Vieta's formula)}\end{split}\]

Parameters:

vr – Quadratic coefficients \((r,q)\)

Returns:

The two roots

Examples

>>> vr = find_rootq(Vector2(5, -6))
>>> print(vr)
(3.0, 2.0)

ginger.rootfinding.horner(coeffs: List[float], degree: int, vr: Vector2) → Vector2

Synthetic division by a quadratic factor \(x^2 - r x - q\).

Performs polynomial division:

\[P(x) = Q(x)\cdot(x^2 - r x - q) + A x + B\]

Returns the linear remainder \((A,B)\) and overwrites coeffs with the quotient \(Q(x)\) (deflated polynomial).

The recurrence for the quotient coefficients \(b_k\) is:

\[\begin{split}b_0 &= a_0 \\ b_1 &= a_1 + r b_0 \\ b_k &= a_k + r b_{k-1} + q b_{k-2} \quad (k \ge 2)\end{split}\]

with remainder \(A = b_{n-1},\; B = b_n + q b_{n-1}\).

Parameters:

• coeffs – Polynomial coefficients in descending order (modified in-place)

• degree – Degree of the polynomial (must be ≥ 2)

• vr – Quadratic factor \((r,q)\)

Returns:

Remainder \((A,B)\)

Examples

>>> coeffs = [1, -8, -72, 382, 727, -2310]
>>> vp = horner(coeffs, 5, Vector2(-1, 6))  # x^2 + x - 6
>>> coeffs
[1, -9, -57, 385, 0, 0]
>>> coeffs = [1, -8, -72, 382, 727, -2310]
>>> vp = horner(coeffs, 5, Vector2(2, 3))  # x^2 - 2x - 3
>>> coeffs
[1, -6, -81, 202, 888, -1704]

ginger.rootfinding.horner_eval(coeffs: Sequence[float | complex], zval: float | complex) → Tuple[Any, List[float | complex]]

Evaluate polynomial via Horner, returning value and intermediate coefficients.

Parameters:

• coeffs – Polynomial coefficients in descending order of degree

• zval – Point at which to evaluate the polynomial

Returns:

Tuple of (polynomial value at zval, intermediate coefficients)

Examples

>>> coeffs = [1, -8, -72, 382, 727, -2310]
>>> horner_eval(coeffs, 3)
(960, [1, -5, -87, 121, 1090, 960])
>>> horner_eval(coeffs, 3+0j)
((960+0j), [1, (-5+0j), (-87+0j), (121+0j), (1090+0j), (960+0j)])

ginger.rootfinding.horner_eval_f(coeffs: Sequence[float | complex], zval: float | complex) → float | complex

Evaluate polynomial using Horner’s method (functional reduce version).

Parameters:

• coeffs – Polynomial coefficients in descending order of degree

• zval – Point at which to evaluate the polynomial

Returns:

Value of the polynomial at zval

Examples

>>> coeffs = [1, -8, -72, 382, 727, -2310]
>>> horner_eval_f(coeffs, 3)
960

ginger.rootfinding.initial_guess(coeffs: List[float]) → List[Vector2]

Generate initial quadratic-factor estimates for Bairstow’s method.

Estimates are placed around a circle centered at \(c\) with radius \(R\):

\[\begin{split}c &= -\frac{a_1}{n a_0},\qquad R = \sqrt[n]{|P(c)|} \\[4pt] \theta_k &= \pi \cdot \text{VDC}_2[k+1] \\[4pt] (r_k, q_k) &= \bigl(2(c + R\cos\theta_k),\; -(c^2 + R^2 + 2cR\cos\theta_k)\bigr)\end{split}\]

where \(\text{VDC}_2\) is a van der Corput low-discrepancy sequence.

Parameters:

coeffs – Polynomial coefficients in descending order

Returns:

List of initial quadratic factors as Vector2 \((r,q)\)

Examples

>>> h = [10.0, 34.0, 75.0, 94.0, 150.0, 94.0, 75.0, 34.0, 10.0]
>>> vr0s = initial_guess(h)

ginger.rootfinding.pbairstow_even(coeffs: ~typing.List[float], vrs: ~typing.List[~ginger.vector2.Vector2], options: ~ginger.rootfinding.Options = <ginger.rootfinding.Options object>) → Tuple[List[Vector2], int, bool]

Parallel Bairstow method for simultaneous root-finding.

Iteratively refines \(m = n/2\) quadratic factors of the polynomial using suppression to decouple estimates. Each factor \((r_i, q_i)\) is updated by solving a 2×2 system:

\[\begin{split}\begin{bmatrix} r_i \\ q_i \end{bmatrix}^{\!(k+1)} = \begin{bmatrix} r_i \\ q_i \end{bmatrix}^{\!(k)} - \begin{bmatrix} A'_1 r_i + B'_1 & A'_1 \\ A'_1 q_i & B'_1 \end{bmatrix}^{-1} \begin{bmatrix} A \\ B \end{bmatrix}\end{split}\]

where the “suppressed” derivative residuals are:

\[\begin{split}\begin{bmatrix} A'_1 \\ B'_1 \end{bmatrix} = \begin{bmatrix} A_1 \\ B_1 \end{bmatrix} - \sum_{j \neq i} \begin{bmatrix} p_{ij} r_i + s_{ij} & p_{ij} \\ p_{ij} q_i & s_{ij} \end{bmatrix}^{-1} \begin{bmatrix} A \\ B \end{bmatrix}\end{split}\]

with \((p_{ij}, s_{ij}) = (r_i - r_j,\; q_i - q_j)\).

Parameters:

• coeffs – Polynomial coefficients in descending order

• vrs – Initial estimates for quadratic factors

• options – Algorithm configuration parameters

Returns:

Tuple of (final root estimates, iterations performed, converged)

Examples

>>> h = [10.0, 34.0, 75.0, 94.0, 150.0, 94.0, 75.0, 34.0, 10.0]
>>> vr0s = initial_guess(h)
>>> vrs, niter, found = pbairstow_even(h, vr0s)
>>> print(found)
True

ginger.rootfinding.poly_from_quadratic_factors(vrs: List[Vector2]) → List[float]

Reconstruct a monic polynomial from its quadratic factors.

Each factor x² - r·x - q is converted to its two roots, and the full polynomial is reconstructed via aberth.poly_from_roots() with Leja ordering for numerical stability.

Parameters:

vrs – Quadratic factors from Bairstow’s method

Returns:

Monic polynomial coefficients (highest degree first)

Examples

>>> vrs = [Vector2(0.0, 1.0)]  # x^2 - 1
>>> coeffs = poly_from_quadratic_factors(vrs)
>>> coeffs
[1.0, 0.0, -1.0]

ginger.rootfinding.roots_from_quadratic(vr: Vector2) → Tuple[complex, complex]

Solve \(x^2 - r x - q = 0\) for its two roots.

Uses the quadratic formula:

\[x = \frac{r \pm \sqrt{r^2 + 4q}}{2}\]

Parameters:

vr – Vector2 with \(x=r, y=q\) representing \(x^2 - r x - q\)

Returns:

The two roots (real or complex conjugate pair)

Examples

>>> r1, r2 = roots_from_quadratic(Vector2(0, 1))  # x^2 - 1
>>> print(r1, r2)
1.0 -1.0
>>> r1, r2 = roots_from_quadratic(Vector2(0, -1))  # x^2 + 1
>>> abs(r1 - 1j) < 1e-14
True
>>> abs(r2 + 1j) < 1e-14
True

ginger.rootfinding.suppress(vA: Vector2, vA1: Vector2, vri: Vector2, vrj: Vector2) → Tuple[Vector2, Vector2]

Zero-suppression for decoupling Bairstow factor estimates.

Modifies the residual vectors \((A,B)\) and \((A_1,B_1)\) to suppress interference from another quadratic factor \((r_j, q_j)\). The adjugate matrix is:

\[\begin{split}\mathbf{M}^* = \begin{bmatrix} s & -p \\ -p q_i & p r_i + s \end{bmatrix}, \qquad \det(\mathbf{M}^*) = s(p r_i + s) - p^2 q_i\end{split}\]

where \((p,s) = (r_i - r_j,\; q_i - q_j)\). The modified residuals are:

\[\begin{split}\begin{bmatrix} A' \\ B' \end{bmatrix} &= \det(\mathbf{M}^*) \cdot \mathbf{M}^* \begin{bmatrix} A \\ B \end{bmatrix} \\[4pt] \begin{bmatrix} A'_1 \\ B'_1 \end{bmatrix} &= \mathbf{M}^*\bigl( \mathbf{M}^* \begin{bmatrix} A_1 \\ B_1 \end{bmatrix} - \begin{bmatrix} A' \\ B' \end{bmatrix} \bigr)\end{split}\]

Reference:

4. 3. Handscomb, Computer Journal, 5 (1962), pp. 139-141.

Parameters:

• vA – Current residual \((A,B)\)

• vA1 – Derivative residual \((A_1,B_1)\)

• vri – Current factor \((r_i,q_i)\)

• vrj – Other factor \((r_j,q_j)\)

Returns:

Modified residuals \((A',B')\) and \((A'_1,B'_1)\)

Examples

>>> vA = Vector2(3, 3)
>>> vA1 = Vector2(1, 2)
>>> vri = Vector2(-2, 0)
>>> vrj = Vector2(4, 5)
>>> vA, vA1 = suppress(vA, vA1, vri, vrj)
>>> dr = delta(vA, vri, vA1)
>>> print(dr)
<-16.78082191780822, 1.4383561643835616>

ginger.rootfinding.suppress_old(vA: Vector2, vA1: Vector2, vri: Vector2, vrj: Vector2) → None

Original zero suppression for Bairstow’s method (modifies in-place).

Modifies residual vectors vA and vA1 to suppress interference from other root estimates (vrj) during iteration.

Note: This original version modifies vectors in-place. The newer suppress() returns modified copies instead.

Parameters:

• vA – Current residual vector (A,B)

• vA1 – First derivative residual vector (A1,B1)

• vri – Current root estimate (ri,qi)

• vrj – Other root estimate (rj,qj)

Reference:

D. C. Handscomb, Computation of the latent roots of a Hessenberg matrix by Bairsow’s method, Computer Journal, 5 (1962), pp. 139-141.

Examples

>>> vA = Vector2(3, 3)
>>> vA1 = Vector2(1, 2)
>>> vri = Vector2(-2, 0)
>>> vrj = Vector2(4, 5)
>>> suppress_old(vA, vA1, vri, vrj)
>>> dr = delta(vA, vri, vA1)
>>> print(dr)
<-16.78082191780822, 1.4383561643835616>

ginger.skeleton module

This is a skeleton file that can serve as a starting point for a Python console script. To run this script uncomment the following lines in the [options.entry_points] section in setup.cfg:

console_scripts =
     fibonacci = ginger.skeleton:run

Then run pip install . (or pip install -e . for editable mode) which will install the command fibonacci inside your current environment.

Besides console scripts, the header (i.e. until _logger…) of this file can also be used as template for Python modules.

Note

This file can be renamed depending on your needs or safely removed if not needed.

References

• https://setuptools.pypa.io/en/latest/userguide/entry_point.html

• https://pip.pypa.io/en/stable/reference/pip_install

ginger.skeleton.fib(n: int) → int

Fibonacci example function

Parameters:

n (int) – integer

Returns:

n-th Fibonacci number

Return type:

int

ginger.skeleton.main(args: List[str]) → None

Wrapper allowing fib() to be called with string arguments in a CLI fashion

Instead of returning the value from fib(), it prints the result to the stdout in a nicely formatted message.

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--verbose", "42"]).

ginger.skeleton.parse_args(args: List[str]) → Namespace

Parse command line parameters

Parameters:

args (List[str]) – command line parameters as list of strings (for example ["--help"]).

Returns:

command line parameters namespace

Return type:

argparse.Namespace

ginger.skeleton.run() → None

Calls main() passing the CLI arguments extracted from sys.argv

This function can be used as entry point to create console scripts with setuptools.

ginger.skeleton.setup_logging(loglevel: int) → None

Setup basic logging

Parameters:

loglevel (int) – minimum loglevel for emitting messages

ginger.vector2 module

Two-dimensional vector class used across root-finding modules.

Vector2 represents an ordered pair (x, y) and provides arithmetic operations (dot product, addition, subtraction, scalar multiplication/division) needed by Bairstow’s and Aberth’s methods for storing quadratic factor coefficients and 2D residuals.

class ginger.vector2.Vector2(x: float, y: float)

Bases: object

A 2D vector class for mathematical vector operations.

This class represents a two-dimensional vector with x and y components. It provides basic vector operations like addition, subtraction, scalar multiplication, dot product, and string representation. The class uses slots for memory efficiency and implements proper operator overloading.

dot(rhs: Vector2) → float

Dot product of two 2D vectors.

\[\mathbf{v}_1 \cdot \mathbf{v}_2 = x_1 x_2 + y_1 y_2\]

Parameters:

rhs – The right-hand side vector

Returns:

The scalar dot product

Examples

>>> v1 = Vector2(1, 2)
>>> v2 = Vector2(3, 4)
>>> v1.dot(v2)
11

property x: float

Getter property for the x-component of the vector.

This property provides read-only access to the private _x attribute, maintaining encapsulation while allowing external access to the value.

Returns:

The x-component of the vector as a float

Return type:

float

Examples

>>> v = Vector2(3.0, 4.0)
>>> v.x
3.0

property y: float

Getter property for the y-component of the vector.

This property provides read-only access to the private _y attribute, maintaining encapsulation while allowing external access to the value.

Returns:

The y-component of the vector as a float

Return type:

float

Examples

>>> v = Vector2(3.0, 4.0)
>>> v.y
4.0

Module contents

ginger — Polynomial root-finding algorithms (parallelizable).

This package provides parallel implementations of Bairstow’s method and Aberth-Ehrlich’s method for finding all roots of real-coefficient polynomials. It is pure Python with no NumPy dependency.

Submodules:

rootfinding — parallel Bairstow method (pbairstow_even) aberth — Aberth-Ehrlich method (single-threaded and MT) autocorr — Bairstow solver for palindromic/autocorrelation polynomials vector2 — 2D vector class for quadratic factor coefficients matrix2 — 2x2 matrix class used in Bairstow correction