Efficient block pivoting for multibody simulations with contact

Résumé

Simulating stiff physical systems is a requirement for numerous computer graphics applications, such as VR training for heavy equipment operation. However, iterative linear solvers often perform poorly in such cases, and direct methods involving a factorization of the system matrix are typically preferred for accurate and stable simulations. This can have a detrimental impact on performance, since factorization of the system matrix is costly for complex simulations. In this paper, we present a method for efficiently solving linear systems of stiff physical systems involving contact, where the dynamics are modeled as a mixed linear complementarity problem (MLCP). Our approach is based on a block Bard-type algorithm that applies low-rank downdates to a Cholesky factorization of the system matrix at each pivoting step. Further performance improvements are realized by exploiting low bandwidth characteristics of the factorization. Our method gives up to 3.5 times speed-up versus recomputing the factorization based on the index set. Various challenging scenarios are used to demonstrate the advantages of our approach.

    @inproceedings{bppdowndating2019,
        author = {Enzenhöfer, Andreas and Lefebvre, Nicolas and Andrews, Sheldon},
        title = {Efficient block pivoting for multibody simulations with contact},
        booktitle = {Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games},
        series = {I3D’19},
        year = {2019},
        pages = {},
        publisher = {ACM}
    }