“A fast unsmoothed aggregation algebraic multigrid framework for the large-scale simulation of incompressible flow” by Shao, Huang and Michels

Multigrid methods are quite efficient for solving the pressure Poisson equation in simulations of incompressible flow. However, for viscous liquids, geometric multigrid turned out to be less efficient for solving the variational viscosity equation. In this contribution, we present an Unsmoothed Aggregation Algebraic MultiGrid (UAAMG) method with a multi-color Gauss-Seidel smoother, which consistently solves the variational viscosity equation in a few iterations for various material parameters. Moreover, we augment the OpenVDB data structure with Intel SIMD intrinsic functions to perform sparse matrix-vector multiplications efficiently on all multigrid levels. Our framework is 2.0 to 14.6 times faster compared to the state-of-the-art adaptive octree solver in commercial software for the large-scale simulation of both non-viscous and viscous flow. The code is available at http://computationalsciences.org/publications/shao-2022-multigrid.html.

1. Mridul Aanjaneya, Ming Gao, Haixiang Liu, Christopher Batty, and Eftychios Sifakis. 2017. Power Diagrams and Sparse Paged Grids for High Resolution Adaptive Liquids. ACM Trans. Graph. 36, 4, Article 140 (2017), 12 pages.Google ScholarDigital Library
2. Mridul Aanjaneya, Chengguizi Han, Ryan Goldade, and Christopher Batty. 2019. An Efficient Geometric Multigrid Solver for Viscous Liquids. Proceedings of the ACM on Computer Graphics and Interactive Techniques 2, 2 (2019), 1–21.Google ScholarDigital Library
3. Ryoichi Ando and Christopher Batty. 2020. A Practical Octree Liquid Simulator with Adaptive Surface Resolution. 39, 4, Article 32 (2020), 17 pages.Google Scholar
4. Christopher Batty. 2018. VariationalViscosity3D. https://github.com/christopherbatty/VariationalViscosity3D.Google Scholar
5. Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Transactions on Graphics (TOG) 26, 3 (2007), 100–es.Google ScholarDigital Library
6. Christopher Batty and Robert Bridson. 2008. Accurate viscous free surfaces for buckling, coiling, and rotating liquids. (2008).Google Scholar
7. Jan Bender and Dan Koschier. 2017. Divergence-free SPH for incompressible and viscous fluids. IEEE Transactions on Visualization and Computer Graphics 23, 3 (March 2017), 1193–1206.Google ScholarDigital Library
8. Jeff Bolz, Ian Farmer, Eitan Grinspun, and Peter Schröder. 2003. Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid. ACM Trans. Graph. 22, 3 (July 2003), 917–924.Google ScholarDigital Library
9. Robert Bridson. 2016. Fluid Simulation for Computer Graphics. CRC Press.Google ScholarDigital Library
10. Robert Bridson and Matthias Müller-Fischer. 2007. Fluid simulation: SIGGRAPH 2007 course notes Video files associated with this course are available from the citation page. In ACM SIGGRAPH 2007 courses. 1–81.Google ScholarDigital Library
11. William L. Briggs, Van Emden Henson, and Steve F. McCormick. 2000. A multigrid tutorial. SIAM.Google ScholarDigital Library
12. Oliver Bröker, Marcus J. Grote, Carsten Mayer, and Arnold Reusken. 2001. Robust Parallel Smoothing for Multigrid Via Sparse Approximate Inverses. 23, 4 (apr 2001), 1396–1417.Google Scholar
13. Nuttapong Chentanez and Matthias Müller. 2011. Real-time Eulerian water simulation using a restricted tall cell grid. ACM Trans. Graph. 30, 4 (2011), 82.Google ScholarDigital Library
14. Nuttapong Chentanez and Matthias Müller-Fischer. 2012. A Multigrid Fluid Pressure Solver Handling Separating Solid Boundary Conditions. IEEE Transactions on Visualization and Computer Graphics 18, 8 (2012), 1191–1201.Google ScholarDigital Library
15. Alexandre Joel Chorin. 1967. The numerical solution of the Navier-Stokes equations for an incompressible fluid. Bull. Amer. Math. Soc. 73, 6 (1967), 928–931.Google ScholarCross Ref
16. Denis Demidov. 2019. AMGCL: An Efficient, Flexible, and Extensible Algebraic Multigrid Implementation. Lobachevskii Journal of Mathematics 40, 5 (01 May 2019), 535–546.Google ScholarCross Ref
17. Denis Demidov. 2020. AMGCL – A C++ library for efficient solution of large sparse linear systems. Software Impacts 6 (2020), 100037.Google ScholarCross Ref
18. Christian Dick, Marcus Rogowsky, and Rüdiger Westermann. 2015. Solving the fluid pressure Poisson equation using multigrid—evaluation and improvements. IEEE transactions on visualization and computer graphics 22, 11 (2015), 2480–2492.Google Scholar
19. Douglas Enright, Stephen Marschner, and Ronald Fedkiw. 2002. Animation and Rendering of Complex Water Surfaces. ACM Trans. Graph. 21, 3 (July 2002), 736–744.Google ScholarDigital Library
20. Florian Ferstl, Rüdiger Westermann, and Christian Dick. 2014. Large-Scale Liquid Simulation on Adaptive Hexahedral Grids. IEEE Transactions on Visualization and Computer Graphics 20, 10 (2014), 1405–1417.Google ScholarCross Ref
21. Nick Foster and Ronald Fedkiw. 2001. Practical animation of liquids. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. 23–30.Google ScholarDigital Library
22. Frederic Gibou, Ronald P Fedkiw, Li-Tien Cheng, and Myungjoo Kang. 2002. A second-order-accurate symmetric discretization of the Poisson equation on irregular domains. J. Comput. Phys. 176, 1 (2002), 205–227.Google ScholarDigital Library
23. Ryan Goldade, Yipeng Wang, Mridul Aanjaneya, and Christopher Batty. 2019. An Adaptive Variational Finite Difference Framework for Efficient Symmetric Octree Viscosity. ACM Trans. Graph. 38, 4, Article 94 (July 2019), 14 pages.Google ScholarDigital Library
24. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
25. Markus Ihmsen, Jens Cornelis, Barbara Solenthaler, Christopher Horvath, and Matthias Teschner. 2014a. Implicit incompressible SPH. IEEE Transactions on Visualization and Computer Graphics 20, 3 (March 2014), 426–435.Google ScholarDigital Library
26. Markus Ihmsen, Jens Orthmann, Barbara Solenthaler, Andreas Kolb, and Matthias Teschner. 2014b. SPH Fluids in Computer Graphics. In Eurographics 2014 – State of the Art Reports.Google Scholar
27. Chenfanfu Jiang, Craig Schroeder, Andrew Selle, Joseph Teran, and Alexey Stomakhin. 2015. The Affine Particle-in-Cell Method. ACM Trans. Graph. 34, 4, Article 51 (July 2015), 10 pages.Google ScholarDigital Library
28. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson Surface Reconstruction. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing (Cagliari, Sardinia, Italy) (SGP ’06). Eurographics Association, Goslar, DEU, 61–70.Google ScholarDigital Library
29. Dan Koschier, Jan Bender, Barbara Solenthaler, and Matthias Teschner. 2019. Smoothed Particle Hydrodynamics for Physically-Based Simulation of Fluids and Solids. In EUROGRAPHICS 2019 Tutorials. The Eurographics Association.Google Scholar
30. Egor Larionov, Christopher Batty, and Robert Bridson. 2017. Variational Stokes: A Unified Pressure-Viscosity Solver for Accurate Viscous Liquids. ACM Trans. Graph. 36, 4, Article 101 (July 2017), 11 pages.Google ScholarDigital Library
31. Haixiang Liu, Yuanming Hu, Bo Zhu, Wojciech Matusik, and Eftychios Sifakis. 2018. Narrow-Band Topology Optimization on a Sparsely Populated Grid. ACM Trans. Graph. 37, 6, Article 251 (dec 2018), 14 pages.Google ScholarDigital Library
32. Frank Losasso, Ronald Fedkiw, and Stanley Osher. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Computers and Fluids 35 (2005), 2006.Google Scholar
33. 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
34. Chaoyang Lyu, Wei Li, Mathieu Desbrun, and Xiaopei Liu. 2021. Fast and Versatile Fluid-Solid Coupling for Turbulent Flow Simulation. ACM Trans. Graph. 40, 6, Article 201 (dec 2021), 18 pages.Google ScholarDigital Library
35. 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 (Madrid, Spain) (SCA ’10). Eurographics Association, Goslar, DEU, 65–74.Google ScholarDigital Library
36. Nathan Mitchell, Michael Doescher, and Eftychios Sifakis. 2016. A Macroblock Optimization for Grid-Based Nonlinear Elasticity. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Zurich, Switzerland) (SCA ’16). Eurographics Association, Goslar, DEU, 11–19.Google ScholarDigital Library
37. Jeroen Molemaker, Jonathan M. Cohen, Sanjit Patel, and Jonyong Noh. 2008. Low Viscosity Flow Simulations for Animation (SCA ’08). Eurographics Association, Goslar, DEU, 9–18.Google Scholar
38. Matthias Müller-Fischer, David Charypar, and Markus Gross. 2003. Particle-based fluid simulation for interactive applications. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (San Diego, California) (SCA ’03). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 154–159.Google Scholar
39. Ken Museth. 2013. VDB: High-Resolution Sparse Volumes with Dynamic Topology. ACM Trans. Graph. 32, 3, Article 27 (June 2013), 22 pages.Google ScholarDigital Library
40. Yen Ting Ng, Chohong Min, and Frédéric Gibou. 2009. An efficient fluid-solid coupling algorithm for single-phase flows. J. Comput. Phys. 228, 23 (2009), 8807–8829.Google ScholarDigital Library
41. Xingyu Ni, Bo Zhu, Bin Wang, and Baoquan Chen. 2020. A Level-Set Method for Magnetic Substance Simulation. ACM Trans. Graph. 39, 4, Article 29 (July 2020), 15 pages.Google ScholarDigital Library
42. John W Ruge and Klaus Stüben. 1987. Algebraic multigrid. In Multigrid methods. SIAM, 73–130.Google Scholar
43. Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A Sparse Paged Grid Structure Applied to Adaptive Smoke Simulation. ACM Trans. Graph. 33, 6, Article 205 (Nov. 2014), 12 pages.Google ScholarDigital Library
44. Side Effects Software. 2021. Houdini 19.0. (2021).Google Scholar
45. Barbara Solenthaler and Renato Pajarola. 2009. Predictive-corrective incompressible SPH. ACM Trans. Graph. 28, 3, Article 40 (2009), 6 pages.Google ScholarDigital Library
46. Jos Stam. 1999. Stable Fluids. Proc. of ACM SIGGRAPH (1999), 121–128.Google Scholar
47. Klaus Stüben. 2001. A review of algebraic multigrid. J. Comput. Appl. Math. 128, 1 (2001), 281–309. Numerical Analysis 2000. Vol. VII: Partial Differential Equations.Google ScholarDigital Library
48. Tetsuya Takahashi and Ming C. Lin. 2019. A Geometrically Consistent Viscous Fluid Solver with Two-Way Fluid-Solid Coupling. Computer Graphics Forum 38, 2 (2019), 49–58.Google ScholarCross Ref
49. Rasmus Tamstorf, Toby Jones, and Stephen F. McCormick. 2015. Smoothed Aggregation Multigrid for Cloth Simulation. ACM Trans. Graph. 34, 6, Article 245 (oct 2015), 13 pages.Google ScholarDigital Library
50. Nils Thürey and Ulrich Rüde. 2009. Stable Free Surface Flows with the Lattice Boltzmann Method on Adaptively Coarsened Grids. Comput. Vis. Sci. 12, 5 (June 2009), 247–263.Google Scholar
51. Peter Vaněk, Marian Brezina, and Jan Mandel. 2001. Convergence of algebraic multigrid based on smoothed aggregation. Numer. Math. 88, 3 (2001), 559–579.Google ScholarCross Ref
52. Petr Vaněk, Jan Mandel, and Marian Brezina. 1996. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 3 (1996), 179–196.Google ScholarCross Ref
53. Xinlei Wang, Minchen Li, Yu Fang, Xinxin Zhang, Ming Gao, Min Tang, Danny M. Kaufman, and Chenfanfu Jiang. 2020. Hierarchical Optimization Time Integration for CFL-Rate MPM Stepping. ACM Trans. Graph. 39, 3, Article 21 (Apr 2020), 16 pages.Google ScholarDigital Library
54. Zhendong Wang, Longhua Wu, Marco Fratarcangeli, Min Tang, and Huamin Wang. 2018. Parallel multigrid for nonlinear cloth simulation. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 131–141.Google Scholar
55. Daniel Weber, Johannes Mueller-Roemer, André Stork, and Dieter Fellner. 2015. A Cut-Cell Geometric Multigrid Poisson Solver for Fluid Simulation. Computer Graphics Forum 34, 2 (2015), 481–491.Google ScholarDigital Library
56. Zangyueyang Xian, Xin Tong, and Tiantian Liu. 2019. A Scalable Galerkin Multigrid Method for Real-Time Simulation of Deformable Objects. ACM Trans. Graph. 38, 6, Article 162 (nov 2019), 13 pages.Google ScholarDigital Library
57. Xiang Yang and Rajat Mittal. 2017. Efficient relaxed-Jacobi smoothers for multigrid on parallel computers. J. Comput. Phys. 332 (2017), 135–142.Google ScholarCross Ref
58. Omar Zarifi. 2020. Sparse Smoke Simulations in Houdini. In Special Interest Group on Computer Graphics and Interactive Techniques Conference Talks. 1–2.Google Scholar
59. Yongning Zhu and Robert Bridson. 2005. Animating sand as a fluid. ACM Transactions on Graphics (TOG) 24, 3 (2005), 965–972.Google ScholarDigital Library
60. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An Efficient Multigrid Method for the Simulation of High-Resolution Elastic Solids. ACM Trans. Graph. 29, 2, Article 16 (apr 2010), 18 pages.Google ScholarDigital Library