Struct winterfell::Matrix

pub struct Matrix<E> where
    E: FieldElement,  { /* private fields */ }

A two-dimensional matrix of field elements arranged in column-major order.

This struct is used as a backing type for many objects manipulated by the prover. The matrix itself does not assign any contextual meaning to the values stored in it. For example, columns may contain evaluations of polynomials, or polynomial coefficients, or really anything else. However, the matrix does expose a number of methods which make assumptions about the underlying data.

A matrix imposes the following restrictions on its content:

• A matrix must consist of at least 1 column and at least 2 rows.
• All columns must be of the same length.
• Number of rows must be a power of two.

Implementations

impl<E> Matrix<E> where
    E: FieldElement, 

pub fn new(columns: Vec<Vec<E, Global>, Global>) -> Matrix<E>

Returns a new Matrix instantiated with the data from the specified columns.

Panics

Panics if:

• The provided vector of columns is empty.
• Not all of the columns have the same number of elements.
• Number of rows is smaller than or equal to 1.
• Number of rows is not a power of two.

pub fn num_cols(&self) -> usize

Returns the number of columns in this matrix.

pub fn num_rows(&self) -> usize

Returns the number of rows in this matrix.

pub fn get(&self, col_idx: usize, row_idx: usize) -> E

Returns the element located at the specified column and row indexes in this matrix.

Panics

Panics if either col_idx or row_idx are out of bounds for this matrix.

pub fn set(&mut self, col_idx: usize, row_idx: usize, value: E)

Set the cell in this matrix at the specified column and row indexes to the provided value.

Panics

Panics if either col_idx or row_idx are out of bounds for this matrix.

pub fn get_column(&self, col_idx: usize) -> &[E]

Returns a reference to the column at the specified index.

pub fn get_column_mut(&mut self, col_idx: usize) -> &mut [E]

Returns a reference to the column at the specified index.

pub fn read_row_into(&self, row_idx: usize, row: &mut [E])

Copies values of all columns at the specified row into the specified row slice.

Panics

Panics if row_idx is out of bounds for this matrix.

pub fn update_row(&mut self, row_idx: usize, row: &[E])

Updates a row in this matrix at the specified index to the provided data.

Panics

Panics if row_idx is out of bounds for this matrix.

pub fn columns(&self) -> ColumnIter<'_, E>

Returns an iterator over the columns of this matrix.

pub fn columns_mut(&mut self) -> ColumnIterMut<'_, E>

Returns a mutable iterator over the columns of this matrix.

pub fn interpolate_columns(&self) -> Matrix<E>

Interpolates columns of the matrix into polynomials in coefficient form and returns the result.

The interpolation is performed as follows:

• Each column of the matrix is interpreted as evaluations of degree num_rows - 1 polynomial over a subgroup of size num_rows.
• Then each column is interpolated using iFFT algorithm into a polynomial in coefficient form.
• The resulting polynomials are returned as a single matrix where each column contains coefficients of a degree num_rows - 1 polynomial.

pub fn interpolate_columns_into(self) -> Matrix<E>

Interpolates columns of the matrix into polynomials in coefficient form and returns the result. The input matrix is consumed in the process.

The interpolation is performed as follows:

• Each column of the matrix is interpreted as evaluations of degree num_rows - 1 polynomial over a subgroup of size num_rows.
• Then each column is interpolated (in place) using iFFT algorithm into a polynomial in coefficient form.
• The resulting polynomials are returned as a single matrix where each column contains coefficients of a degree num_rows - 1 polynomial.

pub fn evaluate_columns_over(
    &self,
    domain: &StarkDomain<<E as FieldElement>::BaseField>
) -> Matrix<E>

Evaluates polynomials contained in the columns of this matrix over the specified domain and returns the result.

The evaluation is done as follows:

• Each column of the matrix is interpreted as coefficients of degree num_rows - 1 polynomial.
• These polynomials are evaluated over the LDE domain defined by the specified StarkDomain using FFT algorithm. The domain specification includes the size of the subgroup as well as the domain offset (to define a coset).
• The resulting evaluations are returned in a new Matrix.

pub fn evaluate_columns_at<F>(&self, x: F) -> Vec<F, Global> where
    F: FieldElement + From<E>, 

Evaluates polynomials contained in the columns of this matrix at a single point x.

pub fn commit_to_rows<H>(&self) -> MerkleTree<H> where
    H: ElementHasher<BaseField = <E as FieldElement>::BaseField>, 

Returns a commitment to this matrix.

The commitment is built as follows:

• Each row of the matrix is hashed into a single digest of the specified hash function.
• The resulting values are used to built a binary Merkle tree such that each row digest becomes a leaf in the tree. Thus, the number of leaves in the tree is equal to the number of rows in the matrix.
• The resulting Merkle tree is return as the commitment to the entire matrix.

pub fn into_columns(self) -> Vec<Vec<E, Global>, Global>

Returns the columns of this matrix as a list of vectors.

TODO: replace this with an iterator.

Trait Implementations

impl<E> Clone for Matrix<E> where
    E: Clone + FieldElement, 

fn clone(&self) -> Matrix<E>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<E> Debug for Matrix<E> where
    E: Debug + FieldElement, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.