Liu, YinchuAndrews, SheldonPelechano, NuriaVanderhaeghe, David2022-04-222022-04-222022978-3-03868-169-41017-4656https://doi.org/10.2312/egs.20221036https://diglib.eg.org:443/handle/10.2312/egs20221036We 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.Attribution 4.0 International LicenseCCS Concepts: Computing methodologies --> Physical simulation; Mathematics of computing --> Graph algorithmsComputing methodologiesPhysical simulationMathematics of computingGraph algorithms10.2312/egs.2022103673-764 pages