A Rust linear algebra library based on expression templates
Hi,
I have just uploaded a very early version of \householder\, a Rust linear algebra library based on expression templates similar to C++ eigen and I am very interested in opinions.
1.) What are expression templatex? These are data structures that represent operations such as addition or multiplication. They have lazy evaluation, so execution only happens on demand.
2.) Why is this important?
Imagine the operation c = 5.0 \* a + 7.0 \* b, where a, b, and c are matrices. Without expression templates we would evaluate 5.0 \* a and 7.0 \* b into a temporary matrices and then add those temporaries together. This requires several passes through the matrices and the allocation of temporary storage.
With expression templates one represent this operation symbolically as
Add(Prod(5.0, a), Prod(7.0, b))
where Add and Prod are data structures that just store the required terms and only perform an evaluation when needed. At the end with compiler optimisations everything compiles down to a single pass through the matrices in which componentwise we perform the operations.
3.) Where does this come from? The C++ Eigen library is a very popular linear algebra library based on expression templates. With householder we are aiming to create something similar for Rust. A further inspiration came from the Rust xpr package, which is a demonstration package on how one could do expression templates in Rust. At the end our implementation is a bit different. But xpr got us on the right track on how to do it.
Further goals of Householder are:
\- Rust native multithreaded matrix decompositions. The guidance here is what libraries such as BLIS and PLASMA are doing in the C/C++ world. Also, Eigen provides native routines. Not relying on BLAS/Lapack makes portability and deployment a lot easier.
\- Support for sparse matrices on single nodes and clusters. One of our application domains is distributed HPC, and adding parallel sparse-matrix data structures is high on our list.
\- Well tested randomized linear algebra. We often require randomized linear algebra routines (e.g. randomized SVD, etc.), which are highly efficient for matrices that are large but have low information content (i.e. singular values decay quickly). We aim to integrate modern randomized decompositions into householder.
Is Househoulder already usable?
Not really. All the basic data structures for matrices based on expression templates are implemented. We support addition of matrices, scalar multiplication, matrix/matrix and matrix vector products. The latter are done through the matrixmultiply package. Focus was for the first upload of the library to get the basic data structures right. We are now starting to move some of our other codes to use householder as linear algebra backend and will add functionality as required.
I'd be very interested in comments, technical discussions, ideas for linear algebra packages, etc. Our goal is not to create competition to ndarray and nalgebra. Both are excellent packages that serve different domains. For us efficient expression template like structures, multithreaded native sparse matrix decompositions, randomized linear algebra, and sparse matrices are important. These are quite orthogonal to what those packages are doing.