Trait Interpolate 

pub trait Interpolate<F: TwoAdicField>: Matrix<F> {
    // Provided methods
    fn interpolate_subgroup<EF: ExtensionField<F>>(&self, point: EF) -> Vec<EF> { ... }
    fn interpolate_coset<EF: ExtensionField<F>>(
        &self,
        shift: F,
        point: EF,
    ) -> Vec<EF> { ... }
    fn interpolate_coset_with_precomputation<EF: ExtensionField<F>>(
        &self,
        shift: F,
        point: EF,
        adjusted_weights: &[EF],
    ) -> Vec<EF> { ... }
}

Barycentric Lagrange interpolation over two-adic cosets.

Blanket-implemented for every matrix over a two-adic field. Import the trait, then call the methods directly on any matrix.

Provided Methods

fn interpolate_subgroup<EF: ExtensionField<F>>(&self, point: EF) -> Vec<EF>

Evaluate a batch of polynomials at a point outside the canonical subgroup.

Convenience wrapper that uses shift = 1.

Safety

The evaluation point must not lie in the subgroup.

fn interpolate_coset<EF: ExtensionField<F>>( &self, shift: F, point: EF, ) -> Vec<EF>

Evaluate a batch of polynomials at a point outside a shifted coset.

Builds the coset, batch-inverts the denominators, converts to adjusted weights, and evaluates — all in one call.

Evaluations must be in standard (not bit-reversed) order.

Safety

The evaluation point must not lie in the coset.

fn interpolate_coset_with_precomputation<EF: ExtensionField<F>>( &self, shift: F, point: EF, adjusted_weights: &[EF], ) -> Vec<EF>

Fastest interpolation path — zero allocation beyond the result vector.

Given evaluations of a batch of polynomials over the given coset of the canonical power-of-two subgroup, evaluate the polynomials at point.

This method takes the precomputed adjusted_weights and should be preferred over interpolate_coset when repeatedly called with the same subgroup and/or point.

Overview

Each adjusted weight encodes the identity:

  g*h^i / (z - g*h^i)  =  z * adjusted_i

so the full barycentric formula becomes:

  f(z)  =  z * (z^N - g^N) / (N * g^N)  *  sum_i  adjusted_i * f(g*h^i)

The inner sum is a single SIMD-optimized column-wise dot product. The outer scalar is computed with one base-field inversion.

Safety

• The evaluation point must not lie in the coset.
• Each weight must equal 1/(z - x_i) - 1/z for the corresponding coset element.

Performance

• One base-field inversion (for N * g^N).
• log_2(N) extension-field squarings (for z^N).
• log_2(N) base-field squarings (for g^N).
• One SIMD-parallel column-wise dot product over the full matrix.
• No heap allocation except the result vector.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors

impl<F: TwoAdicField, M: Matrix<F>> Interpolate<F> for M