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

Lefebvre, Nicolas (2020). Block principal pivoting with incremental Cholesky factorizations for real-time multibody simulations. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (1MB) | Prévisualisation
Prévisualisation	PDF Télécharger (1MB) | Prévisualisation

Résumé

Physics engines are at the heart of a wide array of applications and must deal with different challenges depending on the context in which they are used. Virtual reality (VR) training for heavy equipment operation often simulates scenarios involving interactions between elements with large mass ratios and stiff constraints, like a heavy weight lifted by a steel wire. To have any value as a training tool, simulators must must perform accurate simulations while handling arbitrary user input under very strict performance constraints. Iterative linear solvers, while being fast to compute approximate solutions, often perform poorly in such cases leading to inaccurate or unstable simulations, and so direct methods involving a factorization of the system matrix are preferred. However, the factorization has a significant computational cost that can reduce performance. In this work, we present an efficient linear solver for systems with stiff physical constraints and contacts, where the dynamics are modeled as a mixed linear complementarity problem (MLCP). Our method is based on a block principal pivoting (BPP) algorithm, and at each step previous factorizations are reused by applying low-rank downdates at each pivoting step. We obtain further performance improvements by exploiting the low bandwidth characteristics of the lead matrix. We analyze the performance gain in various challenging scenarios, some of which gained up to a 3.5× speed-up when compared to recomputing the factorization from scratch. We further explore the possibility of accelerating our method by caching intermediary factorizations.

Titre traduit

Pivot de Gauss par blocs avec factorisation de Cholesky incrémentales pour les simulations physiques en temps-réel

Résumé traduit

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.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Thesis presented to École de technologie supérieure in partial fulfillment of a master’s degree with thesis in software engineering". Comprend des références bibliographiques (pages 49-51).
Mots-clés libres:	simulation physique en temps-réel, pivot de Gauss par blocs, complémentarité linéaire, dynamique, Cholesky, cache
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Andrews, Sheldon
Programme:	Maîtrise en ingénierie > Génie
Date de dépôt:	22 sept. 2021 17:14
Dernière modification:	24 sept. 2021 18:28
URI:	https://espace.etsmtl.ca/id/eprint/2697

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt