CaltechAUTHORS
  A Caltech Library Service

Multiscale cholesky preconditioning for ill-conditioned problems

Chen, Jiong and Schäfer, Florian and Huang, Jin and Desbrun, Mathieu (2021) Multiscale cholesky preconditioning for ill-conditioned problems. ACM Transactions on Graphics, 40 (4). Art. No. 81. ISSN 0730-0301. doi:10.1145/3450626.3459851. https://resolver.caltech.edu/CaltechAUTHORS:20210809-193100494

[img] PDF - Published Version
See Usage Policy.

29MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210809-193100494

Abstract

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3450626.3459851DOIArticle
ORCID:
AuthorORCID
Desbrun, Mathieu0000-0003-3424-6079
Additional Information:© 2021 Association for Computing Machinery. Published: 19 July 2021. The authors wish to thank Houman Owhadi for supporting this project from its onset, and Rasmus Tamstorf for early discussions. Partial funding for JC and JH was provided by National Key R&D Program of China (No. 2020AAA0108901) and NSFC (No. 61732016). FS was partially supported by AFOSR grant FA9550-18-1-0271 and ONR grant N00014-18-1-2363. MD gratefully thanks the GeoViC team for their hospitality, and acknowledges additional funding from Inria. Images of Fig. 10 are courtesy of pixabay.com, the Armadillo model from Fig. 9 is courtesy of Stanford University, the hand model from Fig. 7 is courtesy of AIM@SHAPE, while the bird model from Fig. 8 is courtesy of the authors of [Liu et al. 2018].
Funders:
Funding AgencyGrant Number
National Key Research and Development Program of China2020AAA0108901
National Natural Science Foundation of China61732016
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0271
Office of Naval Research (ONR)N00014-18-1-2363
Subject Keywords:Numerical solvers, preconditioned conjugate gradient, incomplete Cholesky decomposition, wavelets
Issue or Number:4
DOI:10.1145/3450626.3459851
Record Number:CaltechAUTHORS:20210809-193100494
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210809-193100494
Official Citation: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 (August 2021), 13 pages. https://doi.org/10.1145/3450626.3459851
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110174
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:09 Aug 2021 20:08
Last Modified:09 Aug 2021 20:08

Repository Staff Only: item control page