An Efficient Geometric Multigrid Solver for Viscous Liquids
An Efficient Geometric Multigrid Solver for Viscous Liquids
复制标题
DOI：
10.1145/3340255
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Mridul Aanjaneya;Chengguizi Han;Ryan Goldade;Christopher Batty
中科院分区：
文献类型：
--
作者：
Mridul Aanjaneya;Chengguizi Han;Ryan Goldade;Christopher Batty
我们基于 Batty 和 Bridson [2008] 的变分方法提出了一种用于模拟粘性液体的高效几何多重网格求解器。尽管粘度控制方程是椭圆形的，但离散模板中不同速度分量之间的强耦合要求使用更奇特的平滑技术来实现教科书上的多重网格效率。我们的主要贡献是设计了一种新颖的盒平滑器，涉及小型稀疏系统（2D 中最多 9 x 9，3D 中最多 15 x 15），与简单的多重网格方法相比，它具有出色的收敛速度和 3.5 倍 - 13.8 倍的性能改进。我们采用混合方法，仅在更平滑的盒子内部使用直接求解器，并保持其余管道免组装，使我们的求解器能够有效地容纳超过 1.94 亿个自由度，同时占用小于 16 GB 的内存占用。为了减少使用框平滑器的计算开销，我们预先计算所有内部自由度的子域系统矩阵的 Cholesky 分解。我们描述了变分公式如何自然地适应多重网格层次结构，以正确执行边界条件，该公式需要在单元、边缘和面的中心计算体积权重。我们提出的多重网格求解器可作为共轭梯度的出色预处理器，其性能优于现有的最先进的替代方案。我们在粘性液体运动的几个高分辨率示例（包括与刚体的双向耦合相互作用）上证明了我们的方法的有效性。
We present an efficient geometric Multigrid solver for simulating viscous liquids based on the variational approach of Batty and Bridson [2008]. Although the governing equations for viscosity are elliptic, the strong coupling between different velocity components in the discrete stencils mandates the use of more exotic smoothing techniques to achieve textbook Multigrid efficiency. Our key contribution is the design of a novel box smoother involving small and sparse systems (at most 9 x 9 in 2D and 15 x 15 in 3D), which yields excellent convergence rates and performance improvements of 3.5x - 13.8x over a naïve Multigrid approach. We employ a hybrid approach by using a direct solver only inside the box smoother and keeping the remaining pipeline assembly-free, allowing our solver to efficiently accommodate more than 194 million degrees of freedom, while occupying a memory footprint of less than 16 GB. To reduce the computational overhead of using the box smoother, we precompute the Cholesky factorization of the subdomain system matrix for all interior degrees of freedom. We describe how the variational formulation, which requires volume weights computed at the centers of cells, edges, and faces, can be naturally accommodated in the Multigrid hierarchy to properly enforce boundary conditions. Our proposed Multigrid solver serves as an excellent preconditioner for Conjugate Gradients, outperforming existing state-of-the-art alternatives. We demonstrate the efficacy of our method on several high resolution examples of viscous liquid motion including two-way coupled interactions with rigid bodies.