{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T05:29:33Z","timestamp":1739510973493,"version":"3.37.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T00:00:00Z","timestamp":1699228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T00:00:00Z","timestamp":1699228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2025,2]]},"DOI":"10.1007\/s10208-023-09633-8","type":"journal-article","created":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T18:02:03Z","timestamp":1699293723000},"page":"55-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Communication Lower Bounds for Nested Bilinear Algorithms via Rank Expansion of Kronecker Products"],"prefix":"10.1007","volume":"25","author":[{"given":"Caleb","family":"Ju","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yifan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edgar","family":"Solomonik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,6]]},"reference":[{"issue":"5","key":"9633_CR1","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1109\/TASSP.1977.1162981","volume":"25","author":"R Agarwal","year":"1977","unstructured":"Agarwal, R., Cooley, J.: New algorithms for digital convolution. IEEE Transactions on Acoustics, Speech, and Signal Processing 25(5), 392\u2013410 (1977)","journal-title":"IEEE Transactions on Acoustics, Speech, and Signal Processing"},{"issue":"5","key":"9633_CR2","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1007\/s11590-019-01422-z","volume":"13","author":"A Agrawal","year":"2019","unstructured":"Agrawal, A., Diamond, S., Boyd, S.: Disciplined geometric programming. Optimization Letters 13(5), 961\u2013976 (2019)","journal-title":"Optimization Letters"},{"key":"9633_CR3","doi-asserted-by":"crossref","unstructured":"Ballard, G., Buluc, A., Demmel, J., Grigori, L., Lipshitz, B., Schwartz, O., Toledo, S.: Communication optimal parallel multiplication of sparse random matrices. In: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures, pp. 222\u2013231 (2013)","DOI":"10.1145\/2486159.2486196"},{"key":"9633_CR4","doi-asserted-by":"crossref","unstructured":"Ballard, G., Demmel, J., Holtz, O., Lipshitz, B., Schwartz, O.: Communication-optimal parallel algorithm for Strassen\u2019s matrix multiplication. In: Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures, pp. 193\u2013204 (2012)","DOI":"10.1145\/2312005.2312044"},{"issue":"3","key":"9633_CR5","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1137\/090769156","volume":"32","author":"G Ballard","year":"2011","unstructured":"Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Minimizing communication in numerical linear algebra. SIAM Journal on Matrix Analysis and Applications 32(3), 866\u2013901 (2011)","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"6","key":"9633_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2395116.2395121","volume":"59","author":"G Ballard","year":"2013","unstructured":"Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Graph expansion and communication costs of fast matrix multiplication. Journal of the ACM (JACM) 59(6), 1\u201323 (2013)","journal-title":"Journal of the ACM (JACM)"},{"issue":"3","key":"9633_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3015144","volume":"3","author":"G Ballard","year":"2016","unstructured":"Ballard, G., Druinsky, A., Knight, N., Schwartz, O.: Hypergraph partitioning for sparse matrix-matrix multiplication. ACM Transactions on Parallel Computing (TOPC) 3(3), 1\u201334 (2016)","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"key":"9633_CR8","doi-asserted-by":"crossref","unstructured":"Ballard, G., Knight, N., Rouse, K.: Communication lower bounds for matricized tensor times Khatri-Rao product. In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 557\u2013567. IEEE (2018)","DOI":"10.1109\/IPDPS.2018.00065"},{"key":"9633_CR9","doi-asserted-by":"crossref","unstructured":"Bilardi, G., De\u00a0Stefani, L.: The I\/O complexity of Strassen\u2019s matrix multiplication with recomputation. In: Workshop on Algorithms and Data Structures, pp. 181\u2013192. Springer (2017)","DOI":"10.1007\/978-3-319-62127-2_16"},{"key":"9633_CR10","doi-asserted-by":"crossref","unstructured":"Bilardi, G., De\u00a0Stefani, L.: The I\/O complexity of Toom-Cook integer multiplication. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2034\u20132052. SIAM (2019)","DOI":"10.1137\/1.9781611975482.123"},{"issue":"2","key":"9633_CR11","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1006\/jpdc.1995.1080","volume":"27","author":"G Bilardi","year":"1995","unstructured":"Bilardi, G., Preparata, F.P.: Horizons of parallel computation. Journal of Parallel and Distributed Computing 27(2), 172\u2013182 (1995)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"5","key":"9633_CR12","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s002240000131","volume":"32","author":"G Bilardi","year":"1999","unstructured":"Bilardi, G., Preparata, F.P.: Processor-time tradeoffs under bounded-speed message propagation: Part II, lower bounds. Theory of Computing Systems 32(5), 531\u2013559 (1999)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"9633_CR13","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0001-8708(76)90184-5","volume":"20","author":"HJ Brascamp","year":"1976","unstructured":"Brascamp, H.J., Lieb, E.H.: Best constants in Young\u2019s inequality, its converse, and its generalization to more than three functions. Advances in Mathematics 20(2), 151\u2013173 (1976)","journal-title":"Advances in Mathematics"},{"key":"9633_CR14","doi-asserted-by":"crossref","unstructured":"Christ, M., Demmel, J., Knight, N., Scanlon, T., Yelick, K.: Communication lower bounds and optimal algorithms for programs that reference arrays\u2013part 1. arXiv:1308.0068 (2013)","DOI":"10.21236\/ADA584726"},{"key":"9633_CR15","unstructured":"De\u00a0Stefani, L.: On the I\/O complexity of hybrid algorithms for integer multiplication. arXiv:1912.08045 (2020)"},{"key":"9633_CR16","unstructured":"Demmel, J., Dinh, G.: Communication-optimal convolutional neural nets. arXiv:1802.06905 (2018)"},{"key":"9633_CR17","doi-asserted-by":"crossref","unstructured":"Dinh, G., Demmel, J.: Communication-optimal tilings for projective nested loops with arbitrary bounds. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 523\u2013525 (2020)","DOI":"10.1145\/3350755.3400275"},{"key":"9633_CR18","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944","volume-title":"Matrix Computations","author":"GH Golub","year":"2013","unstructured":"Golub, G.H., Van\u00a0Loan, C.F.: Matrix Computations. The Johns Hopkins University Press, (2013)"},{"key":"9633_CR19","unstructured":"Halmos, P.R.: Finite-dimensional vector spaces. Springer, (1958)"},{"issue":"46","key":"9633_CR20","doi-asserted-by":"publisher","first-page":"9887","DOI":"10.1021\/jp034596z","volume":"107","author":"S Hirata","year":"2003","unstructured":"Hirata, S.: Tensor Contraction Engine: Abstraction and automated parallel implementation of configuration-interaction, coupled-cluster, and many-body perturbation theories. The Journal of Physical Chemistry A 107(46), 9887\u20139897 (2003)","journal-title":"The Journal of Physical Chemistry A"},{"key":"9633_CR21","unstructured":"H\u00f6lder, O.: \u00dcber einen mittelwertssatz. Nachr. Acad. Wiss. G\u00f6ttingen Math.-Phys. K pp. 38\u201347 (1889)"},{"key":"9633_CR22","doi-asserted-by":"crossref","unstructured":"Hong, J.W., Kung, H.T.: I\/O complexity: The red-blue pebble game. In: Proceedings of the thirteenth annual ACM symposium on Theory of computing, pp. 326\u2013333 (1981)","DOI":"10.1145\/800076.802486"},{"issue":"9","key":"9633_CR23","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/j.jpdc.2004.03.021","volume":"64","author":"D Irony","year":"2004","unstructured":"Irony, D., Toledo, S., Tiskin, A.: Communication lower bounds for distributed-memory matrix multiplication. Journal of Parallel and Distributed Computing 64(9), 1017\u20131026 (2004)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"9633_CR24","doi-asserted-by":"crossref","unstructured":"Jain, S., Zaharia, M.: Spectral lower bounds on the I\/O complexity of computation graphs. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 329\u2013338 (2020)","DOI":"10.1145\/3350755.3400210"},{"issue":"4","key":"9633_CR25","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1137\/19M1301059","volume":"62","author":"C Ju","year":"2020","unstructured":"Ju, C., Solomonik, E.: Derivation and analysis of fast bilinear algorithms for convolution. SIAM Review 62(4), 743\u2013777 (2020)","journal-title":"SIAM Review"},{"issue":"6","key":"9633_CR26","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1109\/MCSE.2013.95","volume":"15","author":"P Kogge","year":"2013","unstructured":"Kogge, P., Shalf, J.: Exascale computing trends: Adjusting to the \u201cnew normal\u201d for computer architecture. Computing in Science & Engineering 15(6), 16\u201326 (2013)","journal-title":"Computing in Science & Engineering"},{"issue":"2","key":"9633_CR27","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0024-3795(77)90069-6","volume":"18","author":"JB Kruskal","year":"1977","unstructured":"Kruskal, J.B.: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear algebra and its applications 18(2), 95\u2013138 (1977)","journal-title":"Linear algebra and its applications"},{"key":"9633_CR28","doi-asserted-by":"crossref","unstructured":"Lavin, A., Gray, S.: Fast algorithms for convolutional neural networks. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4013\u20134021 (2016)","DOI":"10.1109\/CVPR.2016.435"},{"issue":"10","key":"9633_CR29","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1090\/S0002-9904-1949-09320-5","volume":"55","author":"LH Loomis","year":"1949","unstructured":"Loomis, L.H., Whitney, H.: An inequality related to the isoperimetric inequality. Bulletin of the American Mathematical Society 55(10), 961\u2013962 (1949)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"9633_CR30","doi-asserted-by":"crossref","unstructured":"Nissim, R., Schwartz, O.: Revisiting the I\/O-complexity of fast matrix multiplication with recomputations. In: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 482\u2013490. IEEE (2019)","DOI":"10.1109\/IPDPS.2019.00058"},{"issue":"3","key":"9633_CR31","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1137\/1026076","volume":"26","author":"V Pan","year":"1984","unstructured":"Pan, V.: How can we speed up matrix multiplication? SIAM review 26(3), 393\u2013415 (1984)","journal-title":"SIAM review"},{"issue":"3","key":"9633_CR32","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TASSP.1987.1165132","volume":"35","author":"I Pitas","year":"1987","unstructured":"Pitas, I., Strintzis, M.: Multidimensional cyclic convolution algorithms with minimal multiplicative complexity. IEEE transactions on acoustics, speech, and signal processing 35(3), 384\u2013390 (1987)","journal-title":"IEEE transactions on acoustics, speech, and signal processing"},{"key":"9633_CR33","doi-asserted-by":"crossref","unstructured":"Selesnick, I.W., Burrus, C.S.: Extending Winograd\u2019s small convolution algorithm to longer lengths. In: Proceedings of IEEE International Symposium on Circuits and Systems-ISCAS\u201994, vol.\u00a02, pp. 449\u2013452. IEEE (1994)","DOI":"10.1109\/ISCAS.1994.408999"},{"issue":"1","key":"9633_CR34","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1515\/cmam-2019-0075","volume":"21","author":"E Solomonik","year":"2021","unstructured":"Solomonik, E., Demmel, J.: Fast bilinear algorithms for symmetric tensor contractions. Computational Methods in Applied Mathematics 21(1), 211\u2013231 (2021)","journal-title":"Computational Methods in Applied Mathematics"},{"issue":"5","key":"9633_CR35","doi-asserted-by":"publisher","first-page":"A3328","DOI":"10.1137\/20M1338599","volume":"43","author":"E Solomonik","year":"2021","unstructured":"Solomonik, E., Demmel, J., Hoefler, T.: Communication lower bounds of bilinear algorithms for symmetric tensor contractions. SIAM Journal on Scientific Computing 43(5), A3328\u2013A3356 (2021)","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"4","key":"9633_CR36","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische mathematik 13(4), 354\u2013356 (1969)","journal-title":"Numerische mathematik"},{"key":"9633_CR37","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributive computing. In: Proceedings of the eleventh annual ACM symposium on Theory of computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-023-09633-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-023-09633-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-023-09633-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T18:53:07Z","timestamp":1739472787000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-023-09633-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,6]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["9633"],"URL":"https:\/\/doi.org\/10.1007\/s10208-023-09633-8","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"type":"print","value":"1615-3375"},{"type":"electronic","value":"1615-3383"}],"subject":[],"published":{"date-parts":[[2023,11,6]]},"assertion":[{"value":"2 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}