Algorithms Package

Class FinderAlgorithm from the package pyzeal_algorithms.

This module defines an abstract class/interface for a generic root finding algorithm. This builds the foundation for the primary user-facing API of PyZEAL.

Authors:

• Philipp Schuette

class pyzeal.algorithms.finder_algorithm.FinderAlgorithm(*args, **kwargs)

Abstract class representation of a generic root finding algorithm. Concrete algorithms are implemented by subclassing this class and overriding the virtual method calcRoots appropriately.

abstract calcRoots(context)

Entry point for a generic root finding algorithm operating in a given context. Found roots are expected to be inserted into context.container upon the algorithms completion.

Parameters:

context (RootContext) – Context in which the algorithm operates.

Return type:

None

Class FinderAlgorithm from the package pyzeal_algorithms. This module defines a simple root finding algorithm that works on any continuously differentiable function by constructing a supporting grid in the complex plane and starting an ordinary Newton algorithm at these support points. It is expected that this approach underperforms in compared to algorithms which fully exploit the holomorphic nature of target functions.

Authors:

• Philipp Schuette

• Luca Wasmuth

class pyzeal.algorithms.newton_grid.NewtonGridAlgorithm(numSamplePoints=50)

Class representation of a root finding algorithm for holomorphic functions based on starting an ordinary Newton algorithm on a grid of support points in the complex plane.

__init__(numSamplePoints=50)

Initialize a root finding algorithm which searches for roots using the Newton algorithm with starting points on an evenly spaced grid.

Parameters:

numSamplePoints (int) – Number of support points in grid rows/columns. (default: 50)

calcRoots(context)

Calculate roots in a given context based on the Newton algorithm on a grid of support points in the complex plane.

Parameters:

context (RootContext) – Context in which the algorithm operates.

Return type:

None

Class SimpleHoloAlgorithm from the package pyzeal_algorithms. This module defines a root finding algorithm based on a simple, straight forward approach to the argument principle. The simplicity comes from the fact that we avoid numeric quadrature by approximating integration of the logarithmic derivative via changes in the complex argument of the target function. Due to the possibility of overlooking large changes in the complex argument this algorithm is not completely reliable, see [Henrici].

Authors:

• Philipp Schuette

class pyzeal.algorithms.simple_holo.SimpleArgumentAlgorithm(estimatorType, *, numPts=6500, deltaPhi=0.01, maxPrecision=1e-10)

Class representation of a simple root finding algorithm for holomorphic functions based on the argument principle and the approximation of integrals over logarithmic derivatives via the summation of phase differences.

__init__(estimatorType, *, numPts=6500, deltaPhi=0.01, maxPrecision=1e-10)

Initialize a root finding algorithm that employs a straightforward, simple adaptation of the argument principle by refining an initial bounding rectangle until it either contains no further roots or it is smaller in size than the requested accuracy.

Parameters:

• numPts (int) – the default number of support points on rectangle edges (default: 6500) at the start of dynamic refinement

• deltaPhi (float) – the maximal phase shift between neighboring points on (default: 0.01) rectangle edges before dynamic refinement starts

• maxPrecision (float) – the minimal distance between neighboring points on (default: 1e-10) rectangle edges during dynamic refinement

calcRoots(context)

Start a root calculation using a straightforward argument principle based refinement strategy.

This routine calculates the initially expected number of roots by delegating the argument calculation to its ArgumentEstimator instance. Then it delegates the actual work of recursive refinement to the routines decideRefinement and calcRootsRecursion.

Parameters:

context (RootContext) – context in which the algorithm operates

Return type:

None

calculateRefinedMoment(reRan, imRan, context)

Recursively calculate roots in the given search range according to context.

Parameters:

• reRan (Tuple[float, float]) – Real part of current search range

• imRan (Tuple[float, float]) – Imaginary part of current search range

• context (RootContext) – RootContext in which the algorithm operates

Return type:

float

decideRefinement(reRan, imRan, phi, context)

Decide which way the current search area should be subdivided and calculate roots in the subdivided areas. The simple strategy consists of the choices (1) return, if argument indicates no roots, (2) place root in context.container if roots present and accuracy attained, or (3) subdivide further if roots present but accuracy not yet attained.

Parameters:

• reRan (Tuple[float, float]) – Real part of current search Range

• imRan (Tuple[float, float]) – Imaginary part of current search range

• phi (float) – Change in argument along the boundary of the current range

• context (RootContext) – RootContext in which the algorithm operates

Return type:

None

static getRootFromRectangle(right, left, top, bottom, phi, context)

Compute the location of a root in a sufficiently small rectangle and update the progress bar accordingly.

Parameters:

• right (float) – right boundary of the rectangle

• left (float) – left boundary of the rectangle

• top (float) – top boundary of the rectangle

• bottom (float) – bottom boundary of the rectangle

• phi (float) – the total argument within the rectangle

• context (RootContext) – overall context of the current calculation

Return type:

None

Class SimpleArgumentNewtonAlgorithm from the package pyzeal_algorithms.

This module defines a refined version of the SimpleArgumentAlgorithm by supplementing the argument principle with a Newton algorithm once a starting point has been identified with sufficient accuracy.

Authors:

• Philipp Schuette

class pyzeal.algorithms.simple_holo_newton.SimpleArgumentNewtonAlgorithm(estimatorType, *, numPts=6500, deltaPhi=0.01, maxPrecision=1e-10)

Class representation of a root finding algorithm combining the phase interpretation of the argument principle used in SimpleArgumentAlgorithm with a number of Newton steps once a sufficient refinement depth has been reached.

decideRefinement(reRan, imRan, phi, context)

Decide which way the current search area should be subdivided and calculate roots in the subdivided areas. The simple strategy consists of the choices (1) return, if argument indicates no roots, (2) place root in context.container if roots present and accuracy attained, (3) start Newton algorithm if simple root present and sufficent accuracy attained, or (4) subdivide further if multiple roots present or attained accuracy insufficient for Newton algorithm.

Parameters:

• reRan (Tuple[float, float]) – Real part of current search Range

• imRan (Tuple[float, float]) – Imaginary part of current search range

• phi (float) – Change in argument along the boundary of the current range

• context (RootContext) – RootContext in which the algorithm operates

Return type:

None

Class AssociatedPolynomialAlgorithm from the package pyzeal_algorithms.

This module defines a root finding algorithm based on associated polynomials whose coefficients are calculated from higher moments of the logarithmic derivative using Newton’s identities. Our implementation follows the original ideas of [Delves, Lyness].

Authors:

• Philipp Schuette

class pyzeal.algorithms.polynomial_holo.AssociatedPolynomialAlgorithm(estimatorType, *, numPts=6500, deltaPhi=0.01, maxPrecision=1e-10)

Class representation of a root finding algorithm which uses numerical quadrature to calculate higher moments. Then Newton’s identities can be used to calculate the associated polynomial from these moments. The zeros of the latter coincide with the zeros of the original target function.

coefficientsFromMoments(moments)

Calculate the coefficients of the associated polynomial from the higher moments (=power sums of roots) using Newton’s identities.

Parameters:

moments (List[complex]) – moments/power sums of roots

Returns:

List[complex] – coefficients of the associated polynomial

decideRefinement(reRan, imRan, phi, context)

Decide which way the current search area should be subdivided and calculate roots in the subdivided areas. The simple strategy consists of the choices (1) return, if argument indicates no roots, (2) place root in context.container if roots present and accuracy attained, (3) construct and solve Newton identities if only a few roots present, or (4) subdivide further if too many roots present.

Parameters:

• reRan (Tuple[float, float]) – Real part of current search Range

• imRan (Tuple[float, float]) – Imaginary part of current search range

• phi (float) – Change in argument along the boundary of the current range

• context (RootContext) – RootContext in which the algorithm operates

Return type:

None