Multiscale cholesky preconditioning for ill-conditioned problems
Multiscale cholesky preconditioning for ill-conditioned problems
复制标题
针对病态问题的多尺度胆囊预处理
DOI：
--
复制
发表时间：
2021
影响因子：
6.2
通讯作者：
M. Desbrun
中科院分区：
文献类型：
--
作者：
Jiong Chen;Florian Schäfer;Jin Huang;M. Desbrun
许多计算机图形应用可归结为求解线性方程组的稀疏系统。虽然各种专业库中以及针对不同计算机架构的现有数值求解器工具集通常能为图像处理、建模和模拟应用提供高效且可扩展的解决方案，但越来越多的图形问题面临大规模且病态的稀疏线性系统——这是一个数值难题，它通常会使直接分解（由于高内存需求）和迭代求解器（由于收敛缓慢）都陷入困境。我们提出了一种对此类问题进行高效预处理的新方法，这类问题通常源于对具有非均匀和各向异性系数的偏微分方程在非结构化网格上的离散化。我们的数值方法包括简单地对自由度进行从细到粗的排序以及多尺度稀疏模式，利用这些我们应用不完全乔列斯基分解。通过进一步利用超节点实现缓存一致性、利用图着色提高并行性以及利用部分对角移位来纠正负主元，我们得到了一个预处理器，将其与共轭梯度求解器相结合，在处理涉及不良网格元素和/或高系数对比度的图形问题时，其性能远远超过现有的精心设计的库。我们还通过将数值均匀化中使用的算子自适应小波的最新方法与矩阵的传统乔列斯基分解相联系的理论基础来支持我们简单求解器背后的核心概念，为我们在不完全乔列斯基分解和多尺度分析之间提供了一个我们在数值上加以利用的清晰桥梁。
Many computer graphics applications boil down to solving sparse systems of linear equations. While the current arsenal of numerical solvers available in various specialized libraries and for different computer architectures often allow efficient and scalable solutions to image processing, modeling and simulation applications, an increasing number of graphics problems face large-scale and ill-conditioned sparse linear systems --- a numerical challenge which typically chokes both direct factorizations (due to high memory requirements) and iterative solvers (because of slow convergence). We propose a novel approach to the efficient preconditioning of such problems which often emerge from the discretization over unstructured meshes of partial differential equations with heterogeneous and anisotropic coefficients. Our numerical approach consists in simply performing a fine-to-coarse ordering and a multiscale sparsity pattern of the degrees of freedom, using which we apply an incomplete Cholesky factorization. By further leveraging supernodes for cache coherence, graph coloring to improve parallelism and partial diagonal shifting to remedy negative pivots, we obtain a preconditioner which, combined with a conjugate gradient solver, far exceeds the performance of existing carefully-engineered libraries for graphics problems involving bad mesh elements and/or high contrast of coefficients. We also back the core concepts behind our simple solver with theoretical foundations linking the recent method of operator-adapted wavelets used in numerical homogenization to the traditional Cholesky factorization of a matrix, providing us with a clear bridge between incomplete Cholesky factorization and multiscale analysis that we leverage numerically.