dimforge / nalgebra

Linear algebra library for Rust.
https://nalgebra.org
Apache License 2.0
3.95k stars 471 forks source link

Mutating update for decompositions (QR, LU, ...) #1070

Open pnevyk opened 2 years ago

pnevyk commented 2 years ago

To be able to reuse matrix allocations, it would be nice to have a possibility to calculate matrix decompositions while reusing their already allocated storage. Each decomposition type would have a new method fn update(&mut self, matrix: &Matrix<...>) (*) that updates self by calculating the decomposition for matrix.

If this idea is approved, I am fine with making a PR.

*I am not sure about the name "update". It may be confused with rank-1 update that is implemented for Cholesky (and that can be implemented for some other decompositions as well). Proposals for alternatives are welcome.

stfnp commented 1 year ago

I stumbled upon this when trying to port some C++ code using Eigen, because this is possible there. Maybe their API can serve as an example.

Their decompositions typically have three constructors, here for LLT (Cholesky):

LLT(const EigenBase<InputType>& a)
LLT(Index size)
LLT()

The first constructor is similar to what nalgebra has: The decomposition is initialized and computed from a matrix. In addition to that there is a constructor that preallocates for a known problem size but doesn't yet do any computation and also a default constructor that doesn't allocate anything yet.

And then there is a method called compute that updates the decomposition for a new matrix and reuses the storage if the problem size matches:

compute(const EigenBase<InputType>& a)

As a user, I think something like this would be a nice addition to nalgebra. It is very useful when implementing some iterative algorithm that does a matrix decomposition in each iteration. Reusing the decomposition can save many allocations in such cases.