Graph Partitioning Algorithms for Rigid Body Simulations
Loading...
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
We propose several graph partitioning algorithms for improving the performance of rigid body simulations. The algorithms operate on the graph formed by rigid bodies (nodes) and constraints (edges), producing non-overlapping and contiguous sub-systems that can be simulated in parallel by a domain decomposition technique. We demonstrate that certain partitioning algorithms reduce the computational time of the solver, and graph refinement techniques that reduce coupling between sub-systems, such as the Kernighan-Lin and Fiduccia-Mattheyses algorithms, give additional performance improvements.
Description
CCS Concepts: Computing methodologies --> Physical simulation; Mathematics of computing --> Graph algorithms
@inproceedings{10.2312:egs.20221036,
booktitle = {Eurographics 2022 - Short Papers},
editor = {Pelechano, Nuria and Vanderhaeghe, David},
title = {{Graph Partitioning Algorithms for Rigid Body Simulations}},
author = {Liu, Yinchu and Andrews, Sheldon},
year = {2022},
publisher = {The Eurographics Association},
ISSN = {1017-4656},
ISBN = {978-3-03868-169-4},
DOI = {10.2312/egs.20221036}
}