{"id":{"repo_id":"ets-quebec","oai_identifier":"oai:espace.etsmtl.ca:2697"},"canonical_url":"https://search.ndltd.org/etd/ets-quebec/oai:espace.etsmtl.ca:2697","repository":{"repo_id":"ets-quebec","name":"ETS (Quebec)","base_url":"https://espace.etsmtl.ca/cgi/oai2"},"display":{"title":"Block principal pivoting with incremental Cholesky factorizations for real-time multibody simulations","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Lefebvre, Nicolas"],"institution":"École de technologie supérieure","degree_name":"Mémoire de maîtrise électronique","degree_level":"masters","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-12-17","date_published":"2020-12-17","updated_at":"2026-11-18T22:08:52Z","subjects":["simulation physique en temps-réel, pivot de Gauss par blocs, complémentarité linéaire, dynamique, Cholesky, cache"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["INSERT-YOUR-LIBRARY-ID-HERE2697"],"render_values":[{"text":"INSERT-YOUR-LIBRARY-ID-HERE2697","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"https://espace.etsmtl.ca/id/eprint/2697/1/LEFEBVRE_Nicolas.pdf","download_label":"Download PDF","download_source":"dc:identifier","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://espace.etsmtl.ca/cgi/oai2?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Aespace.etsmtl.ca%3A2697","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lefebvre, Nicolas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-12-17"]},{"key":"dc:publisher","label":"Institution","values":["École de technologie supérieure"]},{"key":"dc:type","label":"Dc Type","values":["Electronic Thesis or Dissertation"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Mémoire de maîtrise électronique"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["École de technologie supérieure"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["simulation physique en temps-réel, pivot de Gauss par blocs, complémentarité linéaire, dynamique, Cholesky, cache"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["INSERT-YOUR-LIBRARY-ID-HERE2697","https://espace.etsmtl.ca/id/eprint/2697/1/LEFEBVRE_Nicolas.pdf","https://espace.etsmtl.ca/id/eprint/2697/7/LEFEBVRE_Nicolas-web.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Block principal pivoting with incremental Cholesky factorizations for real-time multibody simulations"]}]}],"canonical_facts":{"dc:creator":["Lefebvre, Nicolas"],"dc:date":["2020-12-17"],"dc:description":["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."],"dc:format":["application/pdf"],"dc:identifier":["INSERT-YOUR-LIBRARY-ID-HERE2697","https://espace.etsmtl.ca/id/eprint/2697/1/LEFEBVRE_Nicolas.pdf","https://espace.etsmtl.ca/id/eprint/2697/7/LEFEBVRE_Nicolas-web.pdf"],"dc:language":["en"],"dc:publisher":["École de technologie supérieure"],"dc:subject":["simulation physique en temps-réel, pivot de Gauss par blocs, complémentarité linéaire, dynamique, Cholesky, cache"],"dc:title":["Block principal pivoting with incremental Cholesky factorizations for real-time multibody simulations"],"dc:type":["Electronic Thesis or Dissertation"],"thesis:degree_level":["masters"],"thesis:degree_name":["Mémoire de maîtrise électronique"],"thesis:institution_name":["École de technologie supérieure"]},"updated_at":"2026-11-18T22:08:52Z"}