Efficient GPU Data Structures and Methods to Solve Sparse Linear Systems in Dynamics Applications

Simple item page
dc.contributor.authorWeber, Danielen_US
dc.contributor.authorBender, Janen_US
dc.contributor.authorSchnoes, Markusen_US
dc.contributor.authorStork, Andreen_US
dc.contributor.authorFellner, Dieter W.en_US
dc.contributor.editorHolly Rushmeier and Oliver Deussenen_US
dc.date.accessioned2015-02-28T15:16:44Z
dc.date.available2015-02-28T15:16:44Z
dc.date.issued2013en_US
dc.description.abstractWe present graphics processing unit (GPU) data structures and algorithms to efficiently solve sparse linear systems that are typically required in simulations of multi-body systems and deformable bodies. Thereby, we introduce an efficient sparse matrix data structure that can handle arbitrary sparsity patterns and outperforms current state-of-the-art implementations for sparse matrix vector multiplication. Moreover, an efficient method to construct global matrices on the GPU is presented where hundreds of thousands of individual element contributions are assembled in a few milliseconds. A finite-element-based method for the simulation of deformable solids as well as an impulse-based method for rigid bodies are introduced in order to demonstrate the advantages of the novel data structures and algorithms. These applications share the characteristic that a major computational effort consists of building and solving systems of linear equations in every time step. Our solving method results in a speed-up factor of up to 13 in comparison to other GPU methods.We present GPU data structures and algorithms to efficiently solve sparse linear systems which are typically required in simulations of multibody systems and deformable bodies. Thereby, we introduce an efficient sparse matrix data structure that can handle arbitrary sparsity patterns and outperforms current state-of-the-art implementations for sparse matrix vector multiplication. Moreover, an efficient method to construct global matrices on the GPU is presented where hundreds of thousands of individual element contributions are assembled in a few milliseconds. A finite element based method for the simulation of deformable solids as well as an impulse-based method for rigid bodies are introduced in order to demonstrate the advantages of the novel data structures and algorithms. These applications share the characteristic that a major computational effort consists of building and solving systems of linear equations in every time step. Our solving method results in a speed-up factor of up to 13 in comparison to other GPU methods.en_US
dc.description.number1
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume32
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2012.03227.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.subjectComputer Graphics [I.3.1]en_US
dc.subjectHardware Architectureen_US
dc.subjectGraphics processorsen_US
dc.subjectComputer Graphics [I.3.7]en_US
dc.subjectThree Dimensional Graphics and Realismen_US
dc.subjectAnimationen_US
dc.subjectinteractive simulationen_US
dc.subjectGPU computingen_US
dc.subjectphysically based modelingen_US
dc.subjectlinear systemsen_US
dc.titleEfficient GPU Data Structures and Methods to Solve Sparse Linear Systems in Dynamics Applicationsen_US
Files
Collections
32-Issue 1