Linear Algebra libraries for Rust

I tried to implement LWE with Rust. Here is the memo about linear algebra libraries.

Which library to use

As of Nov.2021, there was no “defacto standard” linear algebra library in Rust. I investigated, and decided to use ndarray or nlagebra.

ndarray vs nalgebra - Reddit

ndarray

https://github.com/rust-ndarray/ndarray

tensorflow/Rust uses ndarray.

• ndarray is mentioned in Rust cookbook:
• ndarray use BLAS impelementation on the runtime (Intel MKL, OpenBLAS, etc.), so it could be faster than other libraries.
• ndarray can handle arbitrary dimension array.

nalgebra

• Fully written in Rust, but some functions use lapack crate, which is a wrapper crate for LAPACK.
• nalgebra is specialized for 1D, and 2D array.

I tried to use Static vector nalgebra::base::SVector (optimized).

check test and know the traits.

• I couldn’t find about combining SVectors into a matrix (no trait like that?, dynamic?)
  • I should test ::from_vec!. from_vec! doesn’t combine vectores:

    let dm = DMatrix::from_vec(2, 3, vec![0, 1, 2, 3, 4, 5]);
    

  • Matrix data is stored in 1D vector by nalgebra Matrix definition, so I guess they don’t provide such API so far.
  • https://github.com/dimforge/nalgebra/blob/dev/tests/core/matrix.rs

Data structure

https://docs.rs/nalgebra/latest/nalgebra/base/struct.Matrix.html

Matrix data is stored in 1D vector (data.data attribute), and the size are stored in data.nrows and data.ncols, respectively. The matrix data is called VecStorage.

https://docs.rs/nalgebra/latest/src/nalgebra/base/vec_storage.rs.html#33-37

pub struct VecStorage<T, R: Dim, C: Dim> {
    data: Vec<T>,
    nrows: R,
    ncols: C,
}

When I followed allocator.rs -> default_allocator.rs, I could see use std::ptr; and use alloc::vec::Vec;

OK, the core Vec is normal standard library.

Review: When you create a matrix, from memory point of view, all data is stored in Vec (1D) and the size is defined col times row, which means, the library is specialized for matrix (2D).

Finally I decided to implement only standard Vec lib.

Vector operations

Initialize with initial values

https://www.joshmcguigan.com/blog/array-initialization-rust/

Vector of Vector (DON’T DO THIS WAY!)

let mut A = Vec::<Vec::<Z>>::new();
A.push(vec!(4, 9, 6));
A.push(vec!(4, 9, 9));

This 2D array is fragmented, because memory allocation of each vectors occured every time.

// Check
assert_eq!(A[4], vec!(5, 10, 4));
assert_eq!(A[6][2], 4);
assert_eq!(e[5], 9);

Dot product (poor, functional implementation) for Vec

The type of A is Vec<Vec<Z>>, and the type of s is Vec<T>:

for a_i in A.iter() {
    b.push(
        a_i.iter().zip(s.iter())
                  .map(|(x, y)| x * y)
                  .sum::<Z>()
    );
}

Implement vector addition + (failed)

I tried to implement std::ops::Add tarit for Vec.

https://doc.rust-lang.org/std/ops/index.html

Failed:

error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
  --> src/main.rs:69:1
   |
69 | impl<T> Add for Vec<T>
   | ^^^^^^^^---^^^^^------
   | |       |       |
   | |       |       `Vec` is not defined in the current crate
   | |       `Vec` is not defined in the current crate
   | impl doesn't use only types from inside the current crate
   |
   = note: define and implement a trait or new type instead

Casting usize

as T keyword.

Type casting in fluent APIs

https://doc.rust-lang.org/book/appendix-02-operators.html

path::<...>, method::<...>: Specifies parameters to generic type, function, or method in an expression; often referred to as turbofish (e.g., "42".parse::<i32>()).