Block principal pivoting with incremental Cholesky factorizations for real-time multibody simulations

Résumé

Les engins de simulation physiques sont au coeur d’un large éventail d’applications et doivent faire face à différents défis en fonction du contexte dans lequel ils sont utilisés. La formation en réalité virtuelle (RV) pour la conduite d’équipement lourd présente souvent des scénarios impliquants des interactions entre des objets ayant des rapports de masse importants et des contraintes rigides, comme une charge lourde soulevée par un fil d’acier. Pour avoir de la valeur en tant qu’outil de formation, ces simulateurs doivent effectuer des calculs très précis tout en gérant les interactions utilisateur et ce sous une contrainte de performance très stricte. Bien que rapides, les solveurs linéaires itératifs fonctionnent souvent mal dans de tels cas, conduisant à des simulations imprécises ou instables. Les solveurs utilisant des méthodes qui impliquent une factorisation de la matrice système sont préférées. Cependant, la factorisation a un coût de calcul important qui peut réduire les performances. Dans ce travail, nous présentons un solveur de système linéaire efficace pour un système avec des contraintes physiques rigides et des contacts avec friction, modélisé comme un problème de complémentarité linéaire mixte (MLCP). Notre méthode est basée sur un algorithme de pivot de Guass par block et réutilise les factorisations précédentes en appliquant des mises à jour de rang un à chaque étape de pivotement. Les performances sont davantage améliorées en exploitant l’étroitesse de la bande de la matrice principale. Nous analysons le gain de performance dans divers scénarios difficiles, certains allant jusqu’à 3,5 fois plus vite par rapport au recalcul de la factorisation à partir de zéro. Nous explorons aussi la possibilité d’accélérer notre méthode en mettant en cache les factorisations intermédiaires.

Date	17 déc. 2020
langue originale	Anglais américain
Établissement diplômant	École de technologie supérieure
Superviseur	Sheldon Andrews (Directeur(-trice))