“A Schur Complement Preconditioner for Scalable Parallel Fluid Simulation” by Chu, Zafar and Yang
Conference:
Type(s):
Title:
- A Schur Complement Preconditioner for Scalable Parallel Fluid Simulation
Session/Category Title: Fluids III
Presenter(s)/Author(s):
Moderator(s):
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,0243 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.
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. Google ScholarDigital 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.Google Scholar
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. Google ScholarDigital 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.Google ScholarCross Ref
5. Marsha Berger and J. Oliger. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53 (March 1984), 484–512.Google ScholarCross Ref
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. Google ScholarDigital 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. Google ScholarDigital 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.Google Scholar
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. Google ScholarDigital Library
10. Robert Bridson. 2015. Fluid Simulation for Computer Graphics. CRC Press.Google Scholar
11. Robert Bridson and Chen Greif. 2006. A multipreconditioned conjugate gradient algorithm. SIAM J. Matrix Anal. Appl. 27, 4 (2006), 1056–1068. Google ScholarDigital Library
12. X Cai. 2003. Overlapping domain decomposition methods. Advanced Topics in Computational Partial Differential Equations. Springer, 57–95.Google Scholar
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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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 Google ScholarDigital Library
17. James W. Demmel. 1997. Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia, PA. Google ScholarDigital 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.Google ScholarCross Ref
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. Google ScholarDigital Library
20. Robert D. Falgout. 2006. An introduction to algebraic multigrid computing. Comput. Sci. Eng. 8, 6 (Nov 2006), 24–33. Google ScholarDigital 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.Google ScholarCross Ref
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.Google ScholarCross Ref
23. Nick Foster and Dimitri Metaxas. 1996. Realistic animation of liquids. Graph. Models Image Process. 58, 5 (1996), 471–483. Google ScholarDigital Library
24. Jean Gallier. 2010. The Schur complement and symmetric positive semidefinite (and definite) matrices. Retrieved from http://www.cis.upenn.edu/∼jean/schur-comp.pdf.Google Scholar
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. Google ScholarDigital 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).Google Scholar
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. Google ScholarDigital Library
28. Gene H. Golub and Charles F. Van Loan. 1996. Matrix Computations (3rd ed.). Johns Hopkins University Press, Baltimore, MD. Google ScholarDigital Library
29. Ronald D. Henderson. 1997. Nonlinear dynamics and pattern formation in turbulent wake transition. J. Fluid Mech. 352 (1997), 65–112.Google ScholarCross Ref
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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
36. Jan Mandel. 1993. Balancing domain decomposition. Commun. Numer. Meth. Eng. 9, 3 (1993), 233–241.Google ScholarCross Ref
37. Tarek Mathew. 2008. Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations. Vol. 61. Springer Science 8 Business Media. Google ScholarDigital 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. Google ScholarDigital Library
39. William F. Mitchell. 2010. A Collection of 2D Elliptic Problems for Testing Adaptive Algorithms. Technical Report NISTIR 7668. NIST.Google Scholar
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. Google ScholarDigital Library
41. Ken Museth. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans. Graph. 32, 3 (2013), 27. Google ScholarDigital Library
42. William H. Press. 2007. Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press.Google ScholarDigital Library
43. James Reinders. 2007. Intel Threading Building Blocks (1st ed.). O’Reilly 8 Associates, Inc., Sebastopol, CA. Google ScholarDigital Library
44. Yousef Saad. 1994. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1, 4 (1994), 387–402.Google ScholarCross Ref
45. Nicole Spillane. 2016. An Adaptive Multipreconditioned Conjugate Gradient Algorithm. (2016). https://hal.archives-ouvertes.fr/hal-01170059, working paper or preprint.Google Scholar
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. Google ScholarDigital 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.Google Scholar
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. Google ScholarDigital 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. Google ScholarDigital Library
50. Yongning Zhu and Robert Bridson. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3 (July 2005), 965–972. Google ScholarDigital Library
