This GH2003 paper by Goodnight et al. at the University of Virginia is a demonstrates an implementation on of the multigrid method for solving boundary value problems, such as the systems of partial differential equations that arise in physical simulation problems like fluid flow, heat transfer, and tone mapping. This paper is an expanded, more detailed version of the authors’ earlier tech report. (A Multigrid Solver for Boundary Value Problems Using Programmable Graphics Hardware. Nolan Goodnight, Cliff Woolley, Gregory Lewin, David Luebke, and Greg Humphreys. To appear in the proceedings of Graphics Hardware 2003.)

This paper describes a framework for the implementation of linear algebra operators on GPUs, providing the building blocks for the design of more complex numerical algorithms. The framework takes advantage of sparse and banded matrices in particular. The paper demonstrates the approach by implementing direct solvers for sparse matrices with application to multi-dimensional finite difference equations, i.e. the 2D wave equation and the incompressible Navier-Stokes equations. (Linear Algebra Operators for GPU Implementation of Numerical Algorithms. Jens Krüger and Rüdiger Westermann. To appear in the proceedings of SIGGRAPH 2003.)

This paper from the upcoming book ShaderX 2 Programming by Ádám Moravánszky gives a detailed description of implementing dense matrix operations on programmable GPUs. Matrix multiplication is applied to solving linear systems of equations and the linear complementarity problem, which can in turn be used to simulate soft body and rigid body physics. The performance of the GPU implementation is compared to the SSE2 optimized ATLAS library running on the CPU. DirectX 9 pixel and vertex shader programs are provided. (Dense Matrix Algebra on the GPU. Ádám Moravánszky. To appear in ShaderX 2 Programming, Wordware, 2003.)

This paper by Govindaraju et al. describes an approach for collision detection between multiple deformable and breakable objects in a large environment using graphics hardware. The algorithm uses a two-pass rendering scheme to compute a potentially colliding set (PCS) in linear time using visibility queries with no precomputation or frame buffer read back. ( CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments Using Graphics Hardware. Naga Govindaraju, Stephane Redon, Ming C. Lin and Dinesh Manocha. To appear in Proceedings of Graphics Hardware 2003)

This paper by Harris et al. at UNC Chapel Hill describes a physically-based, visually-realistic interactive cloud simulation implemented on programmable GPUs. The simulation uses “flat 3D textures” – 3D data laid out as slices tiled in a 2D texture – to implement efficient 3D simulations on the GPU. The work required to simulate a single time step is automatically spread over many frames while the user views the results of the previous time step at high frame rates. (Simulation of Cloud Dynamics on Graphics Hardware. Mark J. Harris, William V. Baxter III, Thorsten Scheuermann and Anselmo Lastra. To appear in Proceedings of Graphics Hardware 2003.)

This paper by Theodore Kim and Ming Lin describes a physically-based technique for simulating ice crystal growth. The most expensive part of the simulation pipeline, the phase and temperature field calculations, can be mapped to graphics hardware. The resulting implementation experiences up to a 9x speedup. (Visual Simulation of Ice Crystal Growth. Theodore Kim and Ming Lin. To appear in the proceedings of ACM SIGGRAPH / Eurographics Symposium on Computer Animation 2003.)

This paper by Bolz et al. of Cal Tech shows two basic, broadly useful, computational kernels implemented on GPUs: a sparse matrix conjugate gradient solver, and a regular-grid multigrid solver. The paper demonstrates a prototype implementation on NVIDIA’s GeForce FX, using geometric flow (cube smoothing movie, 3D photography scan denoising movie) and fluid simulation (particle advection movie) as application examples. (Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid. Jeff Bolz, Ian Farmer, Eitan Grinspun and Peter Schröder. To appear in the proceedings of SIGGRAPH 2003.)

This demo by Simon Green of NVIDIA demonstrates Verlet cloth simulation implemented on the GPU using fragment programs and floating point buffers. It uses the GL_NV_pixel_data_range OpenGL extension to implement “render to vertex array” in order to render the cloth as a mesh. (Cloth Simulation Demo)

This tutorial was presented at the 2003 Game Developers Conference by Greg James (NVIDIA) and Mark Harris (UNC). Topics included real-time fluid dynamics, reaction-diffusion, and cellular automata running on GPUs. On the web page you will find talk slides, demos, source code, and links relating to simulation and animation on the GPU.

This paper by Goodnight et al. at the University of Virginia demonstrates an implementation on two modern graphics architectures of the multigrid method for solving boundary value problems, such as the systems of partial differential equations that arise in physical simulation problems like fluid flow and heat transfer. (A Multigrid Solver for Boundary Value Problems Using Graphics Hardware. Nolan Goodnight, Gregory Lewin, David Luebke, and Kevin Skadron, University of Virginia Technical Report CS-2003-03 (January 2003).)