More Web Proxy on the site http://driver.im/

article

Sparse matrix solvers on the GPU: conjugate gradients and multigrid

Authors:

Eitan Grinspun,

Peter SchröderAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 22, Issue 3

Pages 917 - 924

https://doi.org/10.1145/882262.882364

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)

Download
30.88 MB

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.]]

Digital 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.]]

[3]

BLELLOCH, G. E. 1990. Vector Models for Data-Parallel Computing. MIT Press.]]

Digital Library

[4]

BRIGGS, W. L., HENSON, V. E., AND MCCORMACK, S. F. 2000. A Multigrid Tutorial, 2nd ed. SIAM.]]

Digital Library

[5]

CARR, N. A., HALL, J. D., AND HART, J. C. 2002. The Ray Engine. In SIGGRAPH/Eurographics Workshop on Graphics Hardware.]]

Digital Library

[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.]]

Digital Library

[7]

DEMMEL, J. W. 1997. Applied Numerical Linear Algebra. SIAM, Philadelphia, PA.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[11]

FEDKIW, R., STAM, J., AND JENSEN, H. W. 2001. Visual Simulation of Smoke. In Proceedings of SIGGRAPH, 15--22.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[19]

KASS, M., AND MILLER, G. 1990. Rapid, Stable Fluid Dynamics for Computer Graphics. Computer Graphics (Proceedings of SIGGRAPH) 24, 4, 49--57.]]

Digital Library

[20]

KELLER, A. 1997. Instant Radiosity. In Proceedings of SIGGRAPH, 49--56.]]

Digital Library

[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.]]

Digital 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.]]

Digital Library

[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.]]

Digital Library

[24]

KRÜGER, J., AND WESTERMANN, R. 2003. Linear algebra operators for gpu implementation of numerical algorithms. ACM Transactions on Graphics.]]

Digital Library

[25]

LARSEN, E. S., AND MCALLISTER, D. K. 2001. Fast Matrix Multiplies using Graphics Hardware. In Supercomputing.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[31]

OLANO, M., Ed. 2002. Real-Time Shading Languages. Course Notes. ACM SIGGRAPH.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

[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.]]

Digital Library

Cited By

Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Zhang JHuang HSun JLuna JMutlu OWang Z(2024)SparseACC: A Generalized Linear Model Accelerator for Sparse DatasetsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.332427643:3(840-853)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TCAD.2023.3324276
Jo MPark WKim MLee W(2024)Accelerated Finite Element Method Solver for RCS Analysis Using CUDA-Based Parallel ComputingIEEE Access10.1109/ACCESS.2024.344991412(120375-120388)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3449914
Show More Cited By

Index Terms

Sparse matrix solvers on the GPU: conjugate gradients and multigrid
1. Computing methodologies
  1. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics processors
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Partial differential equations
    2. Numerical analysis
      1. Computations on matrices

Recommendations

Sparse matrix solvers on the GPU: conjugate gradients and multigrid
SIGGRAPH '05: ACM SIGGRAPH 2005 Courses

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 ...
Sparse matrix solvers on the GPU: conjugate gradients and multigrid
SIGGRAPH '03: ACM SIGGRAPH 2003 Papers

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 ...
Interactive smoke simulation and rendering on the GPU
VRCAI '13: Proceedings of the 12th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry

We present a fluid dynamic system, which allows to moving objects and real-time simulations of large scale three dimensional smokes. Our system includes a GPU accelerated Eulerian fluid solver which is well suited for real-time application since it is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 22, Issue 3

July 2003

683 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/882262

Issue’s Table of Contents

Copyright © 2003 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2003

Published in TOG Volume 22, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

467
Total Citations
View Citations
6,961
Total Downloads

Downloads (Last 12 months)131
Downloads (Last 6 weeks)25

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Zhang JHuang HSun JLuna JMutlu OWang Z(2024)SparseACC: A Generalized Linear Model Accelerator for Sparse DatasetsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.332427643:3(840-853)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TCAD.2023.3324276
Jo MPark WKim MLee W(2024)Accelerated Finite Element Method Solver for RCS Analysis Using CUDA-Based Parallel ComputingIEEE Access10.1109/ACCESS.2024.344991412(120375-120388)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3449914
Wu SWang YHou JMeng R(2024)GPU parallel computation strategy for electrothermal coupling problems using improved assembly-free FEMJournal of Computational Design and Engineering10.1093/jcde/qwae02411:2(269-284)Online publication date: 15-Mar-2024
https://doi.org/10.1093/jcde/qwae024
Prades JReaño CSilla F(2024)NGSJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2024.103138151:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.sysarc.2024.103138
Baioni PBenacchio TCapone Lde Falco C(2024)Portable, massively parallel implementation of a material point method for compressible flowsComputational Particle Mechanics10.1007/s40571-024-00864-2Online publication date: 9-Dec-2024
https://doi.org/10.1007/s40571-024-00864-2
Lyu LCao WRen XWu EYang Z(2024)Efficient odd–even multigrid for pointwise incompressible fluid simulation on GPUThe Visual Computer10.1007/s00371-024-03264-yOnline publication date: 13-Feb-2024
https://doi.org/10.1007/s00371-024-03264-y
Merchant F(2024)Architectures for Scientific ComputingHandbook of Computer Architecture10.1007/978-981-15-6401-7_16-1(1-14)Online publication date: 17-Sep-2024
https://doi.org/10.1007/978-981-15-6401-7_16-1
Schuchart JGabriel E(2024)Stream Support in MPI Without the ChurnRecent Advances in the Message Passing Interface10.1007/978-3-031-73370-3_4(56-72)Online publication date: 25-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-73370-3_4
Diehl PBrandt SKaiser HDiehl PBrandt SKaiser H(2024)Accelerator CardsParallel C++10.1007/978-3-031-54369-2_17(185-186)Online publication date: 3-Feb-2024
https://doi.org/10.1007/978-3-031-54369-2_17
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents