{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:25:01Z","timestamp":1787333101756,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We introduce a new theoretical framework for deriving lower bounds on data movement in bilinear algorithms. Bilinear algorithms are a general representation of fast algorithms for bilinear functions, which include computation of matrix multiplication, convolution, and symmetric tensor contractions. A bilinear algorithm is described by three matrices. Our communication lower bounds are based on quantifying the minimal matrix ranks of matching subsets of columns of these matrices. This infrastructure yields new lower bounds for symmetric tensor contraction algorithms, which provide new qualitative insights. Tensor symmetry (invariance under permutation of modes) is common to many applications of tensor computations (e.g., tensor representation of hypergraphs, analysis of high-order moments in data, as well as tensors modeling interactions of electrons in computational chemistry). Tensor symmetry enables reduction in representation size as well as contraction cost by factors that scale with the number of equivalent permutations. However, we derive lower bounds showing that these cost and memory reductions can necessitate increases in data movement by factors that scale with the size of the tensors.<\/jats:p>","DOI":"10.1137\/20m1338599","type":"journal-article","created":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T12:43:48Z","timestamp":1632401028000},"page":"A3328-A3356","source":"Crossref","is-referenced-by-count":3,"title":["Communication Lower Bounds of Bilinear Algorithms for Symmetric Tensor Contractions"],"prefix":"10.1137","volume":"43","author":[{"given":"Edgar","family":"Solomonik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torsten","family":"Hoefler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/72935.72937"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/215399.215427"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"atypb4","first-page":"32","volume":"59","author":"Ballard G.","year":"2013","journal-title":"J. ACM"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00065"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"R. J. Bartlett,\n                      Many-body perturbation theory and coupled cluster theory for electron correlation in molecules\n                      , 32 (1981), pp. 359-401.","DOI":"10.1146\/annurev.pc.32.100181.002043"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0619-6"},{"key":"atypb8","volume-title":"The I\/O Complexity of Strassen's Matrix Multiplication with Recomputation, preprint, https:\/\/arxiv.org\/abs\/1605.02224","author":"Bilardi G.","year":"2016"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/16M1094828"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.21236\/ADA584726"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/060661569"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155333"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.80"},{"key":"atypb14","first-page":"454","volume":"235","author":"Napoli E. Di","year":"2014","journal-title":"Appl. Math. Comput."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.23377"},{"key":"atypb16","first-page":"38","volume-title":"Nachr. Ges. Wiss. G\u00f6ttingen","author":"H\u00f6lder O.","year":"1889"},{"key":"atypb17","first-page":"326","volume-title":"Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC '81)","author":"Hong J.-W.","year":"1981"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2004.03.021"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/355841.355847"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1949-09320-5"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1080\/00268970500131140"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/1026076"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.36"},{"key":"atypb25","volume-title":"thesis","author":"Scott J. N.","year":"2015"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/19M1299633"},{"key":"atypb27","unstructured":"E. Solomonik,\n                      Provably Efficient Algorithms for Numerical Tensor Algebra\n                      , Ph.D. thesis, University of California, Berkeley, 2014."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/2897188"},{"key":"atypb29","volume-title":"Tech. report","author":"Solomonik E.","year":"2015"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1515\/cmam-2019-0075"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.21236\/ADA580199"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.06.002"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"atypb34","unstructured":"A. Tiskin,\n                      The Design and Analysis of Bulk-Synchronous Parallel Algorithms\n                      , Ph.D. thesis, University of Oxford, 1998."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1063\/1.1727484"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1338599","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:32:29Z","timestamp":1787329949000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1338599"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1338599"],"URL":"https:\/\/doi.org\/10.1137\/20m1338599","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}