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

SIGGRAPH '03: ACM SIGGRAPH 2003 Papers

Pages 917 - 924

https://doi.org/10.1145/1201775.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

Yuan CShi HLan LQiu YYuksel CWang HJiang CWu KYang Y(2024)Volumetric Homogenization for Knitwear SimulationACM Transactions on Graphics10.1145/368791143:6(1-19)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687911
Chen ALiu ZYang YYuksel C(2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658179
Adabag EAtal MGerard WPlancher B(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
https://doi.org/10.1109/ICRA57147.2024.10611212
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

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 '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 ...
GPU-accelerated preconditioned iterative linear solvers

This work is an overview of our preliminary experience in developing a high-performance iterative linear solver accelerated by GPU coprocessors. Our goal is to illustrate the advantages and difficulties encountered when deploying GPU technology to ...

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

Conference Chair:
Alyn P. Rockwood
Colorado School of Mines

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]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGGRAPH03

Sponsor:

SIGGRAPH

SIGGRAPH03: Special Interest Group on Computer Graphics and Interactive Techniques

July 27 - 31, 2003

California, San Diego

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

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

116
Total Citations
View Citations
6,463
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yuan CShi HLan LQiu YYuksel CWang HJiang CWu KYang Y(2024)Volumetric Homogenization for Knitwear SimulationACM Transactions on Graphics10.1145/368791143:6(1-19)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687911
Chen ALiu ZYang YYuksel C(2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658179
Adabag EAtal MGerard WPlancher B(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
https://doi.org/10.1109/ICRA57147.2024.10611212
Bu XPlancher B(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
https://doi.org/10.1109/ICRA57147.2024.10610386
Guo JLiu JWang QZhu X(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
https://doi.org/10.1007/978-981-97-0801-7_2
Kim JJang MNam HKim S(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
https://dl.acm.org/doi/10.1145/3613424.3623790
Pérez PGangnet MBlake A(2023)Poisson Image EditingSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596772(577-582)Online publication date: 2-Aug-2023
https://doi.org/10.1145/3596711.3596772
Lan LLi MJiang CWang HYang Y(2023)Second-order Stencil Descent for Interior-point HyperelasticityACM Transactions on Graphics10.1145/359210442:4(1-16)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592104
Giannoula CFernandez ILuna JKoziris NGoumas GMutlu O(2022)SparsePProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35080416:1(1-49)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3508041
Walden AZubair MStone CNielsen E(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
https://doi.org/10.1109/MCHPC54807.2021.00010
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents