Chordal Decomposition for Spectral Coarsening

Abstract

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.

arXiv comment16 pages, 28 figures

References in corpus (4)

• Fast ADMM for Semidefinite Programs with Chordal Sparsity
• A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening
• A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming
• Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization

Cited by in corpus (1)

• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization