Struct miden_processor::ColMatrix
source · pub struct ColMatrix<E>where
E: FieldElement,{ /* private fields */ }Expand description
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§
source§impl<E> ColMatrix<E>where
E: FieldElement,
impl<E> ColMatrix<E>where
E: FieldElement,
sourcepub fn new(columns: Vec<Vec<E>>) -> ColMatrix<E>
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.
sourcepub fn num_base_cols(&self) -> usize
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.
sourcepub fn get(&self, col_idx: usize, row_idx: usize) -> E
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.
sourcepub fn get_base_element(
&self,
base_col_idx: usize,
row_idx: usize
) -> <E as FieldElement>::BaseField
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.
sourcepub fn set(&mut self, col_idx: usize, row_idx: usize, value: E)
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.
sourcepub fn get_column(&self, col_idx: usize) -> &[E]
pub fn get_column(&self, col_idx: usize) -> &[E]
Returns a reference to the column at the specified index.
sourcepub fn get_column_mut(&mut self, col_idx: usize) -> &mut [E]
pub fn get_column_mut(&mut self, col_idx: usize) -> &mut [E]
Returns a reference to the column at the specified index.
sourcepub fn read_row_into(&self, row_idx: usize, row: &mut [E])
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.
sourcepub fn update_row(&mut self, row_idx: usize, row: &[E])
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.
sourcepub fn merge_column(&mut self, column: Vec<E>)
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.
sourcepub fn columns(&self) -> ColumnIter<'_, E>
pub fn columns(&self) -> ColumnIter<'_, E>
Returns an iterator over the columns of this matrix.
sourcepub fn columns_mut(&mut self) -> ColumnIterMut<'_, E>
pub fn columns_mut(&mut self) -> ColumnIterMut<'_, E>
Returns a mutable iterator over the columns of this matrix.
sourcepub fn interpolate_columns(&self) -> ColMatrix<E>
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 - 1polynomial over a subgroup of sizenum_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 - 1polynomial.
sourcepub fn interpolate_columns_into(self) -> ColMatrix<E>
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 - 1polynomial over a subgroup of sizenum_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 - 1polynomial.
sourcepub fn evaluate_columns_over(
&self,
domain: &StarkDomain<<E as FieldElement>::BaseField>
) -> ColMatrix<E>
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 - 1polynomial. - 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.
sourcepub fn evaluate_columns_at<F>(&self, x: F) -> Vec<F>where
F: FieldElement + From<E>,
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.
sourcepub fn commit_to_rows<H>(&self) -> MerkleTree<H>
pub fn commit_to_rows<H>(&self) -> MerkleTree<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 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.
sourcepub fn into_columns(self) -> Vec<Vec<E>>
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.