Module interpolation 

Lagrange interpolation over structured (two-adic coset) and arbitrary evaluation domains.

Evaluates polynomials at out-of-domain points given their evaluations on the chosen domain.

Mathematical background (two-adic coset path)

Slight variation of this approach: https://hackmd.io/@vbuterin/barycentric_evaluation.

We start with the evaluations of a polynomial f over a coset gH of size N and want to compute f(z).

Observe that z^N - g^N is equal to 0 at all points in the coset. Thus (z^N - g^N)/(z - gh^i) is equal to 0 at all points except for gh^i where it is equal to:

  N * (gh^i)^{N - 1} = N * g^N * (gh^i)^{-1}.

Hence L_i(z) = h^i * (z^N - g^N)/(N * g^{N - 1} * (z - gh^i)) will be equal to 1 at gh^i and 0 at all other points in the coset. This means that we can compute f(z) as:

  sum_i L_i(z) f(gh^i) = (z^N - g^N)/(N * g^N) * sum_i gh^i/(z - gh^i) * f(gh^i)
                       = z * (z^N - g^N)/(N * g^N) * sum_i (1/(z - gh^i) - 1/z) * f(gh^i).

This second equality lets us trade off N extension-by-base multiplications for a single extension-by-extension multiplication, an extension inversion and N extension-by-extension subtractions. For large N this is worth it.

Thus we define the adjusted weights to be (1/(z - g*h^i) - 1/z) and work with these instead.

Arbitrary-domain path

For evaluation domains that are not a two-adic coset we fall back to the standard second-form barycentric formula with precomputed weights w_i = 1/prod_{j != i}(x_i - x_j). See InterpolateArbitrary for the matrix-level entry points and interpolate_lagrange for a single-polynomial convenience helper.

Traits

Interpolate

Barycentric Lagrange interpolation over two-adic cosets.

InterpolateArbitrary

Lagrange interpolation over arbitrary evaluation domains.

Functions

barycentric_weights

Computes barycentric weights w_i = 1 / prod_{j != i} (x_i - x_j).

compute_adjusted_weights

Subtract z^{-1} from each inverse denominator to produce adjusted barycentric weights.

interpolate_lagrange

Interpolates a single polynomial from (x, y) pairs.