Re: [eigen] Dense Matrix Decompositions/Solvers: Inherit from SolverBase

[Patrick Peltzer <peltzer@xxxxxxxxxxxxxxxxxxx>]

Hi Gael,

thank you for your answer.

On 08.03.2018 18:03, Gael Guennebaud wrote:

This looks very interesting. Out of curiosity, have you considered leveraging matrix differential rules, such as identifying expressions like x = A.lu().solve(b) and instead of going through the whole factorization to cary out the derivatives, simply use the rules for differentiating the inverse of a matrix...??

This is exactly what the symbolic solvers are doing. Some words on how the direct linear solvers (LU, QR, ...) can be differentiated: 
The ordinary adjoint algorithmic differentiation approach would be to save all necessary data in the forward run ( termed "taping") on an external data structure (the "tape") so it can be accessed in the reverse run when the adjoints are propagated. The forward run includes the taping of the whole decomposition process, occupying memory in the order of O(n^3) and accordingly requires the reverse passing of the computation, causing an additional computational cost in the order of O(n^3).
By exploiting the mathematical insight, it is possible to propagate the adjoints in the reverse run without going through the decomposition computation, given the finished decomposition was saved in the forward run before. This reduces the computational complexity to O(n^2) in the reverse section and the memory cost to O(n^2) as well.

I've implemented such symbolic variants for the FullPivLU, PartialPivLU and HouseholderQR solvers so far. I'm currently collecting data and things appear to look very promising (especially the additional memory cost has been greatly reduced). Right now, the symbolic solvers need to be explicitly instantiated, but I will try to find a nice way to specialize the existing solvers for the dco/c++ data types in order to automatically grant support for the hardcoded solver calls inside the Eigen internals. Besides including the other dense solvers, other symbolic variants of linear algebra operations are on my agenda for the future.

Yes, that's mostly a lack of time, and having all of them inherit SolverBase is of course highly desirable.

 

...

extending the respective unit tests to cover transpose/adjoint solving is all what's missing to accept a pull-request.

gael

 

Alright, great to know! You can also expect the other solvers to follow in the future as well.

Best regards,
Patrick