.png){kind=icon}
返回
Multiscale Cholesky Preconditioning for Ill-conditioned Problems
.png){kind=icon}
OA
AI
DOI：10.1145/3450626.3459851.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Numerical solvers
preconditioned conjugate gradient
incomplete Cholesky decomposition
wavelets
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
9.5
论文数:
4.7K
被引数:
3.6W
机构
引用论文
Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games.png)
SIAM REVIEWOAAI
SIAM REVIEWIF6.1
OAAI分享收藏Tuning the electronic and optical properties of BaNiO3 via Fe substitution: a first-principles study
PREAI
分享收藏Generation of Human iPSC-derived Neural Progenitor Cells (NPCs) as Drug Discovery Model for Neurological and Mitochondrial DisordersBIO-PROTOCOL
OAAI
BIO-PROTOCOLIF0
OAAI分享收藏
查看更多内容