{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T05:46:08Z","timestamp":1787377568650,"version":"build-2736575974"},"reference-count":38,"publisher":"Walter de Gruyter GmbH","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-1548562"],"award-info":[{"award-number":["ACI-1548562"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,1]]},"abstract":"Abstract<\/jats:title>\n In matrix-vector multiplication, matrix symmetry does not permit a straightforward reduction in computational cost.\nMore generally, in contractions of symmetric tensors, the symmetries are not preserved in the usual algebraic form of contraction algorithms.\nWe introduce an algorithm that reduces the bilinear complexity (number of computed elementwise products) for most types of symmetric tensor contractions.\nIn particular, it lowers the bilinear complexity of symmetrized contractions of symmetric tensors of order \n \n \n \n s<\/m:mi>\n +<\/m:mo>\n v<\/m:mi>\n <\/m:mrow>\n <\/m:math>\n \n {s+v}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and \n \n \n \n v<\/m:mi>\n +<\/m:mo>\n t<\/m:mi>\n <\/m:mrow>\n <\/m:math>\n \n {v+t}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> by a factor of \n \n \n \n \n \n (<\/m:mo>\n \n s<\/m:mi>\n +<\/m:mo>\n t<\/m:mi>\n +<\/m:mo>\n v<\/m:mi>\n <\/m:mrow>\n )<\/m:mo>\n <\/m:mrow>\n !<\/m:mo>\n <\/m:mrow>\n \n \n s<\/m:mi>\n !<\/m:mo>\n <\/m:mrow>\n \u2062<\/m:mo>\n \n t<\/m:mi>\n !<\/m:mo>\n <\/m:mrow>\n \u2062<\/m:mo>\n \n v<\/m:mi>\n !<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:mfrac>\n <\/m:math>\n \n {\\frac{(s+t+v)!}{s!t!v!}}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> to leading order.\nThe algorithm computes a symmetric tensor of bilinear products, then subtracts unwanted parts of its partial sums.\nSpecial cases of this algorithm provide improvements to the bilinear complexity of the multiplication of a symmetric matrix and a vector, the symmetrized vector outer product, and the symmetrized product of symmetric matrices.\nWhile the algorithm requires more additions for each elementwise product, the total number of operations is in some cases less than classical algorithms, for tensors of any size.\nWe provide a round-off error analysis of the algorithm and demonstrate that the error is not too large in practice.\nFinally, we provide an optimized implementation for one variant of the symmetry-preserving algorithm, which achieves speedups of up to 4.58\n \n \n \u00d7<\/m:mo>\n <\/m:math>\n \n \\times<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for a particular tensor contraction, relative to a classical approach that casts the problem as a matrix-matrix multiplication.<\/jats:p>","DOI":"10.1515\/cmam-2019-0075","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T09:02:55Z","timestamp":1581066175000},"page":"211-231","source":"Crossref","is-referenced-by-count":6,"title":["Fast Bilinear Algorithms for Symmetric Tensor Contractions"],"prefix":"10.1515","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6480-9066","authenticated-orcid":false,"given":"Edgar","family":"Solomonik","sequence":"first","affiliation":[{"name":"Department of Computer Science , University of Illinois at Urbana-Champaign , Urbana, IL , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science and Department of Mathematics , University of California, Berkeley , Berkeley, CA , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"374","published-online":{"date-parts":[[2020,2,5]]},"reference":[{"key":"2023033111222158331_j_cmam-2019-0075_ref_001","doi-asserted-by":"crossref","unstructured":"A. A. Albert,\nOn Jordan algebras of linear transformations,\nTrans. Amer. Math. Soc. 59 (1946), 524\u2013555.","DOI":"10.1090\/S0002-9947-1946-0016759-3"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_002","unstructured":"E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. D. Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov and D. Sorensen,\nLAPACK Users\u2019 Guide,\nSIAM, Philadelphia, 1992."},{"key":"2023033111222158331_j_cmam-2019-0075_ref_003","doi-asserted-by":"crossref","unstructured":"G. Ballard, J. Demmel, O. Holtz, B. Lipshitz and O. Schwartz,\nCommunication-optimal parallel algorithm for Strassen\u2019s matrix multiplication,\nProceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures\u2014SPAA \u201912,\nACM, New York (2012), 193\u2013204.","DOI":"10.1145\/2312005.2312044"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_004","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd,\nMatrix multiplication via arithmetic progressions,\nJ. Symbolic Comput. 9 (1990), no. 3, 251\u2013280.","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_005","doi-asserted-by":"crossref","unstructured":"E. Deumens, V. F. Lotrich, A. Perera, M. J. Ponton, B. A. Sanders and R. J. Bartlett,\nSoftware design of ACES III with the super instruction architecture,\nWIREs Comput. Molecular Sci. 1 (2011), no. 6, 895\u2013901.","DOI":"10.1002\/wcms.77"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_006","doi-asserted-by":"crossref","unstructured":"E. Epifanovsky, M. Wormit, T. Ku\u015b, A. Landau, D. Zuev, K. Khistyaev, P. Manohar, I. Kaliman, A. Dreuw and A. I. Krylov,\nNew implementation of high-level correlated methods using a general block-tensor library for high-performance electronic structure calculations,\nJ. Comput. Chem. (2013), 10.1002\/jcc.23377.","DOI":"10.1002\/jcc.23377"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_007","doi-asserted-by":"crossref","unstructured":"A. Gr\u00fcneis, G. H. Booth, M. Marsman, J. Spencer, A. Alavi and G. Kresse,\nNatural orbitals for wave function based correlated calculations using a plane wave basis set,\nJ. Chem. Theory Comput. 7 (2011), no. 9, 2780\u20132785.","DOI":"10.1021\/ct200263g"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_008","doi-asserted-by":"crossref","unstructured":"W. Hackbusch,\nA sparse matrix arithmetic based on \n \n \n \u210b\n \n \n {\\mathscr{H}}\n \n -matrices. I. Introduction to \n \n \n \u210b\n \n \n {\\mathscr{H}}\n \n -matrices,\nComputing 62 (1999), no. 2, 89\u2013108.","DOI":"10.1007\/s006070050015"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_009","doi-asserted-by":"crossref","unstructured":"M. Hanrath and A. Engels-Putzka,\nAn efficient matrix-matrix multiplication based antisymmetric tensor contraction engine for general order coupled cluster,\nJ. Chem. Phys. 133 (2010), no. 6, Article ID 064108.","DOI":"10.1063\/1.3467878"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_010","doi-asserted-by":"crossref","unstructured":"M. Head-Gordon, J. A. Pople and M. J. Frisch,\nMP2 energy evaluation by direct methods,\nChem. Phys. Lett. 153 (1988), no. 6, 503\u2013506.","DOI":"10.1016\/0009-2614(88)85250-3"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_011","doi-asserted-by":"crossref","unstructured":"S. Hirata,\nTensor Contraction Engine: Abstraction and automated parallel implementation of configuration-interaction, coupled-cluster, and many-body perturbation theories,\nJ. Phys. Chem. A 107 (2003), no. 46, 9887\u20139897.","DOI":"10.1021\/jp034596z"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_012","doi-asserted-by":"crossref","unstructured":"F. L. Hitchcock,\nThe expression of a tensor or a polyadic as a sum of products,\nStud. Appl. Math. 6 (1927), no. 1\u20134, 164\u2013189.","DOI":"10.1002\/sapm192761164"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_013","doi-asserted-by":"crossref","unstructured":"J. Huang, D. A. Matthews and R. A. van de Geijn,\nStrassen\u2019s algorithm for tensor contraction,\nSIAM J. Sci. Comput. 40 (2018), no. 3, C305\u2013C326.","DOI":"10.1137\/17M1135578"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_014","doi-asserted-by":"crossref","unstructured":"M. K\u00e1llay and P. R. Surj\u00e1n,\nHigher excitations in coupled-cluster theory,\nJ. Chem. Phys. 115 (2001), no. 7, Article ID 2945.","DOI":"10.1063\/1.1383290"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_015","doi-asserted-by":"crossref","unstructured":"V. Khoromskaia and B. N. Khoromskij,\nTensor Numerical Methods in Quantum Chemistry,\nDe Gruyter, Berlin, 2018.","DOI":"10.1515\/9783110365832"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_016","doi-asserted-by":"crossref","unstructured":"B. N. Khoromskij,\nTensor Numerical Methods in Scientific Computing,\nadon Ser. Comput. Appl. Math. 19,\nDe Gruyter, Berlin, 2018.","DOI":"10.1515\/9783110365917"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_017","doi-asserted-by":"crossref","unstructured":"T. G. Kolda and B. W. Bader,\nTensor decompositions and applications,\nSIAM Rev. 51 (2009), no. 3, 455\u2013500.","DOI":"10.1137\/07070111X"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_018","doi-asserted-by":"crossref","unstructured":"C. L. Lawson, R. J. Hanson, D. R. Kincaid and F. T. Krogh,\nBasic linear algebra subprograms for Fortran usage,\nACM Trans. Math. Software (TOMS), 5 (1979), no. 3, 308\u2013323.","DOI":"10.1145\/355841.355847"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_019","doi-asserted-by":"crossref","unstructured":"V. Lotrich, N. Flocke, M. Ponton, B. A. Sanders, E. Deumens, R. J. Bartlett and A. Perera,\nAn infrastructure for scalable and portable parallel programs for computational chemistry,\nProceedings of the 23rd International Conference on Supercomputing\u2014ICS \u201909,\nACM, New York (2009), 523\u2013524.","DOI":"10.1145\/1542275.1542361"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_020","unstructured":"D. A. Matthews and J. F. Stanton,\nAquarius: Scalability and extensibility by design,\nAbstracts Papers Amer. Chem. Soc. 248 (2014)."},{"key":"2023033111222158331_j_cmam-2019-0075_ref_021","doi-asserted-by":"crossref","unstructured":"J. Noga and P. Valiron,\nImproved algorithm for triple-excitation contributions within the coupled cluster approach,\nMolecular Phys. 103 (2005), no. 15\u201316, 2123\u20132130.","DOI":"10.1080\/00268970500131140"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_022","doi-asserted-by":"crossref","unstructured":"R. Or\u00fas,\nA practical introduction to tensor networks: Matrix product states and projected entangled pair states,\nAnn. Physics 349 (2014), 117\u2013158.","DOI":"10.1016\/j.aop.2014.06.013"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_023","doi-asserted-by":"crossref","unstructured":"I. V. Oseledets,\nTensor-train decomposition,\nSIAM J. Sci. Comput. 33 (2011), no. 5, 2295\u20132317.","DOI":"10.1137\/090752286"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_024","doi-asserted-by":"crossref","unstructured":"V. Pan,\nHow can we speed up matrix multiplication?,\nSIAM Rev. 26 (1984), no. 3, 393\u2013415.","DOI":"10.1137\/1026076"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_025","unstructured":"S. Rajbhandari, A. Nikam, P.-W. Lai, K. Stock, S. Krishnamoorthy and P. Sadayappan,\nFramework for distributed contractions of tensors with symmetry, preprint (2013), Ohio State University."},{"key":"2023033111222158331_j_cmam-2019-0075_ref_026","doi-asserted-by":"crossref","unstructured":"M. D. Schatz, T. M. Low, R. A. van de Geijn and T. G. Kolda,\nExploiting symmetry in tensors for high performance: multiplication with symmetric tensors,\nSIAM J. Sci. Comput. 36 (2014), no. 5, C453\u2013C479.","DOI":"10.1137\/130907215"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_027","unstructured":"Y. Shao,\nAdvances in methods and algorithms in a modern quantum chemistry program package,\nPhys. Chem. Chem. Phys. 8 (2006), no. 27, 3172\u20133191."},{"key":"2023033111222158331_j_cmam-2019-0075_ref_028","unstructured":"E. Solomonik,\nProvably Efficient Algorithms for Numerical Tensor Algebra,\nPhD thesis, University of California, Berkeley, 2014."},{"key":"2023033111222158331_j_cmam-2019-0075_ref_029","unstructured":"E. Solomonik and J. Demmel,\nContracting symmetric tensors using fewer multiplications,\nTechnical report, ETH Z\u00fcrich, 2015."},{"key":"2023033111222158331_j_cmam-2019-0075_ref_030","doi-asserted-by":"crossref","unstructured":"E. Solomonik, D. Matthews, J. R. Hammond, J. F. Stanton and J. Demmel,\nA massively parallel tensor contraction framework for coupled-cluster computations,\nJ. Parallel Distributed Comput. 74 (2014), no. 12, 3176\u20133190.","DOI":"10.1016\/j.jpdc.2014.06.002"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_031","doi-asserted-by":"crossref","unstructured":"V. Strassen,\nGaussian elimination is not optimal,\nNumer. Math. 13 (1969), 354\u2013356.","DOI":"10.1007\/BF02165411"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_032","doi-asserted-by":"crossref","unstructured":"V. Strassen,\nRank and optimal computation of generic tensors,\nLinear Algebra Appl. 52\/53 (1983), 645\u2013685.","DOI":"10.1016\/0024-3795(83)80041-X"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_033","doi-asserted-by":"crossref","unstructured":"L. R. Tucker,\nSome mathematical notes on three-mode factor analysis,\nPsychometrika 31 (1966), 279\u2013311.","DOI":"10.1007\/BF02289464"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_034","doi-asserted-by":"crossref","unstructured":"M. Valiev, E. J. Bylaska, N. Govind, K. Kowalski, T. P. Straatsma, H. J. Van Dam, D. Wang, J. Nieplocha, E. Apra, T. Windus and W. A. de Jong,\nNWChem: A comprehensive and scalable open-source solution for large scale molecular simulations,\nComput. Phys. Commun. 181 (2010), no. 9, 1477\u20131489.","DOI":"10.1016\/j.cpc.2010.04.018"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_035","doi-asserted-by":"crossref","unstructured":"V. V. Williams,\nMultiplying matrices faster than Coppersmith\u2013Winograd,\nProceedings of the 2012 ACM Symposium on Theory of Computing\u2014STOC\u201912,\nACM, New York (2012), 887\u2013898.","DOI":"10.1145\/2213977.2214056"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_036","doi-asserted-by":"crossref","unstructured":"J. Xia, S. Chandrasekaran, M. Gu and X. S. Li,\nFast algorithms for hierarchically semiseparable matrices,\nNumer. Linear Algebra Appl. 17 (2010), no. 6, 953\u2013976.","DOI":"10.1002\/nla.691"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_037","doi-asserted-by":"crossref","unstructured":"K. Ye and L.-H. Lim,\nAlgorithms for structured matrix-vector product of optimal bilinear complexity,\n2016 IEEE Information Theory Workshop (ITW),\nIEEE Press, Piscataway (2016), 310\u2013314.","DOI":"10.1109\/ITW.2016.7606846"},{"key":"2023033111222158331_j_cmam-2019-0075_ref_038","doi-asserted-by":"crossref","unstructured":"K. Ye and L.-H. Lim,\nFast structured matrix computations: tensor rank and Cohn\u2013Umans method,\nFound. Comput. Math. 18 (2018), no. 1, 45\u201395.","DOI":"10.1007\/s10208-016-9332-x"}],"container-title":["Computational Methods in Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/cmam\/21\/1\/article-p211.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2019-0075\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2019-0075\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,31]],"date-time":"2023-03-31T14:36:15Z","timestamp":1680273375000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2019-0075\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,5]]},"references-count":38,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,2,7]]},"published-print":{"date-parts":[[2021,1,1]]}},"alternative-id":["10.1515\/cmam-2019-0075"],"URL":"https:\/\/doi.org\/10.1515\/cmam-2019-0075","relation":{},"ISSN":["1609-4840","1609-9389"],"issn-type":[{"value":"1609-4840","type":"print"},{"value":"1609-9389","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,5]]}}}