Skip to content
Snippets Groups Projects

Draft: Doc joss

Closed Draft: Doc joss
doc-joss into main
Closed PERENNOU Tanguy requested to merge doc-joss into main
Viewing commit 9f5f32c7
Prev Next
Show latest version
1 file
+ 240
− 83
Compare changes
  • Side-by-side
  • Inline
src/algebra/linalg.rs
+ 240
− 83
//! some linear algebra fun
//!
//! this module mainly contains an implementation of matrices over a finite
//! This module mainly contains an implementation of matrices over a finite
//! field.
use ark_ff::Field;
use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
@@ -8,9 +8,10 @@ use ark_std::rand::{Rng, RngCore};
use crate::error::KomodoError;
/// a matrix defined over a finite field
/// A matrix defined over a finite field, as defined in [`ark_ff::Field`], e.g.
/// [`ark_bls12_381::Fr`] (FIXME: fix doc link to `ark_bls12_381::Fr`).
///
/// internally, a matrix is just a vector of field elements that whose length is
/// Internally, a matrix is just a vector of field elements whose length is
/// exactly the width times the height and where elements are organized row by
/// row.
#[derive(Clone, PartialEq, Default, Debug, CanonicalSerialize, CanonicalDeserialize)]
@@ -64,45 +65,50 @@ impl<T: Field> Matrix<T> {
Self::from_diagonal(vec![T::one(); size])
}
/// build a Vandermonde matrix for some seed points
/// Build a Vandermonde matrix over a finite field for some seed points,
/// checking that the seed points are distinct.
///
/// actually, this is the tranpose of the Vandermonde matrix defined in the
/// Actually, this is the tranpose of the Vandermonde matrix defined in the
/// [Wikipedia article][article], i.e. there are as many columns as there
/// are seed points and there are as many rows as there are powers of the
/// seed points.
///
/// > **Note**
/// > if you are sure the points are distinct and don't want to perform any
/// > runtime check to ensure that condition, have a look at
/// > **Note** : if you are sure the points are distinct and don't want to
/// > perform any runtime check to ensure that condition, have a look at
/// > [`Self::vandermonde_unchecked`].
///
/// # Example
/// ```rust
/// # use ark_ff::Field;
/// # use komodo::algebra::linalg::Matrix;
/// use komodo::algebra::linalg::Matrix;
/// use ark_bls12_381::Fr;
/// use ark_ff::Field;
/// // helper to convert integers to field elements
/// fn vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T>
/// # {
/// # elements.iter().map(|&x| T::from(x)).collect()
/// # }
/// # type T = ark_bls12_381::Fr;
/// fn vec_to_elements<T: Field>(vec: Vec<u128>) -> Vec<T> {
/// vec.iter().map(|&x| T::from(x)).collect()
/// }
///
/// let seed_points = vec_to_elements(vec![0, 1, 2, 3, 4]);
/// let height = 4;
/// let matrix = Matrix::<Fr>::vandermonde(&seed_points, height).unwrap();
///
/// let expected = vec_to_elements(vec![
/// 1, 1, 1, 1, 1,
/// 0, 1, 2, 3, 4,
/// 0, 1, 4, 9, 16,
/// 0, 1, 8, 27, 64,
/// ]);
/// // `matrix` content:
/// // 1, 1, 1, 1, 1,
/// // 0, 1, 2, 3, 4,
/// // 0, 1, 4, 9, 16,
/// // 0, 1, 8, 27, 64
///
/// assert_eq!(
/// Matrix::<T>::vandermonde(&seed_points, height).unwrap(),
/// Matrix { elements: expected, height, width: seed_points.len() }
/// );
/// # let expected = vec_to_elements(vec![
/// # 1, 1, 1, 1, 1,
/// # 0, 1, 2, 3, 4,
/// # 0, 1, 4, 9, 16,
/// # 0, 1, 8, 27, 64,
/// # ]);
/// # assert_eq!(matrix, Matrix { elements: expected, height: 4, width: 5 });
/// ```
///
/// # Errors
/// - if two seed points are equal: [`KomodoError::InvalidVandermonde`]
///
/// [article]: https://en.wikipedia.org/wiki/Vandermonde_matrix
pub fn vandermonde(points: &[T], height: usize) -> Result<Self, KomodoError> {
for i in 0..points.len() {
@@ -142,7 +148,26 @@ impl<T: Field> Matrix<T> {
}
}
/// build a completely random matrix of shape $n \times m$
/// Build a completely random matrix over a finite field, of _n_ rows and
/// _m_ columns.
///
/// # Example
/// ```rust
/// use komodo::algebra::linalg::Matrix;
/// use ark_bls12_381::Fr;
///
/// let mut rng = ark_std::test_rng();
/// let matrix = Matrix::<Fr>::random(3, 4, &mut rng);
///
/// // `matrix` content example (element values are random):
/// // 4, 1, 2, 0,
/// // 3, 5, 7, 11,
/// // 8, 10, 9, 6
///
/// # assert_eq!(matrix.height, 3);
/// # assert_eq!(matrix.width, 4);
/// # assert_eq!(matrix.elements.len(), 12);
/// ```
pub fn random<R: RngCore>(n: usize, m: usize, rng: &mut R) -> Self {
Self {
elements: (0..(n * m)).map(|_| T::from(rng.gen::<u128>())).collect(),
@@ -151,51 +176,53 @@ impl<T: Field> Matrix<T> {
}
}
/// build a matrix from a "_matrix_" of elements
/// Build a matrix over a finite field from a vector of vectors (a vector of
/// rows, a more natural way of representing matrices), checking that all
/// rows have the same length.
///
/// > **Note**
/// > if you are sure each row should have the same length and don't want to
/// > perform any runtime check to ensure that condition, have a look at
/// > [`Self::from_vec_vec_unchecked`].
/// > **Note**: if you are sure all rows have the same length and don't want
/// > check it at runtime, use [`Self::from_vec_vec_unchecked`].
///
/// # Example
/// ```rust
/// # use komodo::algebra::linalg::Matrix;
/// # use ark_ff::Field;
/// use komodo::algebra::linalg::Matrix;
/// use ark_bls12_381::Fr;
/// use ark_ff::Field;
/// // helper to convert integers to field elements
/// fn vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T>
/// # {
/// # elements.iter().map(|&x| T::from(x)).collect()
/// # }
/// // helper to convert integers to field elements, in a "matrix"
/// fn mat_to_elements<T: Field>(mat: Vec<Vec<u128>>) -> Vec<Vec<T>>
/// # {
/// # mat.iter().cloned().map(vec_to_elements).collect()
/// # }
/// # type T = ark_bls12_381::Fr;
/// fn vec_to_elements<T: Field>(vec: Vec<u128>) -> Vec<T> {
/// vec.iter().map(|&x| T::from(x)).collect()
/// }
/// // helper to convert integers to field elements, in a vector of vectors
/// fn mat_to_elements<T: Field>(mat: Vec<Vec<u128>>) -> Vec<Vec<T>> {
/// mat.iter().cloned().map(vec_to_elements).collect()
/// }
///
/// let elements = mat_to_elements(vec![
/// let vec_vec = mat_to_elements(vec![
/// vec![0, 1, 2, 3],
/// vec![4, 5, 6, 7],
/// vec![8, 9, 0, 1],
/// ]);
/// let matrix = Matrix::<Fr>::from_vec_vec(vec_vec).unwrap();
///
/// let height = elements.len();
/// let width = elements[0].len();
///
/// let expected = vec_to_elements(vec![
/// 0, 1, 2, 3,
/// 4, 5, 6, 7,
/// 8, 9, 0, 1,
/// ]);
/// // `matrix` content:
/// // 0, 1, 2, 3,
/// // 4, 5, 6, 7,
/// // 8, 9, 0, 1
///
/// assert_eq!(
/// Matrix::<T>::from_vec_vec(elements).unwrap(),
/// Matrix { elements: expected, height, width }
/// );
/// # let expected = vec_to_elements(vec![
/// # 0, 1, 2, 3,
/// # 4, 5, 6, 7,
/// # 8, 9, 0, 1,
/// # ]);
/// # assert_eq!(matrix, Matrix { elements: expected, height: 3, width: 4 });
/// ```
pub fn from_vec_vec(matrix: Vec<Vec<T>>) -> Result<Self, KomodoError> {
if matrix.is_empty() {
///
/// # Errors
/// - if the rows are not of the same length:
/// [`KomodoError::InvalidMatrixElements`]
///
pub fn from_vec_vec(vec_vec: Vec<Vec<T>>) -> Result<Self, KomodoError> {
if vec_vec.is_empty() {
return Ok(Self {
elements: vec![],
height: 0,
@@ -203,8 +230,8 @@ impl<T: Field> Matrix<T> {
});
}
let width = matrix[0].len();
for (i, row) in matrix.iter().enumerate() {
let width = vec_vec[0].len();
for (i, row) in vec_vec.iter().enumerate() {
if row.len() != width {
return Err(KomodoError::InvalidMatrixElements(format!(
"expected rows to be of same length {}, found {} at row {}",
@@ -215,19 +242,19 @@ impl<T: Field> Matrix<T> {
}
}
Ok(Self::from_vec_vec_unchecked(matrix))
Ok(Self::from_vec_vec_unchecked(vec_vec))
}
/// the unchecked version of [`Self::from_vec_vec`]
pub fn from_vec_vec_unchecked(matrix: Vec<Vec<T>>) -> Self {
let height = matrix.len();
let width = matrix[0].len();
pub fn from_vec_vec_unchecked(vec_vec: Vec<Vec<T>>) -> Self {
let height = vec_vec.len();
let width = vec_vec[0].len();
let mut elements = Vec::new();
elements.resize(height * width, T::zero());
for i in 0..height {
for j in 0..width {
elements[i * width + j] = matrix[i][j];
elements[i * width + j] = vec_vec[i][j];
}
}
@@ -276,12 +303,42 @@ impl<T: Field> Matrix<T> {
}
}
/// compute the inverse of the matrix
/// Compute the inverse of the matrix.
///
/// > **Note**: the matrix should be square and invertible.
///
/// # Example
/// ```rust
/// # use komodo::algebra::linalg::Matrix;
/// # use ark_bls12_381::Fr;
/// # use ark_ff::Field;
/// # // helper to convert integers to field elements
/// # fn vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T> {
/// # elements.iter().map(|&x| T::from(x)).collect()
/// # }
/// #
/// // see Self::vandermonde() for the definition of vec_to_elements()
/// let seed_points = vec_to_elements(vec![0, 1, 2, 3, 4]);
/// let height = seed_points.len(); // square Vandermonde matrix
/// let matrix = Matrix::<Fr>::vandermonde(&seed_points, height).unwrap();
///
/// let inverse = matrix.invert().unwrap();
/// #
/// # let identity = vec_to_elements(vec![
/// # 1, 0, 0, 0, 0,
/// # 0, 1, 0, 0, 0,
/// # 0, 0, 1, 0, 0,
/// # 0, 0, 0, 1, 0,
/// # 0, 0, 0, 0, 1]);
/// # assert_eq!(
/// # matrix.mul(&inverse).unwrap(),
/// # Matrix { elements: identity, height: height, width: height });
/// ```
///
/// # Errors
/// - if the matrix is not square: [`KomodoError::NonSquareMatrix`]
/// - if the matrix is not invertible: [`KomodoError::NonInvertibleMatrix`]
///
/// > **None**
/// > the matrix should be
/// > - square
/// > - invertible
pub fn invert(&self) -> Result<Self, KomodoError> {
if self.height != self.width {
return Err(KomodoError::NonSquareMatrix(self.height, self.width));
@@ -322,16 +379,36 @@ impl<T: Field> Matrix<T> {
}
}
/// compute the rank of the matrix
/// Compute the rank of the matrix.
///
/// > **None**
/// > see the [_Wikipedia article_](https://en.wikipedia.org/wiki/Rank_(linear_algebra))
/// > for more information
/// >
/// > **Note:**
/// > - the rank is always smaller than the min between the height and the
/// > width of any matrix.
/// > - a square and invertible matrix will have _full rank_, i.e. it will
/// > be equal to its size.
/// >
/// > See the [_Wikipedia article_](https://en.wikipedia.org/wiki/Rank_(linear_algebra))
/// > for more information.
///
/// # Example
///
/// ```rust
/// # use komodo::algebra::linalg::Matrix;
/// # use ark_bls12_381::Fr;
/// # use ark_ff::Field;
/// # // helper to convert integers to field elements
/// # fn vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T> {
/// # elements.iter().map(|&x| T::from(x)).collect()
/// # }
/// #
/// // see Self::vandermonde() for the definition of vec_to_elements()
/// let seed_points = vec_to_elements(vec![0, 1, 2, 3, 4]);
/// let height = seed_points.len();
/// let mat = Matrix::<Fr>::vandermonde(&seed_points, height).unwrap();
///
/// let r = mat.rank();
/// # assert_eq!(r, height);
/// ```
pub fn rank(&self) -> usize {
let mut mat = self.clone();
let mut i = 0;
@@ -371,14 +448,57 @@ impl<T: Field> Matrix<T> {
nb_non_zero_rows
}
/// compute the matrix multiplication with another matrix
/// Compute the matrix multiplication with another matrix.
///
/// if `mat` represents a matrix $A$ and `rhs` is the representation of
/// another matrix $B$, then `mat.mul(rhs)` will compute $A \times B$
/// If `mat` represents a matrix $A$ and `rhs` is the representation of
/// another matrix $B$, then `mat.mul(rhs)` will compute $A \times B$.
///
/// > **Note**
/// > both matrices should have compatible shapes, i.e. if `self` has shape
/// > `(n, m)` and `rhs` has shape `(p, q)`, then `m == p`.
/// > **Note**: both matrices should have compatible shapes, i.e. if `self`
/// > has shape `(n, m)` and `rhs` has shape `(p, q)`, then `m == p`.
///
/// # Example
///
/// ```rust
/// use komodo::algebra::linalg::Matrix;
/// use ark_bls12_381::Fr;
/// # use ark_ff::Field;
/// # // helper to convert integers to field elements
/// # fn vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T> {
/// # elements.iter().map(|&x| T::from(x)).collect()
/// # }
/// # // helper to convert integers to field elements, in a "matrix"
/// # fn mat_to_elements<T: Field>(mat: Vec<Vec<u128>>) -> Vec<Vec<T>> {
/// # mat.iter().cloned().map(vec_to_elements).collect()
/// # }
///
/// // see Self::from_vec_vec() for the definition of mat_to_elements()
/// let a = mat_to_elements(vec![
/// vec![0, 1, 2],
/// vec![3, 4, 5],
/// ]);
/// let b = mat_to_elements(vec![
/// vec![0, 1],
/// vec![2, 3],
/// vec![4, 5],
/// ]);
///
/// let matrix = Matrix::<Fr>::from_vec_vec(a).unwrap();
/// let rhs = Matrix::<Fr>::from_vec_vec(b).unwrap();
/// let product = matrix.mul(&rhs).unwrap();
///
/// // `product` content:
/// // 10, 13,
/// // 28, 40
/// #
/// # let c = mat_to_elements(vec![
/// # vec![10, 13],
/// # vec![28, 40],
/// # ]);
/// # assert_eq!(product, Matrix::<Fr>::from_vec_vec(c).unwrap());
/// ```
///
/// # Errors
/// - if the matrices have incompatible shapes: [`KomodoError::IncompatibleMatrixShapes`]
pub fn mul(&self, rhs: &Self) -> Result<Self, KomodoError> {
if self.width != rhs.height {
return Err(KomodoError::IncompatibleMatrixShapes(
@@ -409,10 +529,47 @@ impl<T: Field> Matrix<T> {
})
}
/// compute the transpose of the matrix
/// Compute the transpose of the matrix.
///
/// > **Note**
/// > see the [_Wikipedia article_](https://en.wikipedia.org/wiki/Transpose)
/// > see the [_Wikipedia article_](https://en.wikipedia.org/wiki/Transpose) for more information.
///
/// # Example
///
/// ```rust
/// use komodo::algebra::linalg::Matrix;
/// use ark_bls12_381::Fr;
/// # use ark_ff::Field;
/// # // helper to convert integers to field elements
/// # fn vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T> {
/// # elements.iter().map(|&x| T::from(x)).collect()
/// # }
/// # // helper to convert integers to field elements, in a "matrix"
/// # fn mat_to_elements<T: Field>(mat: Vec<Vec<u128>>) -> Vec<Vec<T>> {
/// # mat.iter().cloned().map(vec_to_elements).collect()
/// # }
///
/// // see Self::from_vec_vec() for the definition of mat_to_elements()
/// let a = mat_to_elements(vec![
/// vec![0, 1, 2],
/// vec![3, 4, 5],
/// ]);
///
/// let matrix = Matrix::<Fr>::from_vec_vec(a).unwrap();
/// let transposed = matrix.transpose();
///
/// // `transposed` content:
/// // 0, 3,
/// // 1, 4,
/// // 2, 5
/// #
/// # let b = mat_to_elements(vec![
/// # vec![0, 3],
/// # vec![1, 4],
/// # vec![2, 5],
/// # ]);
/// # assert_eq!(transposed, Matrix::<Fr>::from_vec_vec(b).unwrap());
/// ```
pub fn transpose(&self) -> Self {
let height = self.width;
let width = self.height;