Solver Performance

[nithinp7]

While the solver implementation itself is not the current performance bottleneck, we expect it should be the bottleneck once collision detection performance is improved as mentioned in #11 . To this end, we have been interested in several lofty ideas for speeding up the solver implementation itself.

One of the proposed motivations for the projective dynamics framework was the Cholesky pre-factorization of the system matrix - this theoretically should yield an incredibly efficient global optimization step, since the system is already solved up-to a small back-substitution step. In practice however, the system matrix factorization has to be regularly updated according to the ever-changing system connectivity due to collisions and fractures.

One option is to use sparse-Cholesky rank-updates that carefully update the original factorization based on system rank-updates. To my knowledge, CHOLMOD by Dr. Timothy Davis is the only out-of-box tool that is capable of this. From a limited amount of digging so far, it seemed incredibly painful to set up, possibly requiring a Fortran compiler and very specific environment dependencies. This CMake-based CHOLMOD wrapper library seems promising to reduce some of the pain, but more investigation is needed to determine the viability of integrating it into Pies: https://github.com/sergiud/SuiteSparse.

Another option is to use the original Cholesky factorization of the system matrix as a precondition step for alternative, iterative techniques. Conjugate gradient descent, Chebyshev iterations, and alternating-direction method of multipliers have all been implemented with projective dynamics in the literature. Without knowing all the details, I suspect there is an elegant hybrid method to be discovered that combines:

• preconditioning via precomputed Cholesky factorizations,
• asynchronous precondition matrix factorization updates based on changing system connectivity,
• and uses iterative methods to compute the actual solution to the system, preconditioned with the most up-to-date factorization available.