Skip to main content

Algebra

p3_field

Trait Algebra 

Source 
pub trait Algebra<F>:
    PrimeCharacteristicRing
    + From<F>
    + Add<F, Output = Self>
    + AddAssign<F>
    + Sub<F, Output = Self>
    + SubAssign<F>
    + Mul<F, Output = Self>
    + MulAssign<F> {
    const BATCHED_LC_CHUNK: usize = 8;

    // Provided methods
    fn mixed_dot_product<const N: usize>(a: &[Self; N], f: &[F; N]) -> Self
       where F: Dup { ... }
    fn batched_linear_combination(values: &[Self], coeffs: &[F]) -> Self
       where F: Dup { ... }
}
Expand description

A ring R implements Algebra<F> if there is an injective homomorphism from F into R; in particular only F::ZERO maps to R::ZERO.

For the most part, we will usually expect F to be a field but there are a few cases where it is handy to allow it to just be a ring. In particular, every ring naturally implements Algebra<Self>.

§Mathematical Description

Let x and y denote arbitrary elements of F. Then we require that our map from has the properties:

  • Preserves Identity: from(F::ONE) = R::ONE
  • Commutes with Addition: from(x + y) = from(x) + from(y)
  • Commutes with Multiplication: from(x * y) = from(x) * from(y)

Such maps are known as ring homomorphisms and are injective if the only element which maps to R::ZERO is F::ZERO.

The existence of this map makes R into an F-module and hence an F-algebra. If, additionally, R is a field, then this makes R a field extension of F.

Provided Associated Constants§

Source

const BATCHED_LC_CHUNK: usize = 8

Optimal chunk size for batched_linear_combination.

Override in implementations where a different chunk size is faster. Must be one of 1, 2, 4, 8, 16, 32, or 64; other values cause a compile error.

Provided Methods§

Source

fn mixed_dot_product<const N: usize>(a: &[Self; N], f: &[F; N]) -> Self
where F: Dup,

Dot product between algebra elements and base field scalars.

Given arrays a (algebra) and f (scalars), computes:

  result = a[0]*f[0] + a[1]*f[1] + ... + a[N-1]*f[N-1]

Uses a tree-structured summation to minimize dependency chains and maximize throughput on pipelined architectures.

Source

fn batched_linear_combination(values: &[Self], coeffs: &[F]) -> Self
where F: Dup,

Runtime-length linear combination: Σ values[i] * coeffs[i].

Like mixed_dot_product but for slices whose length is not known at compile time. Processes in chunks of BATCHED_LC_CHUNK, delegating each chunk to mixed_dot_product to leverage SIMD-specialized overrides.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§