[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1201775.882364acmconferencesArticle/Chapter ViewAbstractPublication PagessiggraphConference Proceedingsconference-collections
Article

Sparse matrix solvers on the GPU: conjugate gradients and multigrid

Published: 01 July 2003 Publication History

Abstract

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.

Supplementary Material

MP4 File (bolz_farmer_sparse.mp4)

References

[1]
ARVIND, AND IANNUCCI, R. A. 1987. Two Fundamental Issues in Multiprocessing. In Proceedings of DFVLR-Conference 1987, Parallel Processing in Science and Engineering.]]
[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.]]
[3]
BLELLOCH, G. E. 1990. Vector Models for Data-Parallel Computing. MIT Press.]]
[4]
BRIGGS, W. L., HENSON, V. E., AND MCCORMACK, S. F. 2000. A Multigrid Tutorial, 2nd ed. SIAM.]]
[5]
CARR, N. A., HALL, J. D., AND HART, J. C. 2002. The Ray Engine. In SIGGRAPH/Eurographics Workshop on Graphics Hardware.]]
[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.]]
[7]
DEMMEL, J. W. 1997. Applied Numerical Linear Algebra. SIAM, Philadelphia, PA.]]
[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.]]
[9]
DESBRUN, M., MEYER, M., AND ALLIEZ, P. 2002. Intrinsic Parameterizations of Surface Meshes. Computer Graphics Forum (Proceedings of Eurographics) 21, 3, 209--218.]]
[10]
DIEWALD, U., MORIGI, S., AND RUMPF, M. 2002. A Cascadic Geometric Filtering Approach to Subdivision. Comput. Aided Geom. Des. 19, 9, 675--694.]]
[11]
FEDKIW, R., STAM, J., AND JENSEN, H. W. 2001. Visual Simulation of Smoke. In Proceedings of SIGGRAPH, 15--22.]]
[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.]]
[13]
HACKBUSCH, W. 1985. Multi-Grid Methods and Applications. Springer Verlag, Berlin.]]
[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.]]
[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.]]
[16]
HARRIS, M. J. 2002. Analysis of Error in a CML Diffusion Operation. Tech. Rep. TR02-015, UNC Chapel Hill.]]
[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.]]
[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.]]
[19]
KASS, M., AND MILLER, G. 1990. Rapid, Stable Fluid Dynamics for Computer Graphics. Computer Graphics (Proceedings of SIGGRAPH) 24, 4, 49--57.]]
[20]
KELLER, A. 1997. Instant Radiosity. In Proceedings of SIGGRAPH, 49--56.]]
[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.]]
[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.]]
[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.]]
[24]
KRÜGER, J., AND WESTERMANN, R. 2003. Linear algebra operators for gpu implementation of numerical algorithms. ACM Transactions on Graphics.]]
[25]
LARSEN, E. S., AND MCALLISTER, D. K. 2001. Fast Matrix Multiplies using Graphics Hardware. In Supercomputing.]]
[26]
LEISERSON, C., ROSE, F., AND SAXE, J. 1993. Optimizing synchronous circuitry by retiming. In Third Caltech Conference On VLSI.]]
[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.]]
[28]
LI, W., WEI, X., AND KAUFMAN, A. 2003. Implementing Lattice Boltzmann Comptuation on Graphics Hardware. The Visual Computer. To appear.]]
[29]
LINDHOLM, E., KILGARD, M. J., AND MORETON, H. 2001. A User-Programmable Vertex Engine. In Proceedings of SIGGRAPH, 149--158.]]
[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.]]
[31]
OLANO, M., Ed. 2002. Real-Time Shading Languages. Course Notes. ACM SIGGRAPH.]]
[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.]]
[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.]]
[34]
SEMICONDUCTOR INDUSTRY ASSOCIATION, 2002. International Technology Roadmap for Semiconductors. http://public.itrs.net/, December.]]
[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.]]
[36]
STAM, J. 1999. Stable Fluids. In Proceedings of SIGGRAPH, 121--128.]]
[37]
STRZODKA, R., AND RUMPF, M. 2001. Nonlinear Diffusion in Graphics Hardware. In Visualization, 75--84.]]
[38]
STRZODKA, R. 2002. Virtual 16 Bit Precise Operations on RGBA8 Textures. In Vision, Modeling and Visualization.]]
[39]
THE C* TEAM. 1993. C* Manual, 2nd ed. Thinking Machines Corporation.]]
[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.]]

Cited By

View all
  • (2024)Volumetric Homogenization for Knitwear SimulationACM Transactions on Graphics10.1145/368791143:6(1-19)Online publication date: 19-Dec-2024
  • (2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
  • (2024)MPCGPU: Real-Time Nonlinear Model Predictive Control through Preconditioned Conjugate Gradient on the GPU2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611212(9787-9794)Online publication date: 13-May-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGGRAPH '03: ACM SIGGRAPH 2003 Papers
July 2003
683 pages
ISBN:1581137095
DOI:10.1145/1201775
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2003

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. GPU computing
  2. Navier-Stokes
  3. conjugate gradient
  4. fluid simulation
  5. mesh smoothing
  6. multigrid
  7. numerical simulation

Qualifiers

  • Article

Conference

SIGGRAPH03
Sponsor:

Acceptance Rates

SIGGRAPH '03 Paper Acceptance Rate 81 of 424 submissions, 19%;
Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)2
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Volumetric Homogenization for Knitwear SimulationACM Transactions on Graphics10.1145/368791143:6(1-19)Online publication date: 19-Dec-2024
  • (2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
  • (2024)MPCGPU: Real-Time Nonlinear Model Predictive Control through Preconditioned Conjugate Gradient on the GPU2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611212(9787-9794)Online publication date: 13-May-2024
  • (2024)Symmetric Stair Preconditioning of Linear Systems for Parallel Trajectory Optimization2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610386(9779-9786)Online publication date: 13-May-2024
  • (2024)Optimizing CSR-Based SpMV on a New MIMD Architecture Pezy-SC3sAlgorithms and Architectures for Parallel Processing10.1007/978-981-97-0801-7_2(22-39)Online publication date: 1-Mar-2024
  • (2023)HARP: Hardware-Based Pseudo-Tiling for Sparse Matrix Multiplication AcceleratorProceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3613424.3623790(1148-1162)Online publication date: 28-Oct-2023
  • (2023)Poisson Image EditingSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596772(577-582)Online publication date: 2-Aug-2023
  • (2023)Second-order Stencil Descent for Interior-point HyperelasticityACM Transactions on Graphics10.1145/359210442:4(1-16)Online publication date: 26-Jul-2023
  • (2022)SparsePProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35080416:1(1-49)Online publication date: 28-Feb-2022
  • (2021)Memory Optimizations for Sparse Linear Algebra on GPU Hardware2021 IEEE/ACM Workshop on Memory Centric High Performance Computing (MCHPC)10.1109/MCHPC54807.2021.00010(25-32)Online publication date: Nov-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media