“Multiscale cholesky preconditioning for ill-conditioned problems” by Chen, Schäfer, Huang and 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.

1. Raymond Alcouffe, Achi Brandt, Joel Dendy, Jr., and James W. Painter. 1981. The Multi-Grid Method for the Diffusion Equation with Strongly Discontinuous Coefficients. SIAM J. Sci. Stat. Comput. 2, 4 (1981), 430–454.Google ScholarDigital Library
2. Patrick R Amestoy, Timothy A Davis, and Iain S Duff. 1996. An approximate minimum degree ordering algorithm. SIAM J. Matrix Analysis and Applications 17, 4 (1996), 886–905.Google ScholarDigital Library
3. Achi Brandt, James Brannick, Karsten Kahl, and Irene Livshits. 2011. Bootstrap AMG. SIAM J. Sci. Comput. 33, 2 (2011), 612–632.Google ScholarDigital Library
4. Max Budninskiy, Houman Owhadi, and Mathieu Desbrun. 2019. Operator-adapted wavelets for finite-element differential forms. J. Comput. Phys. 388 (2019), 144–177.Google ScholarDigital Library
5. Desai Chen, David IW Levin, Wojciech Matusik, and Danny M Kaufman. 2017. Dynamics-aware numerical coarsening for fabrication design. ACM Trans. Graph. 36, 4, Article 84 (2017).Google ScholarDigital Library
6. Jiong Chen, Hujun Bao, Tianyu Wang, Mathieu Desbrun, and Jin Huang. 2018. Numerical Coarsening Using Discontinuous Shape Functions. ACM Trans. Graph. 37, 4, Article 120 (July 2018).Google ScholarDigital Library
7. Jiong Chen, Max Budninskiy, Houman Owhadi, Hujun Bao, Jin Huang, and Mathieu Desbrun. 2019. Material-adapted refinable basis functions for elasticity simulation. ACM Trans. Graph. 38, 6 (2019), 161.Google ScholarDigital Library
8. Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. Math. Software 35, 3 (2008), 1–14.Google ScholarDigital Library
9. Timothy A Davis. 2006. Direct methods for sparse linear systems. SIAM.Google Scholar
10. Timothy A. Davis and William W. Hager. 2009. Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves. ACM Trans. Math. Softw. 35, 4, Article 27 (2009).Google ScholarDigital Library
11. Denis Demidov. 2019. AMGCL: An efficient, flexible, and extensible algebraic multigrid implementation. Lobachevskii Journal of Mathematics 40, 5 (2019), 535–546.Google ScholarCross Ref
12. Zeev Farbman, Raanan Fattal, Dani Lischinski, and Richard Szeliski. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Trans. Graph. 27, 3 (2008), 1–10.Google ScholarDigital Library
13. Raanan Fattal. 2009. Edge-Avoiding Wavelets and Their Applications. In ACM SIGGRAPH Proceedings. Article 22.Google Scholar
14. Miroslav Fiedler and Vlastimil Pták. 1962. On matrices with non-positive off-diagonal elements and positive principal minors. Czechoslovak Mathematical Journal 12, 3 (1962), 382–400.Google ScholarCross Ref
15. D Gines, G Beylkin, and J Dunn. 1998. LU factorization of non-standard forms and direct multiresolution solvers. Applied and Computational Harmonic Analysis 5, 2 (1998), 156–201.Google ScholarCross Ref
16. Marcus J. Grote and Thomas Huckle. 1997. Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput. 18, 3 (1997), 838–853.Google ScholarDigital Library
17. Joseph Guinness. 2018. Permutation and grouping methods for sharpening Gaussian process approximations. Technometrics 60, 4 (2018), 415–429.Google ScholarCross Ref
18. Philipp Herholz and Marc Alexa. 2018. Factor once: reusing cholesky factorizations on sub-meshes. ACM Trans. Graph. 37, 6 (2018), 1–9.Google ScholarDigital Library
19. Philipp Herholz, Timothy A Davis, and Marc Alexa. 2017. Localized solutions of sparse linear systems for geometry processing. ACM Trans. Graph. 36, 6 (2017), 1–8.Google ScholarDigital Library
20. Philipp Herholz and Olga Sorkine-Hornung. 2020. Sparse Cholesky Updates for Interactive Mesh Parameterization. ACM Trans. Graph. 39, 6, Article 202 (2020).Google ScholarDigital Library
21. Lily Kharevych, Patrick Mullen, Houman Owhadi, and Mathieu Desbrun. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Trans. Graph. 28, 3, Article 51 (2009).Google ScholarDigital Library
22. Ralf Kornhuber, Daniel Peterseim, and Harry Yserentant. 2018. An analysis of a class of variational multiscale methods based on subspace decomposition. Math. Comp. 87, 314 (2018), 2765–2774.Google ScholarCross Ref
23. Dilip Krishnan, Raanan Fattal, and Richard Szeliski. 2013. Efficient preconditioning of Laplacian matrices for computer graphics. ACM Trans. Graph. 32, 4 (2013), 142.Google ScholarDigital Library
24. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive Parameterizations. ACM Trans. Graph. 37, 4, Article 41 (2018).Google ScholarDigital Library
25. Axel Målqvist and Daniel Peterseim. 2014. Localization of elliptic multiscale problems. Math. Comp. 83, 290 (2014), 2583–2603.Google ScholarCross Ref
26. J. Andvandervorst Meijerink and Henk A. van der Vorst. 1977. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Mathematics of computation 31, 137 (1977), 148–162.Google Scholar
27. Maxim Naumov. 2012. Parallel Incomplete-LU and Cholesky Factorization in the Preconditioned Iterative Methods on the GPU. Technical Report. NVIDIA.Google Scholar
28. Matthieu Nesme, Paul G Kry, Lenka Jeřábková, and François Faure. 2009. Preserving topology and elasticity for embedded deformable models. ACM Trans. Graph. 28, 3, Article 52 (2009).Google ScholarDigital Library
29. Houman Owhadi. 2017. Multigrid with rough coefficients and multiresolution operator decomposition from hierarchical information games. SIAM Rev. 59, 1 (2017), 99–149.Google ScholarDigital Library
30. Houman Owhadi and Clint Scovel. 2019. Operator-Adapted Wavelets, Fast Solvers, and Numerical Homogenization: From a Game Theoretic Approach to Numerical Approximation and Algorithm Design. Vol. 35. Cambridge University Press.Google Scholar
31. Sylvain Paris, Samuel W. Hasinoff, and Jan Kautz. 2015. Local Laplacian Filters: Edge-Aware Image Processing with a Laplacian Pyramid. Commun. ACM 58, 3 (2015), 81–91.Google ScholarDigital Library
32. Pietro Perona and Jitendra Malik. 1990. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12, 7 (1990), 629–639.Google ScholarDigital Library
33. Florian Schäfer, Matthias Katzfuss, and Houman Owhadi. 2020. Sparse Cholesky factorization by Kullback-Leibler minimization. arXiv preprint arXiv:2004.14455 (2020).Google Scholar
34. Florian Schäfer, T. J. Sullivan, and Houman Owhadi. 2021. Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity. Multiscale Modeling & Simulation 19, 2 (2021), 688–730.Google ScholarDigital Library
35. Johann Schröder, Ulrich Trottenberg, and Kristian Witsch. 1978. On fast Poisson solvers and applications. In Numerical Treatment of Differential Equations. Springer, 153–187.Google Scholar
36. Jennifer Scott and Miroslav Tůma. 2014a. HSL_MI28: An efficient and robust limited-memory incomplete Cholesky factorization code. ACM Trans. Math. Software 40, 4 (2014), 1–19.Google ScholarDigital Library
37. Jennifer Scott and Miroslav Tůma. 2014b. On positive semidefinite modification schemes for incomplete Cholesky factorization. SIAM J. Sci. Comput. 36, 2 (2014), A609–A633.Google ScholarDigital Library
38. Jennifer Scott and Miroslav Tůma. 2014c. On signed incomplete Cholesky factorization preconditioners for saddle-point systems. SIAM J. Sci. Comput. 36, 6 (2014), A2984–A3010.Google ScholarDigital Library
39. Klaus Stüben. 2000. Algebraic Multigrid (AMG): an Introduction with Applications. Multigrid (2000).Google Scholar
40. Raghunathan Sudarshan. 2005. Operator-adapted Finite Element Wavelets: theory and applications to a posteriori error estimation and adaptive computational modeling. Ph.D. Dissertation. MIT, Department of Civil and Environmental Engineering.Google Scholar
41. Rasmus Tamstorf, Toby Jones, and Stephen F. McCormick. 2015. Smoothed Aggregation Multigrid for Cloth Simulation. ACM Trans. Graph. 34, 6, Article 245 (2015).Google ScholarDigital Library
42. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust Quasistatic Finite Elements and Flesh Simulation. Symp. on Comp. Anim. (2005), 181–190.Google Scholar
43. Rosell Torres, Jose M. Espadero, Felipe A. Calvo, and Miguel A. Otaduy. 2014. Interactive Deformation of Heterogeneous Volume Data. Lecture Notes in Computer Science 8789 (2014).Google Scholar
44. Trilinos. 2020. The Trilinos Project Website. https://trilinos.github.ioGoogle Scholar
45. Petr Vaněk, Jan Mandel, and Marian Brezina. 1996. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 3 (1996), 179–196.Google ScholarCross Ref
46. Irad Yavneh. 2006. Why Multigrid Methods Are So Efficient. Computing in Science Engineering 8, 6 (2006), 12–22.Google ScholarDigital Library
47. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2 (2010), 1–18.Google ScholarDigital Library