Chordal Decomposition for Spectral Coarsening SIGGRAPH Asia 2020

Honglin Chen, University of Toronto
Hsueh-Ti Derek Liu, University of Toronto
Alec Jacobson, University of Toronto
David I.W. Levin, University of Toronto


We introduce a novel solver to significantly reduce the size of a geometric operator while preserving its spectral properties at the lowest frequencies. We use chordal decomposition to formulate a convex optimization problem which allows the user to control the operator sparsity pattern. This allows for a trade-off between the spectral accuracy of the operator and the cost of its application. We efficiently minimize the energy with a change of variables and achieve state-of-the-art results on spectral coarsening. Our solver further enables novel applications including volume-to-surface approximation and detaching the operator from the mesh, i.e., one can produce a mesh tailormade for visualization and optimize an operator separately for computation.



  title = {Chordal Decomposition for Spectral Coarsening},
  author = {Honglin Chen and Hsueh-Ti Derek Liu and Alec Jacobson and David I.W. Levin},
  year = {2020},
  issue_date = {December 2020}, 
  publisher = {Association for Computing Machinery}, 
  volume = {39}, 
  number = {6}, 
  issn = {0730-0301},
  journal = {ACM Trans. Graph.}, 


This work is funded in part by NSERC Discovery (RGPIN–2017–05524, RGPIN2017–05235, RGPAS–2017–507938), Connaught Fund (503114), CFI-JELF Fund, Accelerator (RGPAS–2017–507909), New Frontiers of Research Fund (NFRFE–201), the Ontario Early Research Award program, the Canada Research Chairs Program, the Fields Centre for Quantitative Analysis and Modelling and gifts by Adobe Systems, Autodesk and MESH Inc. We especially thank Yifan Sun, Giovanni Fantuzzi and Yang Zheng for their enlightening discussions and advice about the chordal decomposition, and Thibault Lescoat for sharing the spectral simplification implementation and discussions about running experiments. We thank Abhishek Madan, Silvia Sellán, Michael Xu, Sarah Kushner, Rinat Abdrashitov, Hengguang Zhou and Kaihua Tang for proofreading; Mirela Ben-Chen for insightful discussions about the weighted functional map; Josh Holinaty for testing the code; John Hancock for the IT support; anonymous reviewers for their helpful comments and suggestions.