{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:20:31Z","timestamp":1764937231929,"version":"3.41.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T00:00:00Z","timestamp":1606435200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"the Ontario Early Research Award program"},{"DOI":"10.13039\/100004675","name":"Autodesk","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004675","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007224","name":"Connaught Fund","doi-asserted-by":"crossref","award":["503114"],"award-info":[{"award-number":["503114"]}],"id":[{"id":"10.13039\/501100007224","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001804","name":"the Canada Research Chairs Program","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MESH Inc"},{"name":"Accelerator","award":["RGPAS-2017-507909"],"award-info":[{"award-number":["RGPAS-2017-507909"]}]},{"name":"NSERC Discovery","award":["RGPIN2017?05235, RGPAS?2017?507938, RGPIN-2017-05524"],"award-info":[{"award-number":["RGPIN2017?05235, RGPAS?2017?507938, RGPIN-2017-05524"]}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]},{"name":"New Frontiers of Research Fund","award":["NFRFE?201"],"award-info":[{"award-number":["NFRFE?201"]}]},{"name":"CFI-JELF Fund"},{"name":"the Fields Centre for Quantitative Analysis and Modelling"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>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 tailor-made for visualization and optimize an operator separately for computation.<\/jats:p>","DOI":"10.1145\/3414685.3417789","type":"journal-article","created":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T21:51:05Z","timestamp":1606513865000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Chordal decomposition for spectral coarsening"],"prefix":"10.1145","volume":"39","author":[{"given":"Honglin","family":"Chen","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}]},{"given":"Hsueh-TI Derek","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}]},{"given":"Alec","family":"Jacobson","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}]},{"given":"David I. W.","family":"Levin","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}]}],"member":"320","published-online":{"date-parts":[[2020,11,27]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Positive semidefinite matrices with a given sparsity pattern. Linear algebra and its applications 107","author":"Agler Jim","year":"1988","unstructured":"Jim Agler , William Helton , Scott McCullough , and Leiba Rodman . 1988. Positive semidefinite matrices with a given sparsity pattern. Linear algebra and its applications 107 ( 1988 ), 101--149. Jim Agler, William Helton, Scott McCullough, and Leiba Rodman. 1988. Positive semidefinite matrices with a given sparsity pattern. Linear algebra and its applications 107 (1988), 101--149."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0016-2"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Jean RS Blair and Barry Peyton. 1993. An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation. 1--29.  Jean RS Blair and Barry Peyton. 1993. An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation. 1--29.","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"e_1_2_2_5_1","unstructured":"Gecia Bravo-Hermsdorff and Lee Gunderson. 2019. A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening. In Advances in Neural Information Processing Systems 32. 7736--7747.  Gecia Bravo-Hermsdorff and Lee Gunderson. 2019. A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening. In Advances in Neural Information Processing Systems 32. 7736--7747."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2019.02.018"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S105262340240851X"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073669"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766889"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201386"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356567"},{"volume-title":"Proceedings of the 18th annual ACM SIGGRAPH\/Eurographics Symposium on Computer Animation, SCA 2019. 5:1--5:13","author":"Edwin Chen Yu Ju","key":"e_1_2_2_12_1","unstructured":"Yu Ju Edwin Chen , David I. W. Levin , Danny Kaufmann , Uri M. Ascher , and Dinesh K. Pai . 2019b. EigenFit for consistent elastodynamic simulation across mesh resolution . In Proceedings of the 18th annual ACM SIGGRAPH\/Eurographics Symposium on Computer Animation, SCA 2019. 5:1--5:13 . Yu Ju Edwin Chen, David I. W. Levin, Danny Kaufmann, Uri M. Ascher, and Dinesh K. Pai. 2019b. EigenFit for consistent elastodynamic simulation across mesh resolution. In Proceedings of the 18th annual ACM SIGGRAPH\/Eurographics Symposium on Computer Animation, SCA 2019. 5:1--5:13."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(97)00082-4"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195903001074"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015817"},{"key":"e_1_2_2_16_1","unstructured":"Katsuki Fujisawa Sunyoung Kim Masakazu Kojima Yoshio Okamoto and Makoto Yamashita. 2009. B-453 User's Manual for SparseCoLO: Conversion Methods for SPARSE COnic-form Linear Optimization Problems. (2009).  Katsuki Fujisawa Sunyoung Kim Masakazu Kojima Yoshio Okamoto and Makoto Yamashita. 2009. B-453 User's Manual for SparseCoLO: Conversion Methods for SPARSE COnic-form Linear Optimization Problems. (2009)."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366218"},{"volume-title":"Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1997. 209--216","author":"Garland Michael","key":"e_1_2_2_18_1","unstructured":"Michael Garland and Paul S. Heckbert . 1997. Surface simplification using quadric error metrics . In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1997. 209--216 . Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1997. 209--216."},{"key":"e_1_2_2_19_1","volume-title":"Heckbert","author":"Garland Michael","year":"1998","unstructured":"Michael Garland and Paul S . Heckbert . 1998 . Simplifying surfaces with color and texture using quadric error metrics. In Visualization '98, Proceedings . 263--269. Michael Garland and Paul S. Heckbert. 1998. Simplifying surfaces with color and texture using quadric error metrics. In Visualization '98, Proceedings. 263--269."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Michael Grant and Stephen Boyd. 2008. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control. 95--110.  Michael Grant and Stephen Boyd. 2008. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control. 95--110.","DOI":"10.1007\/978-1-84800-155-8_7"},{"key":"e_1_2_2_21_1","volume-title":"CVX: Matlab Software for Disciplined Convex Programming, version 2.1.","author":"Grant Michael","year":"2014","unstructured":"Michael Grant and Stephen Boyd . 2014 . CVX: Matlab Software for Disciplined Convex Programming, version 2.1. Michael Grant and Stephen Boyd. 2014. CVX: Matlab Software for Disciplined Convex Programming, version 2.1."},{"key":"e_1_2_2_22_1","volume-title":"Positive definite completions of partial Hermitian matrices. Linear algebra and its applications 58","author":"Grone Robert","year":"1984","unstructured":"Robert Grone , Charles R Johnson , Eduardo M S\u00e1 , and Henry Wolkowicz . 1984. Positive definite completions of partial Hermitian matrices. Linear algebra and its applications 58 ( 1984 ), 109--124. Robert Grone, Charles R Johnson, Eduardo M S\u00e1, and Henry Wolkowicz. 1984. Positive definite completions of partial Hermitian matrices. Linear algebra and its applications 58 (1984), 109--124."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.003"},{"key":"e_1_2_2_24_1","volume-title":"Progressive Meshes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1996. 99--108","author":"Hoppe Hugues","year":"1996","unstructured":"Hugues Hoppe . 1996 . Progressive Meshes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1996. 99--108 . Hugues Hoppe. 1996. Progressive Meshes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1996. 99--108."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258843"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/166117.166119"},{"key":"e_1_2_2_27_1","unstructured":"Alec Jacobson et al. 2018. gptoolbox: Geometry Processing Toolbox. http:\/\/github.com\/alecjacobson\/gptoolbox.  Alec Jacobson et al. 2018. gptoolbox: Geometry Processing Toolbox. http:\/\/github.com\/alecjacobson\/gptoolbox."},{"volume-title":"Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '99)","author":"Doug","key":"e_1_2_2_28_1","unstructured":"Doug L. James and Dinesh K. Pai. 1999. ArtDefo: Accurate Real Time Deformable Objects . In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '99) . 65--72. Doug L. James and Dinesh K. Pai. 1999. ArtDefo: Accurate Real Time Deformable Objects. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '99). 65--72."},{"key":"e_1_2_2_29_1","volume-title":"Graph Coarsening with Preserved Spectral Properties. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020","volume":"108","author":"Jin Yu","year":"2020","unstructured":"Yu Jin , Andreas Loukas , and Joseph J\u00e1J\u00e1 . 2020 . Graph Coarsening with Preserved Spectral Properties. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020 , Vol. 108 . 4452--4462. Yu Jin, Andreas Loukas, and Joseph J\u00e1J\u00e1. 2020. Graph Coarsening with Preserved Spectral Properties. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, Vol. 108. 4452--4462."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2010.04.012"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531357"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0402-6"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13932"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820612"},{"key":"e_1_2_2_35_1","article-title":"Spectral Coarsening of Geometric Operators","volume":"38","author":"Derek Liu Hsueh-Ti","year":"2019","unstructured":"Hsueh-Ti Derek Liu , Alec Jacobson , and Maks Ovsjanikov . 2019 . Spectral Coarsening of Geometric Operators . ACM Transactions on Graphics (TOG) 38 , 4, Article Article 105 (July 2019), 13 pages. Hsueh-Ti Derek Liu, Alec Jacobson, and Maks Ovsjanikov. 2019. Spectral Coarsening of Geometric Operators. ACM Transactions on Graphics (TOG) 38, 4, Article Article 105 (July 2019), 13 pages.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_36_1","article-title":"Graph Reduction with Spectral and Cut Guarantees","volume":"20","author":"Loukas Andreas","year":"2019","unstructured":"Andreas Loukas . 2019 . Graph Reduction with Spectral and Cut Guarantees . J. Mach. Learn. Res. 20 (2019), 116:1--116:42. Andreas Loukas. 2019. Graph Reduction with Spectral and Cut Guarantees. J. Mach. Learn. Res. 20 (2019), 116:1--116:42.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018","volume":"80","author":"Loukas Andreas","year":"2018","unstructured":"Andreas Loukas and Pierre Vandergheynst . 2018 . Spectrally Approximating Large Graphs with Smaller Graphs . In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 , Vol. 80 . 3243--3252. Andreas Loukas and Pierre Vandergheynst. 2018. Spectrally Approximating Large Graphs with Smaller Graphs. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Vol. 80. 3243--3252."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2978906"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7403152"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925913"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0351-9"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13496"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185526"},{"volume-title":"Special Interest Group on Computer Graphics and Interactive Techniques Conference, SIGGRAPH '17 Courses. 5:1--5:62","author":"Ovsjanikov Maks","key":"e_1_2_2_44_1","unstructured":"Maks Ovsjanikov , Etienne Corman , Michael M. Bronstein , Emanuele Rodol\u00e0 , Mirela Ben-Chen , Leonidas J. Guibas , Fr\u00e9d\u00e9ric Chazal , and Alexander M. Bronstein . 2017. Computing and processing correspondences with functional maps . In Special Interest Group on Computer Graphics and Interactive Techniques Conference, SIGGRAPH '17 Courses. 5:1--5:62 . Maks Ovsjanikov, Etienne Corman, Michael M. Bronstein, Emanuele Rodol\u00e0, Mirela Ben-Chen, Leonidas J. Guibas, Fr\u00e9d\u00e9ric Chazal, and Alexander M. Bronstein. 2017. Computing and processing correspondences with functional maps. In Special Interest Group on Computer Graphics and Interactive Techniques Conference, SIGGRAPH '17 Courses. 5:1--5:62."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1013894"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866190"},{"key":"e_1_2_2_47_1","first-page":"1","article-title":"Partial Functional","volume":"36","author":"Rodol\u00ed E.","year":"2017","unstructured":"E. Rodol\u00ed , L. Cosmo , M. M. Bronstein , A. Torsello , and D. Cremers . 2017 . Partial Functional Correspondence. Comput. Graph. Forum 36 , 1 (Jan. 2017), 222--236. E. Rodol\u00ed, L. Cosmo, M. M. Bronstein, A. Torsello, and D. Cremers. 2017. Partial Functional Correspondence. Comput. Graph. Forum 36, 1 (Jan. 2017), 222--236.","journal-title":"Correspondence. Comput. Graph. Forum"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322979"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629697"},{"key":"e_1_2_2_50_1","volume-title":"Vavasis","author":"Srijuntongsiri Gun","year":"2004","unstructured":"Gun Srijuntongsiri and Stephen A . Vavasis . 2004 . A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming. CoRR ( 2004). Gun Srijuntongsiri and Stephen A. Vavasis. 2004. A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming. CoRR (2004)."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/130926924"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1011020"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1561\/2400000006"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"e_1_2_2_56_1","volume-title":"Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization. CoRR","author":"Zhao Zhiqiang","year":"2018","unstructured":"Zhiqiang Zhao , Yongyu Wang , and Zhuo Feng . 2018. Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization. CoRR ( 2018 ). Zhiqiang Zhao, Yongyu Wang, and Zhuo Feng. 2018. Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization. CoRR (2018)."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2017.2706941"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2886170"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2017.7963462"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01366-3"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2726578"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417789","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3414685.3417789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:14Z","timestamp":1750197794000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,27]]},"references-count":60,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3414685.3417789"],"URL":"https:\/\/doi.org\/10.1145\/3414685.3417789","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2020,11,27]]},"assertion":[{"value":"2020-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}