A Multilevel Active-Set Preconditioner for Box-Constrained Pressure Poisson Solvers
Article No.: 50, Pages 1 - 22
Abstract
Efficiently solving large-scale box-constrained convex quadratic programs (QPs) is an important computational challenge in physical simulation. We propose a new multilevel preconditioning scheme based on the active-set method and combine it with modified proportioning with reduced gradient projections (MPRGP) to efficiently solve such QPs arising from pressure Poisson equations with non-negative pressure constraints in fluid animation. Our method employs a purely algebraic multigrid method to ensure the solvability of the coarser level systems and to merge only algebraically-connected components, thereby avoiding performance degradation of the preconditioner. We present a filtering scheme to efficiently apply our multilevel preconditioning only to unconstrained subsystems of the pressure Poisson system while reusing the hierarchy constructed per simulation step. We demonstrate the effectiveness of our method over previous approaches in various examples.
Supplemental Material
ZIP File - takahashi
Supplemental movie, appendix, image and software files for, A Multilevel Active-Set Preconditioner for Box-Constrained Pressure Poisson Solvers
- Download
- 66.88 MB
References
[1]
Mridul Aanjaneya. 2018. An Efficient Solver for Two-way Coupling Rigid Bodies with Incompressible Flow. Computer Graphics Forum 37, 8 (2018), 59--68.
[2]
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 (jul 2017), 12 pages.
[3]
Mridul Aanjaneya, Chengguizi Han, Ryan Goldade, and Christopher Batty. 2019. An Efficient Geometric Multigrid Solver for Viscous Liquids. Proc. ACM Comput. Graph. Interact. Tech. 2, 2, Article 14 (July 2019), 21 pages.
[4]
Mark Adams, Marian Brezina, Jonathan Hu, and Ray Tuminaro. 2003. Parallel Multigrid Smoothing: Polynomial versus Gauss--Seidel. J. Comput. Phys. 188, 2 (jul 2003), 593--610.
[5]
Steven S. An, Theodore Kim, and Doug L. James. 2008. Optimizing Cubature for Efficient Integration of Subspace Deformations. ACM Trans. Graph. 27, 5, Article 165 (dec 2008), 10 pages.
[6]
Michael Andersen, Sarah Niebe, and Kenny Erleben. 2017. A Fast Linear Complementarity Problem (LCP) Solver for Separating Fluid-Solid Wall Boundary Conditions. In Proceedings of the 13th Workshop on Virtual Reality Interactions and Physical Simulations (VRIPHYS '17). 39--48.
[7]
Sheldon Andrews, Kenny Erleben, and Zachary Ferguson. 2022. Contact and Friction Simulation for Computer Graphics. In ACM SIGGRAPH 2022 Courses (SIGGRAPH '22). Article 2, 124 pages.
[8]
Uri M Ascher and Eddy Boxerman. 2003. On the modified conjugate gradient method in cloth simulation. The Visual Computer 19 (2003), 526--531.
[9]
David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '98). Association for Computing Machinery, New York, NY, USA, 43--54.
[10]
Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A Fast Variational Framework for Accurate Solid-fluid Coupling. ACM Trans. Graph. 26, 3, Article 100 (2007).
[11]
Haimasree Bhattacharya, Yue Gao, and Adam W. Bargteil. 2015. A Level-Set Method for Skinning Animated Particle Data. IEEE Transactions on Visualization and Computer Graphics 21, 3 (mar 2015), 315--327.
[12]
Robert Bridson. 2015. Fluid Simulation for Computer Graphics. A K Peters/CRC Press.
[13]
Robert Bridson and Matthias Müller. 2007. Fluid Simulation: SIGGRAPH 2007 Course. In ACM SIGGRAPH 2007 Courses (San Diego, California) (SIGGRAPH '07). Association for Computing Machinery, New York, NY, USA, 1--81.
[14]
W Briggs, V Henson, and S Mccormick. 2000. A Multigrid Tutorial, Second Edition. Society for Industrial and Applied Mathematics.
[15]
Oliver Bröker, Marcus J. Grote, Carsten Mayer, and Arnold Reusken. 2001. Robust Parallel Smoothing for Multigrid Via Sparse Approximate Inverses. SIAM Journal on Scientific Computing 23, 4 (2001), 1396--1417.
[16]
Mingchao Cai, Andy Nonaka, John B. Bell, Boyce E. Griffith, and Aleksandar Donev. 2014. Efficient Variable-Coefficient Finite-Volume Stokes Solvers. Communications in Computational Physics 16, 5 (2014), 1263--1297.
[17]
Jiong Chen, Florian Schäfer, Jin Huang, and Mathieu Desbrun. 2021. Multiscale Cholesky Preconditioning for Ill-Conditioned Problems. ACM Trans. Graph. 40, 4, Article 81 (jul 2021), 13 pages.
[18]
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 (San Diego, California) (SCA '07). 219--228.
[19]
Nuttapong Chentanez and Matthias Müller. 2012. A Multigrid Fluid Pressure Solver Handling Separating Solid Boundary Conditions. IEEE Transactions on Visualization and Computer Graphics 18, 8 (2012), 1191--1201.
[20]
D. Demidov. 2019. AMGCL: An Efficient, Flexible, and Extensible Algebraic Multigrid Implementation. Lobachevskii Journal of Mathematics 40, 5 (01 May 2019), 535--546.
[21]
Christian Dick, Marcus Rogowsky, and Rüdiger Westermann. 2016. Solving the Fluid Pressure Poisson Equation Using Multigrid--Evaluation and Improvements. Visualization and Computer Graphics, IEEE Transactions on (2016).
[22]
Zdenek Dostal and Joachim Schoberl. 2005. Minimizing Quadratic Functions Subject to Bound Constraints with the Rate of Convergence and Finite Termination. Computational Optimization and Applications 30, 1 (2005), 23--43.
[23]
Zdenek Dostl. 2009. Optimal Quadratic Programming Algorithms: With Applications to Variational Inequalities (1st ed.). Springer Publishing Company, Incorporated.
[24]
Kenny Erleben. 2013. Numerical Methods for Linear Complementarity Problems in Physics-based Animation. In ACM SIGGRAPH 2013 Courses. Article 8, 42 pages.
[25]
Michael Ferris and Todd Munson. 2000. Complementarity Problems in GAMS and the Path Solver. Journal of Economic Dynamics and Control 24 (2000), 165--188.
[26]
F. Ferstl, R. Westermann, and C. Dick. 2014. Large-Scale Liquid Simulation on Adaptive Hexahedral Grids. Visualization and Computer Graphics, IEEE Transactions on 20, 10 (2014), 1405--1417.
[27]
Dan Gerszewski and Adam W. Bargteil. 2013. Physics-based Animation of Large-scale Splashing Liquids. ACM Transactions on Graphics 32, 6, Article 185 (2013), 6 pages.
[28]
Marcus J Grote and Thomas Huckle. 1997. Parallel preconditioning with sparse approximate inverses. SIAM Journal on Scientific Computing 18, 3 (1997), 838--853.
[29]
Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
[30]
T. Inglis, M.-L. Eckert, J. Gregson, and N. Thuerey. 2017. Primal-Dual Optimization for Fluids. Computer Graphics Forum 36, 8 (2017), 354--368.
[31]
Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded Biharmonic Weights for Real-Time Deformation. ACM Trans. Graph. 30, 4, Article 78 (jul 2011), 8 pages.
[32]
Doug L.James and Christopher D. Twigg. 2005. Skinning Mesh Animations. ACM Trans. Graph. 24, 3 (jul 2005), 399--407.
[33]
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 (2015), 51:1--51:10 pages.
[34]
Dilip Krishnan, Raanan Fattal, and Richard Szeliski. 2013. Efficient Preconditioning of Laplacian Matrices for Computer Graphics. ACM Trans. Graph. 32, 4, Article 142 (jul 2013), 15 pages.
[35]
J. Kružík, D. Horák, M. Čermák, L. Pospíšil, and M. Pecha. 2020. Active set expansion strategies in MPRGP algorithm. Advances in Engineering Software 149 (2020), 102895.
[36]
Junyu Lai, Yangang Chen, Yu Gu, Christopher Batty, and Justin W.L. Wan. 2020. Fast and Scalable Solvers for the Fluid Pressure Equations with Separating Solid Boundary Conditions. Computer Graphics Forum 39, 2 (2020), 23--33.
[37]
Steve Lesser, Alexey Stomakhin, Gilles Daviet, Joel Wretborn, John Edholm, Noh-Hoon Lee, Eston Schweickart, Xiao Zhai, Sean Flynn, and Andrew Moffat. 2022. Loki: A Unified Multiphysics Simulation Framework for Production. ACM Trans. Graph. 41, 4, Article 50 (jul 2022), 20 pages.
[38]
Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection-and Inversion-Free, Large-Deformation Dynamics. ACM Trans. Graph. 39, 4, Article 49 (July 2020), 20 pages.
[39]
Yifei Li, Tao Du, Sangeetha Grama Srinivasan, Kui Wu, Bo Zhu, Eftychios Sifakis, and Wojciech Matusik. 2022. Fluidic Topology Optimization with an Anisotropic Mixture Model. ACM Trans. Graph., Article 239 (nov 2022), 14 pages.
[40]
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.
[41]
Jinyuan Liu, Zangyueyang Xian, Yuqing Zhou, Tsuyoshi Nomura, Ercan M. Dede, and Bo Zhu. 2022. A Marker-and-Cell Method for Large-Scale Flow-Based Topology Optimization on GPU. Struct. Multidiscip. Optim. 65, 4 (apr 2022), 18 pages.
[42]
A. McAdams, E. Sifakis, and J. 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. 65--74.
[43]
Rahul Narain, Abhinav Golas, and Ming C. Lin. 2010. Free-flowing Granular Materials with Two-way Solid Coupling. ACM Transactions on Graphics 29, 6, Article 173 (2010), 10 pages.
[44]
Maxim Naumov. 2011. Parallel Solution of Sparse Triangular Linear Systems in the Preconditioned Iterative Methods on the GPU.
[45]
Maxim Naumov. 2012. Parallel Incomplete-LU and Cholesky Factorization in the Preconditioned Iterative Methods on the GPU.
[46]
Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (second ed.). Springer, New York, NY, USA.
[47]
Yousef Saad. 2003. Iterative Methods for Sparse Linear Systems. Notes 3, 2nd Edition (2003), xviii+528. arXiv:0806.3802
[48]
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.
[49]
Han Shao, Libo Huang, and Dominik L. Michels. 2022. A Fast Unsmoothed Aggregation Algebraic Multigrid Framework for the Large-Scale Simulation of Incompressible Flow. ACM Trans. Graph. 41, 4, Article 49 (jul 2022), 18 pages.
[50]
Jonathan Richard Shewchuk. 1994. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. (August 1994).
[51]
K. Stüben. 2001. A Review of Algebraic Multigrid. J. Comput. Appl. Math. 128, 1--2 (mar 2001), 281--309.
[52]
Tetsuya Takahashi and Christopher Batty. 2021. FrictionalMonolith: A Monolithic Optimization-based Approach for Granular Flow with Contact-Aware Rigid-Body Coupling. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1--16.
[53]
Tetsuya Takahashi and Christopher Batty. 2022. ElastoMonolith: A Monolithic Optimization-Based Liquid Solver for Contact-Aware Elastic-Solid Coupling. ACM Trans. Graph. 41, 6, Article 255 (nov 2022), 19 pages.
[54]
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.
[55]
Rasmus Tamstorf, Toby Jones, and Stephen F. McCormick. 2015. Smoothed Aggregation Multigrid for Cloth Simulation. ACM Trans. Graph. 34, 6, Article 245 (2015), 13 pages.
[56]
Osamu Tatebe. 1993. The multigrid preconditioned conjugate gradient method. In Proceedings of the Sixth Copper Mountain Conference on Multigrid Methods (1993). 621--634.
[57]
Ulrich Trottenberg, Cornelius W. Oosterlee, and Anton Schuller. 2000. Multigrid. Academic press. Petr Vanek, Jan Mandel, and Marian Brezina. 1996. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56 (1996), 179--196.
[58]
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.
[59]
Daniel Weber, Johannes Mueller-Roemer, Andre Stork, and Dieter Fellner. 2015. A Cut-Cell Geometric Multigrid Poisson Solver for Fluid Simulation. Computer Graphics Forum 34, 2 (2015), 481--491.
[60]
Botao Wu, Zhendong Wang, and Huamin Wang. 2022. A GPU-Based Multilevel Additive Schwarz Preconditioner for Cloth and Deformable Body Simulation. ACM Trans. Graph. 41, 4, Article 63 (jul 2022), 14 pages.
[61]
Xiang Yang and Rajat Mittal. 2017. Efficient relaxed-Jacobi smoothers for multigrid on parallel computers. J. Comput. Phys. 332 (2017), 135--142.
[62]
Xinxin Zhang. 2015. tbb_liquid_amgpcg. https://github.com/zhxx1987/tbb_liquid_amgpcg
[63]
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 (2010), 18 pages.
Recommendations
Interlinked SPH Pressure Solvers for Strong Fluid-Rigid Coupling
We present a strong fluid-rigid coupling for Smoothed Particle Hydrodynamics (SPH) fluids and rigid bodies with particle-sampled surfaces. The approach interlinks the iterative pressure update at fluid particles with a second SPH solver that computes ...
A Multigrid Fluid Pressure Solver Handling Separating Solid Boundary Conditions
We present a multigrid method for solving the linear complementarity problem (LCP) resulting from discretizing the Poisson equation subject to separating solid boundary conditions in an Eulerian liquid simulation's pressure projection step. The method ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 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 the author(s) 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: 24 August 2023
Published in PACMCGIT Volume 6, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 78Total Downloads
- Downloads (Last 12 months)56
- Downloads (Last 6 weeks)5
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in