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

  • ©Jeff Bolz, Ian Farmer, Eitan Grinspun, and Peter Schröder




    Sparse matrix solvers on the GPU: conjugate gradients and multigrid



    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

ACM Digital Library Publication:

Overview Page: