Struct ColMatrix

pub struct ColMatrix<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> ColMatrix<E>

where E: FieldElement,

pub fn new(columns: Vec<Vec<E>>) -> ColMatrix<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_base_cols(&self) -> usize

Returns the number of base field columns in this matrix.

The number of base field columns is defined as the number of columns multiplied by the extension degree of field elements contained 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 get_base_element( &self, base_col_idx: usize, row_idx: usize, ) -> <E as FieldElement>::BaseField

Returns base field elements located at the specified column and row indexes in this matrix.

For STARK fields, base_col_idx is the same as col_idx used in Self::get method. For extension fields, each column in the matrix is viewed as 2 or more columns in the base field.

Thus, for example, if we are in a degree 2 extension field, base_col_idx = 0 would refer to the first base element of the first column, base_col_idx = 1 would refer to the second base element of the first column, base_col_idx = 2 would refer to the first base element of the second column etc.

Panics

Panics if either base_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 merge_column(&mut self, column: Vec<E>)

Merges a column to the end of the matrix provided its length matches the matrix.

Panics

Panics if the column has a different length to other columns in the matrix.

pub fn remove_column(&mut self, index: usize) -> Vec<E>

Removes a column of the matrix given its index.

Panics

Panics if the column index is out of range.

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) -> ColMatrix<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) -> ColMatrix<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>, ) -> ColMatrix<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>

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, V>(&self) -> V

where H: ElementHasher<BaseField = <E as FieldElement>::BaseField>, V: VectorCommitment<H>,

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 vector of digests is committed to using the specified vector commitment scheme.
• The resulting commitment is returned as the commitment to the entire matrix.

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

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

TODO: replace this with an iterator.

Trait Implementations

impl<E> Clone for ColMatrix<E>

where E: Clone + FieldElement,

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<E> Debug for ColMatrix<E>

where E: Debug + FieldElement,

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

Formats the value using the given formatter.