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

research-article

A Schur Complement Preconditioner for Scalable Parallel Fluid Simulation

Authors:

Nafees Bin Zafar,

Xubo YangAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 36, Issue 4

Article No.: 139a, Page 1

https://doi.org/10.1145/3072959.3092818

Published: 25 July 2017 Publication History

Abstract

We present an algorithmically efficient and parallelized domain decomposition based approach to solving Poisson’s equation on irregular domains. Our technique employs the Schur complement method, which permits a high degree of parallel efficiency on multicore systems. We create a novel Schur complement preconditioner which achieves faster convergence, and requires less computation time and memory. This domain decomposition method allows us to apply different linear solvers for different regions of the flow. Subdomains with regular boundaries can be solved with an FFT-based Fast Poisson Solver. We can solve systems with 1,024³ degrees of freedom, and demonstrate its use for the pressure projection step of incompressible liquid and gas simulations. The results demonstrate considerable speedup over preconditioned conjugate gradient methods commonly employed to solve such problems, including a multigrid preconditioned conjugate gradient method.

Supplementary Material

MP4 File (tog-32.mp4)

Download
211.77 MB

References

[1]

Ryoichi Ando, Nils Thürey, and Chris Wojtan. 2013. Highly adaptive liquid simulations on tetrahedral meshes. ACM Trans. Graph 32, 4 (2013), 103.

Digital Library

[2]

Steven F. Ashby, Robert D. Falgout, Steven G. Smith, and Thomas W. Fogwell. 1994. Multigrid Preconditioned Conjugate Gradients for the Numerical Simulation of Groundwater Flow on the Cray T3D. Technical Report UCRL-JC-118622, Lawrence Livermore National Laboratory, Livermore, CA.

[3]

Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Trans. Graph 26, 3 (2007), 100.

Digital Library

[4]

Christopher Batty, Stefan Xenos, and Ben Houston. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. Comput. Graphics Forum 29, 2 (2010), 695--704.

[5]

Marsha Berger and J. Oliger. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53 (March 1984), 484--512.

[6]

Petter E. Bjørstad and Olof B. Widlund. 1986. Iterative methods for the solution of elliptic problems on regions partitioned into substructures. SIAM J. Numer. Anal. 23, 6 (1986), 1097--1120.

Digital Library

[7]

Morten Bojsen-Hansen and Chris Wojtan. 2013. Liquid surface tracking with error compensation. ACM Trans. Graph. 32, 4, Article 68 (July 2013), 13 pages.

Digital Library

[8]

Jean-Francois Bourgat, Roland Glowinski, Patrick Le Tallec, and Marina Vidrascu. 1989. Variational formulation and algorithm for trace operator in domain decomposition calculations. Tony Chan, Roland Glowinski, Jacques P eriaux, and Olof Widlund (Eds.). Domain Decomposition Methods, Philadelphia, PA.

[9]

James H. Bramble, Joseph E. Pasciak, and Alfred H. Schatz. 1986. The construction of preconditioners for elliptic problems by substructuring. I. Math. Comput. 47, 175 (1986), 103--134.

Digital Library

[10]

Robert Bridson. 2015. Fluid Simulation for Computer Graphics. CRC Press.

[11]

Robert Bridson and Chen Greif. 2006. A multipreconditioned conjugate gradient algorithm. SIAM J. Matrix Anal. Appl. 27, 4 (2006), 1056--1068.

Digital Library

[12]

X Cai. 2003. Overlapping domain decomposition methods. Advanced Topics in Computational Partial Differential Equations. Springer, 57--95.

[13]

Tony F. C. Chan and Tarek P. Mathew. 1992. The interface probing technique in domain decomposition. SIAM J. Matrix Anal. Appl. 13, 1 (1992), 212--238.

Digital Library

[14]

Nuttapong Chentanez, Bryan E. Feldman, François Labelle, James F. O’Brien, and Jonathan R. Shewchuk. 2007. Liquid simulation on lattice-based tetrahedral meshes. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’07). Eurographics Association, 219--228.

Digital Library

[15]

Nuttapong Chentanez and Matthias Mueller-Fischer. 2012. A multigrid fluid pressure solver handling separating solid boundary conditions. IEEE Trans. Vis. Comp. Graph 18, 8 (2012), 1191--1201.

Digital Library

[16]

Nuttapong Chentanez, Matthias Müller, and Tae-Yong Kim. 2014. Coupling 3D Eulerian, heightfield and particle methods for interactive simulation of large scale liquid phenomena. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’14). ACM, 1--10. http://dl.acm.org/citation.cfm?id=2849517.2849519

Digital Library

[17]

James W. Demmel. 1997. Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia, PA.

Digital Library

[18]

Christian Dick, Marcus Rogowsky, and Rüdiger Westermann. 2016. Solving the fluid pressure Poisson equation using multigrid--evaluation and improvements. IEEE Trans. Vis. Comput. Graph. 22, 11 (2016), 2480--2492.

[19]

R. Elliot English, Linhai Qiu, Yue Yu, and Ronald Fedkiw. 2013. Chimera grids for water simulation. In Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’13). ACM, New York, 85--94.

Digital Library

[20]

Robert D. Falgout. 2006. An introduction to algebraic multigrid computing. Comput. Sci. Eng. 8, 6 (Nov 2006), 24--33.

Digital Library

[21]

Florian Ferstl, Ryoichi Ando, Chris Wojtan, Rüdiger Westermann, and Nils Thuerey. 2016. Narrow band FLIP for liquid simulations. Comput. Graphics Forum (Proc. Eurographics) 35, 2 (2016), 225--232.

[22]

Florian Ferstl, Rüdiger Westermann, and Christian Dick. 2014. Large-scale liquid simulation on adaptive hexahedral grids. IEEE Trans. Vis. Comput. Graph. 20, 10 (2014), 1405--1417.

[23]

Nick Foster and Dimitri Metaxas. 1996. Realistic animation of liquids. Graph. Models Image Process. 58, 5 (1996), 471--483.

Digital Library

[24]

Jean Gallier. 2010. The Schur complement and symmetric positive semidefinite (and definite) matrices. Retrieved from http://www.cis.upenn.edu/&sim;jean/schur-comp.pdf.

[25]

Abhinav Golas, Rahul Narain, Jason Sewall, Pavel Krajcevski, Pradeep Dubey, and Ming Lin. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. ACM Trans. Graph. 31, 6 (2012), 148.

Digital Library

[26]

Ryan Goldade, Christopher Batty, and Chris Wojtan. 2016. A practical method for high-resolution embedded liquid surfaces. Comput. Graph. Forum (Proc. Eurographics 2016) (2016).

[27]

Gene H. Golub, Lan Chieh Huang, Horst Simon, and Wei-Pai Tang. 1998. A fast Poisson solver for the finite difference solution of the incompressible Navier-Stokes equations. SIAM Journal on Scientific Computing 19, 5 (1998), 1606--1624.

Digital Library

[28]

Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press, Baltimore, MD.

Digital Library

[29]

Ronald D. Henderson. 1997. Nonlinear dynamics and pattern formation in turbulent wake transition. J. Fluid Mech. 352 (1997), 65--112.

[30]

Ronald D. Henderson. 2012. Scalable fluid simulation in linear time on shared memory multiprocessors. In Proceedings of the Digital Production Symposium. ACM, 43--52.

Digital Library

[31]

Christopher J. Hughes, Radek Grzeszczuk, Eftychios Sifakis, Daehyun Kim, Sanjeev Kumar, Andrew P. Selle, Jatin Chhugani, Matthew Holliman, and Yen-Kuang Chen. 2007. Physical simulation for animation and visual effects: Parallelization and characterization for chip multiprocessors. SIGARCH Comput. Archit. News 35, 2 (June 2007), 220--231.

Digital Library

[32]

Doyub Kim, Oh-young Song, and Hyeong-Seok Ko. 2009. Stretching and wiggling liquids. ACM Trans. Graph. 28, 5, Article 120 (Dec. 2009), 7 pages.

Digital Library

[33]

Bryan M. Klingner, Bryan E. Feldman, Nuttapong Chentanez, and James F. O’Brien. 2006. Fluid animation with dynamic meshes. ACM Trans. Graph. 25, 3 (July 2006), 820--825.

Digital Library

[34]

Haixiang Liu, Nathan Mitchell, Mridul Aanjaneya, and Eftychios Sifakis. 2016. A scalable Schur--complement fluids solver for heterogeneous compute platforms. ACM Trans. Graph. 35, 6, Article 201 (Nov. 2016), 12 pages.

Digital Library

[35]

Frank Losasso, Frédéric Gibou, and Ron Fedkiw. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. 23, 3 (Aug. 2004), 457--462.

Digital Library

[36]

Jan Mandel. 1993. Balancing domain decomposition. Commun. Numer. Meth. Eng. 9, 3 (1993), 233--241.

[37]

Tarek Mathew. 2008. Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations. Vol. 61. Springer Science 8 Business Media.

Digital Library

[38]

Aleka McAdams, Eftychios Sifakis, and Joseph Teran. 2010. A parallel multigrid Poisson solver for fluids simulation on large grids. In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Eurographics Association, 65--74.

Digital Library

[39]

William F. Mitchell. 2010. A Collection of 2D Elliptic Problems for Testing Adaptive Algorithms. Technical Report NISTIR 7668. NIST.

[40]

Jeroen Molemaker, Jonathan M. Cohen, Sanjit Patel, and Jonyong Noh. 2008. Low viscosity flow simulations for animation. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Eurographics Association, 9--18.

Digital Library

[41]

Ken Museth. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans. Graph. 32, 3 (2013), 27.

Digital Library

[42]

William H. Press. 2007. Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press.

Digital Library

[43]

James Reinders. 2007. Intel Threading Building Blocks (1st ed.). O’Reilly 8 Associates, Inc., Sebastopol, CA.

Digital Library

[44]

Yousef Saad. 1994. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1, 4 (1994), 387--402.

[45]

Nicole Spillane. 2016. An Adaptive Multipreconditioned Conjugate Gradient Algorithm. (2016). https://hal.archives-ouvertes.fr/hal-01170059, working paper or preprint.

[46]

Jos Stam. 1999. Stable fluids. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. ACM/Addison-Wesley Publishing Co., 121--128.

Digital Library

[47]

Osamu Tatebe. 1993. The multigrid preconditioned conjugate gradient method. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. NASA Conference Publication, 621--634.

[48]

Charles H. Tong, Tony F. Chan, and C. C. Jay Kuo. 1991. A domain decomposition preconditioner based on a change to a multilevel nodal basis. SIAM J. Sci. Statist. Comput. 12, 6 (1991), 1486--1495.

Digital Library

[49]

Yang Yang, Xubo Yang, and Shuangcai Yang. 2016. A fast iterated orthogonal projection framework for smoke simulation. IEEE Trans. Vis. Comput. Graph. 22, 5 (2016), 1492--1502.

Digital Library

[50]

Yongning Zhu and Robert Bridson. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3 (July 2005), 965--972.

Digital Library

Cited By

Tao RRen HYang XWang DSun J(2025)Smoke Simulation with Detail Enhancement in Ship FiresJournal of Marine Science and Engineering10.3390/jmse1301010113:1(101)Online publication date: 7-Jan-2025
https://doi.org/10.3390/jmse13010101
Sung SKim JShin B(2024)Material Point Method-Based Simulation Techniques for Medical ApplicationsElectronics10.3390/electronics1307134013:7(1340)Online publication date: 2-Apr-2024
https://doi.org/10.3390/electronics13071340
Mullia KLuan FSun XHašan M(2024)RNA: Relightable Neural AssetsACM Transactions on Graphics10.1145/369586644:1(1-19)Online publication date: 12-Sep-2024
https://dl.acm.org/doi/10.1145/3695866
Show More Cited By

Index Terms

A Schur Complement Preconditioner for Scalable Parallel Fluid Simulation
1. Computing methodologies
  1. Computer graphics
    1. Animation
  2. Modeling and simulation
    1. Simulation types and techniques
      1. Massively parallel and high-performance simulations

Recommendations

A Schur Complement Preconditioner for Scalable Parallel Fluid Simulation

We present an algorithmically efficient and parallelized domain decomposition based approach to solving Poisson’s equation on irregular domains. Our technique employs the Schur complement method, which permits a high degree of parallel efficiency on ...
Constraint Schur complement preconditioners for nonsymmetric saddle point problems

We consider constraint preconditioners for block two-by-two generalized saddle point problems, this is the general nonsymmetric, nonsingular case where the (1,2) block need not equal the transposed (2,1) block and the (2,2) block may not be zero. The ...
A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems

A parallel preconditioner is proposed for general large sparse linear systems that combines a power series expansion method with low-rank correction techniques. To enhance convergence, a power series expansion is added to a basic Schur complement iterative ...

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 36, Issue 4

August 2017

2155 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3072959

Issue’s Table of Contents

Copyright © 2017 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: 25 July 2017

Accepted: 01 April 2017

Revised: 01 April 2017

Received: 01 September 2016

Published in TOG Volume 36, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National High Technology Research and Development Program of China
National Natural Science Foundation of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
455
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)5

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tao RRen HYang XWang DSun J(2025)Smoke Simulation with Detail Enhancement in Ship FiresJournal of Marine Science and Engineering10.3390/jmse1301010113:1(101)Online publication date: 7-Jan-2025
https://doi.org/10.3390/jmse13010101
Sung SKim JShin B(2024)Material Point Method-Based Simulation Techniques for Medical ApplicationsElectronics10.3390/electronics1307134013:7(1340)Online publication date: 2-Apr-2024
https://doi.org/10.3390/electronics13071340
Mullia KLuan FSun XHašan M(2024)RNA: Relightable Neural AssetsACM Transactions on Graphics10.1145/369586644:1(1-19)Online publication date: 12-Sep-2024
https://dl.acm.org/doi/10.1145/3695866
Shi HZordan VYang YAndrews S(2024)Adaptive Distributed Simulation of Fluids and Rigid BodiesProceedings of the 17th ACM SIGGRAPH Conference on Motion, Interaction, and Games10.1145/3677388.3696334(1-10)Online publication date: 21-Nov-2024
https://dl.acm.org/doi/10.1145/3677388.3696334
Li JGao YDai JLi SHao AQin H(2024)MPMNet: A Data-Driven MPM Framework for Dynamic Fluid-Solid InteractionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.327215630:8(4694-4708)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3272156
Zhang ZGao XChen QYuan Y(2024)A novel thermal turbulence reconstruction method using proper orthogonal decomposition and compressed sensing coupled based on improved particle swarm optimization for sensor arrangementPhysics of Fluids10.1063/5.020315936:5Online publication date: 8-May-2024
https://doi.org/10.1063/5.0203159
Tao RZhang XRen HDong YYang X(2024)A unified particle method for fluid simulation in ship fire scenarioOcean Engineering10.1016/j.oceaneng.2024.119266312(119266)Online publication date: Nov-2024
https://doi.org/10.1016/j.oceaneng.2024.119266
Flor AAanjaneya M(2024)Spectral reordering for faster elasticity simulationsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-024-03513-040:7(5067-5077)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s00371-024-03513-0
Wei LFreris N(2024)Multi-scale graph neural network for physics-informed fluid simulationThe Visual Computer10.1007/s00371-024-03402-6Online publication date: 17-May-2024
https://doi.org/10.1007/s00371-024-03402-6
Deng YYu HZhang DWu JZhu B(2023)Fluid Simulation on Neural Flow MapsACM Transactions on Graphics10.1145/361839242:6(1-21)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618392
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.

Figures

Tables

Media

View Issue’s Table of Contents