polynomials.newton#

This module provides computational routines relevant to polynomials in the Newton basis.

minterpy.utils.polynomials.newton.eval_newton_monomials(x, exponents, generating_points, verify_input=False, triangular=False)[source]#

Newton evaluation function.

Compute the value of each Newton monomial on each given point. Internally it uses numba accelerated evaluation function.

Parameters:

  • x (np.ndarray) – The points to evaluate the polynomials on.

  • exponents (np.ndarray) – the multi indices “alpha” for every Newton polynomial corresponding to the exponents of this “monomial”

  • generating_points (np.ndarray) – Nodes where the Newton polynomial lives on. (Or the points which generate these nodes?!)

  • verify_input (bool) – weather the data types of the input should be checked. Turned off by default for performance.

  • triangular (bool) – weather or not the output will be of lower triangular form. This will skip the evaluation of some values. Defaults to False.

Returns:

the value of each Newton polynomial on each point. The output shape is (k, N), where k is the number of points and N is the number of coeffitions of the Newton polyomial.

Return type:

np.ndarray

See also

eval_all_newt_polys

concrete numba accelerated implementation of polynomial evaluation in Newton base.

minterpy.utils.polynomials.newton.eval_newton_polynomials(xx, coefficients, exponents, generating_points, verify_input=False, batch_size=None)[source]#

Evaluate the polynomial(s) in Newton form at multiple query points.

Iterative implementation of polynomial evaluation in Newton form

This version able to handle both:

  • list of input points x (2D input)

  • list of input coefficients (2D input)

Here we use the notations:

  • n = polynomial degree

  • N = amount of coefficients

  • k = amount of points

  • p = amount of polynomials

Parameters:

  • xx (np.ndarray) – Arguemnt array with shape (m, k) the k points to evaluate on with dimensionality m.

  • coefficients (np.ndarray, shape = (N, p)) – The coefficients of the Newton polynomials. NOTE: format fixed such that ‘lagrange2newton’ conversion matrices can be passed as the Newton coefficients of all Lagrange monomials of a polynomial without prior transponation

  • exponents (np.ndarray, shape = (m, N)) – a multi index alpha for every Newton polynomial corresponding to the exponents of this monomial

  • generating_points (np.ndarray, shape = (m, n+1)) – Grid values for every dimension (e.g. Leja ordered Chebychev values). the values determining the locations of the hyperplanes of the interpolation grid. the ordering of the values determine the spacial distribution of interpolation nodes. (relevant for the approximation properties and the numerical stability).

  • verify_input (bool, optional) – weather the data types of the input should be checked. turned off by default for speed.

  • batch_size (int, optional) – batch size of query points

Raises:

TypeError – If the input generating_points do not have dtype = float.

Returns:

(k, p) the value of each input polynomial at each point. TODO squeezed into the expected shape (1D if possible). Notice, format fixed such that the regression can use the result as transformation matrix without transponation

Notes

  • This method is faster than the recursive implementation of tree.eval_lp(...) for a single point and a single polynomial (1 set of coeffs):

    • time complexity: \(O(mn+mN) = O(m(n+N)) = ...\)

    • pre-computations: \(O(mn)\)

    • evaluation: \(O(mN)\)

    • space complexity: \(O(mn)\) (precomputing and storing the products)

    • evaluation: \(O(0)\)

  • advantage:

    • just operating on numpy arrays, can be just-in-time (jit) compiled

    • can evaluate multiple polynomials without recomputing all intermediary results

See also

evaluate_multiple

numba accelerated implementation which is called internally by this function.

convert_eval_output

numba accelerated implementation of the output converter.

minterpy.utils.polynomials.newton.eval_newton_polynomials_batch(xx, coefficients, exponents, generating_points, batch_size)[source]#

Evaluate the polynomial in Newton form in batches of query points.

Notes

  • It is assumed that the inputs have all been verified and rectified.

  • It would be more expensive to evaluate smaller batch sizes but with a smaller memory footprint in any given iteration.

  • If memory does not permit whole evaluation of query points, consider using smaller but not the smallest batch size (i.e., not 1).

Parameters:
minterpy.utils.polynomials.newton.deriv_newt_eval(x, coefficients, exponents, generating_points, derivative_order_along)[source]#

Evaluate the derivative of a polynomial in the Newton form.

m = spatial dimension n = polynomial degree N = number of coefficients p = number of polynomials k = number of evaluation points

Parameters:

  • x ((k, m) the k points to evaluate on with dimensionality m.)

  • coefficients ((N, p) the coefficients of the Newton polynomial(s).)

  • exponents ((m, N) a multi index "alpha" for every Newton polynomial) – corresponding to the exponents of this “monomial”

  • generating_points ((m, n+1) grid values for every dimension (e.g. Leja ordered Chebychev values).)

  • derivative_order_along

  • [2 (eg.)

  • 3

  • order (3rd)

  • order

  • dimensions (and 1st order along spatial)

  • 0

  • 1

  • 2. (and)

Return type:

  1. the value of derivative of the polynomial evaluated at each point.

Notes

  • Can compute derivative polynomials without transforming to canonical basis.

  • This derivative evaluation is done by taking derivatives of the Newton monomials.

  • JIT compilation using Numba was not used here as combinations() from the itertools module does not work with Numba.

  • Due to multiple nested loops this implementation is very slow except for a small problem (small dimension and small polynomial degree).

minterpy.utils.polynomials.newton.integrate_monomials_newton(exponents, generating_points, bounds)[source]#

Integrate the monomials in the Newton basis given a set of exponents.

Parameters:

  • exponents (numpy.ndarray) – A set of exponents from a multi-index set that defines the polynomial, an (N, M) array, where N is the number of exponents (multi-indices) and M is the number of spatial dimensions. The number of exponents corresponds to the number of monomials.

  • generating_points (numpy.ndarray) – A set of generating points of the interpolating polynomial, a (P + 1, M) array, where P is the maximum degree of the polynomial in any dimensions and M is the number of spatial dimensions.

  • bounds (numpy.ndarray) – The bounds (lower and upper) of the definite integration, an (M, 2) array, where M is the number of spatial dimensions.

Returns:

The integrated Newton monomials, an (N,) array, where N is the number of monomials (exponents).

Return type:

numpy.ndarray