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.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
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, 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].
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
Record Number:CaltechAUTHORS:20210809-193100494
Persistent URL:
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.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110174
Deposited By: Tony Diaz
Deposited On:09 Aug 2021 20:08
Last Modified:09 Aug 2021 20:08

Repository Staff Only: item control page