“Sparse matrix solvers on the GPU: conjugate gradients and multigrid” by Bolz, Farmer, Grinspun and Schröder

Many computer graphics applications require high-intensity numerical simulation. We show that such computations can be performed efficiently on the GPU, which we regard as a full function streaming processor with high floating-point performance. We implemented two basic, broadly useful, computational kernels: a sparse matrix conjugate gradient solver and a regular-grid multigrid solver. Real time applications ranging from mesh smoothing and parameterization to fluid solvers and solid mechanics can greatly benefit from these, evidence our example applications of geometric flow and fluid simulation running on NVIDIA’s GeForce FX.

1. ARVIND, AND IANNUCCI, R. A. 1987. Two Fundamental Issues in Multiprocessing. In Proceedings of DFVLR-Conference 1987, Parallel Processing in Science and Engineering.]] Google ScholarDigital Library
2. BARRETT, R., BERRY, M., CHAN, T. F., DEMMEL, J., DONATO, J., DONGARRA, J., EIJKHOUT, V., POZO, R., ROMINE, C., ANDDER VORST, H. V. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. SIAM.]]Google Scholar
3. BLELLOCH, G. E. 1990. Vector Models for Data-Parallel Computing. MIT Press.]] Google Scholar
4. BRIGGS, W. L., HENSON, V. E., AND MCCORMACK, S. F. 2000. A Multigrid Tutorial, 2nd ed. SIAM.]] Google Scholar
5. CARR, N. A., HALL, J. D., AND HART, J. C. 2002. The Ray Engine. In SIGGRAPH/Eurographics Workshop on Graphics Hardware.]] Google Scholar
6. COHEN, M. F., CHEN, S. E., WALLACE, J. R., AND GREENBERG, D. P. 1988. A Progressive Refinement Approach to Fast Radiosity Image Generation. Computer Graphics (Proceedings of SIGGRAPH) 22, 75–84.]] Google ScholarDigital Library
7. DEMMEL, J. W. 1997. Applied Numerical Linear Algebra. SIAM, Philadelphia, PA.]] Google Scholar
8. DESBRUN, M., MEYER, M., SCHRÖDER, P., AND BARR, A. H. 1999. Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow. In Proceedings of SIGGRAPH, 317–324.]] Google Scholar
9. DESBRUN, M., MEYER, M., AND ALLIEZ, P. 2002. Intrinsic Parameterizations of Surface Meshes. Computer Graphics Forum (Proceedings of Eurographics) 21, 3, 209–218.]]Google ScholarCross Ref
10. DIEWALD, U., MORIGI, S., AND RUMPF, M. 2002. A Cascadic Geometric Filtering Approach to Subdivision. Comput. Aided Geom. Des. 19, 9, 675–694.]] Google ScholarDigital Library
11. FEDKIW, R., STAM, J., AND JENSEN, H. W. 2001. Visual Simulation of Smoke. In Proceedings of SIGGRAPH, 15–22.]] Google Scholar
12. GOODNIGHT, N., LEWIN, G., LUEBKE, D., AND SKADRON, K. 2003. A Multigrid Solver for Boundary Value Problems Using Programmable Graphics Hardware. Tech. Rep. CS-2003-03, University of Virginia.]]Google Scholar
13. HACKBUSCH, W. 1985. Multi-Grid Methods and Applications. Springer Verlag, Berlin.]]Google Scholar
14. HALL, J. D., CARR, N. A., AND HART, J. C. 2003. Cache and Bandwidth Aware Matrix Multiplication on the GPU. Tech. rep., University of Illinois.]]Google Scholar
15. HARRIS, M. J., COOMBE, G., SCHEUERMANN, T., AND LASTRA, A. 2002. Physically-Based Visual Simulation on Graphics Hardware. In SIGGRAPH/Eurographics Workshop on Graphics Hardware.]] Google Scholar
16. HARRIS, M. J. 2002. Analysis of Error in a CML Diffusion Operation. Tech. Rep. TR02-015, UNC Chapel Hill.]]Google Scholar
17. HILLESLAND, K. E., MOLINOV, S., AND GRZESZCZUK, R. 2003. Nonlinear Optimization Framework for Image-Based Modeling on Programmable Graphics Hardware. ACM Transactions on Graphics.]] Google Scholar
18. HOFF, K. E., KEYSER, J., LIN, M., MANOCHA, D., AND CULVER, T. 1999. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. In Proceedings of SIGGRAPH, 277–286.]] Google ScholarDigital Library
19. KASS, M., AND MILLER, G. 1990. Rapid, Stable Fluid Dynamics for Computer Graphics. Computer Graphics (Proceedings of SIGGRAPH) 24, 4, 49–57.]] Google ScholarCross Ref
20. KELLER, A. 1997. Instant Radiosity. In Proceedings of SIGGRAPH, 49–56.]] Google Scholar
21. KHAILANY, B., DALLY, W. J., RIXNER, S., KAPASI, U. J., MATTSON, P., NAMKOONG, J., OWENS, J. D., TOWLES, B., AND CHANG, A. 2001. Imagine: Media Processing with Streams. IEEE Micro 21, 2, 35–46.]] Google ScholarDigital Library
22. KHAILANY, B., DALLY, W. J., RIXNER, S., KAPASI, U. J., OWENS, J. D., AND TOWLES, B. 2003. Exploring the VLSI Scalability of Stream Processors. In Proceedings of the Ninth Symposium on High Performance Computer Architecture.]] Google Scholar
23. KOBBELT, L., CAMPAGNA, S., VORSATZ, J., AND SEIDEL, H.-P. 1998. Interactive Multi-Resolution Modeling on Arbitrary Meshes. In Proceedings of SIGGRAPH, 105–114.]] Google Scholar
24. KRÜGER, J., AND WESTERMANN, R. 2003. Linear algebra operators for gpu implementation of numerical algorithms. ACM Transactions on Graphics.]] Google Scholar
25. LARSEN, E. S., AND MCALLISTER, D. K. 2001. Fast Matrix Multiplies using Graphics Hardware. In Supercomputing.]] Google Scholar
26. LEISERSON, C., ROSE, F., AND SAXE, J. 1993. Optimizing synchronous circuitry by retiming. In Third Caltech Conference On VLSI.]]Google Scholar
27. LENGYEL, J., REICHERT, M., DONALD, B. R., AND GREENBERG, D. P. 1990. Real-Time Robot Motion Planning Using Rasterizing Computer Graphics Hardware. Computer Graphics (Proceedings of SIGGRAPH) 24, 327–335.]] Google ScholarCross Ref
28. LI, W., WEI, X., AND KAUFMAN, A. 2003. Implementing Lattice Boltzmann Comptuation on Graphics Hardware. The Visual Computer. To appear.]]Google Scholar
29. LINDHOLM, E., KILGARD, M. J., AND MORETON, H. 2001. A User-Programmable Vertex Engine. In Proceedings of SIGGRAPH, 149–158.]] Google Scholar
30. MÜLLER, M., DORSEY, J., MCMILLAN, L., JAGNOW, R., AND CUTLER, B. 2002. Stable Real-Time Deformations. In ACM SIGGRAPH Symposium on Computer Animation, 49–54.]] Google Scholar
31. OLANO, M., Ed. 2002. Real-Time Shading Languages. Course Notes. ACM SIGGRAPH.]] Google Scholar
32. OWENS, J. D., KHAILANY, B., TOWLES, B., AND DALLY, W. J. 2002. Comparing Reyes and OpenGL on a Stream Architecture. In SIGGRAPH/Eurographics Workshop on Graphics Hardware, 47–56.]] Google Scholar
33. PURCELL, T. J., BUCK, I., MARK, W. R., AND HANRAHAN, P. 2002. Ray Tracing on Programmable Graphics Hardware. ACM Transactions on Graphics 21, 3, 703–712.]] Google ScholarDigital Library
34. SEMICONDUCTOR INDUSTRY ASSOCIATION, 2002. International Technology Roadmap for Semiconductors. http://public.itrs.net/, December.]]Google Scholar
35. SHEWCHUCK, J. R. 1994. An Introduction to the Conjugate Gradient Method without the Agonizing Pain. http://www.cs.cmu.edu/~quakepapers/painless-conjugate-gradient.ps., August.]]Google Scholar
36. STAM, J. 1999. Stable Fluids. In Proceedings of SIGGRAPH, 121–128.]] Google Scholar
37. STRZODKA, R., AND RUMPF, M. 2001. Nonlinear Diffusion in Graphics Hardware. In Visualization, 75–84.]]Google Scholar
38. STRZODKA, R. 2002. Virtual 16 Bit Precise Operations on RGBA8 Textures. In Vision, Modeling and Visualization.]]Google Scholar
39. THE C* TEAM. 1993. C* Manual, 2nd ed. Thinking Machines Corporation.]]Google Scholar
40. THOMPSON, C. J., HAHN, S., AND OSKIN, M. 2002. Using Modern Graphics Architectures for General-Purpose Computing: A Framework and Analysis. In International Symposium on Microarchitecture.]] Google Scholar