{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T08:31:17Z","timestamp":1791621077775,"version":"4.3.4"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1818757"],"award-info":[{"award-number":["DMS-1818757"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1952757"],"award-info":[{"award-number":["DMS-1952757"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2045646"],"award-info":[{"award-number":["DMS-2045646"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation Graduate Research Fellowship","award":["DGE-1650441"],"award-info":[{"award-number":["DGE-1650441"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The tensor-train (TT) decomposition expresses a tensor in a data-sparse format used in molecular simulations, high-order correlation functions, and optimization. In this paper, we propose four parallelizable algorithms that compute the TT format from various tensor inputs: (1) Parallel-TTSVD for traditional format, (2) PSTT and its variants for streaming data, (3) Tucker2TT for Tucker format, and (4) TT-fADI for solutions of Sylvester tensor equations. We provide theoretical guarantees of accuracy, parallelization methods, scaling analysis, and numerical results. For example, for a [Formula: see text]-dimension tensor in [Formula: see text], a two-sided sketching algorithm PSTT2 is shown to have a memory complexity of [Formula: see text], improving upon [Formula: see text] from previous algorithms.<\/jats:p>","DOI":"10.1137\/21m146079x","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T14:43:28Z","timestamp":1686062608000},"page":"C101-C130","source":"Crossref","is-referenced-by-count":23,"title":["Parallel Algorithms for Computing the Tensor-Train Decomposition"],"prefix":"10.1137","volume":"45","author":[{"given":"Tianyi","family":"Shi","sequence":"first","affiliation":[{"name":"Scalable Solvers Group, Lawrence Berkeley National Laboratory, Berkeley, CA 94720 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maximilian","family":"Ruth","sequence":"additional","affiliation":[{"name":"Center for Applied Mathematics, Cornell University, Ithaca, NY 14853 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8183-7077","authenticated-orcid":true,"given":"Alex","family":"Townsend","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Cornell University, Ithaca, NY 14853 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"W. Austin , \nG. Ballard , and \nT. G. Kolda , Parallel tensor compression for large-scale scientific data, in Proceedings of the 30th IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2016, pp. 912\u2013922.","DOI":"10.1109\/IPDPS.2016.67"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/3378445"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"G. Ballard , \nN. Knight , and \nK. Rouse , Communication Lower Bounds for Matricized Tensor Times Khatri-Rao Product, in Proceedings of the 32nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2018, pp. 557\u2013567.","DOI":"10.1109\/IPDPS.2018.00065"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"G. Ballard  and \nK. Rouse , General Memory-Independent Lower Bound for MTTKRP, in Proceedings of the 2020 SIAM Conference on Parallel Processing for Scientific Computing (PP), SIAM, Philadelphia, 2020, pp. 1\u201311, https:\/\/doi.org\/10.1137\/1.9781611976137.","DOI":"10.1137\/1.9781611976137.1"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s42967-020-00090-6"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1002\/fld.4843"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2009.08.108"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"A. R. Benson , \nD. F. Gleich , and \nJ. Demmel , Direct QR factorizations for tall-and-skinny matrices in mapreduce architectures, in Proceedings of the 2013 IEEE International Conference on Big Data, 2013, pp. 264\u2013272, https:\/\/doi.org\/10.1109\/BigData.2013.6691583.","DOI":"10.1109\/BigData.2013.6691583"},{"key":"ref9","volume-title":"A Cellular Computer to Implement the Kalman Filter Algorithm","author":"Cannon L. E.","year":"1969"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"E. Chan , \nM. Heimlich , \nA. Purkayastha , and \nR. van de Geijn , On optimizing collective communication, in Proceedings of the 2004 IEEE International Conference on Cluster Computing, IEEE, 2004, pp. 145\u2013155.","DOI":"10.1109\/CLUSTR.2004.1392612"},{"key":"ref11","first-page":"67","volume":"88","author":"Chan T. F.","year":"1987","journal-title":"Linear Algebra Appl."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-018-9622-8"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2017.2771264"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/20M1387158"},{"key":"ref15","unstructured":"H. A. Daas , \nG. Ballard , \nP. Cazeaux , \nE. Hallman , \nA. Miedlar , \nM. Pasha , \nT. W. Reid , and \nA. K. Saibaba , Randomized Algorithms for Rounding in the Tensor-Train Format, preprint, https:\/\/arxiv.org\/abs\/2110.04393, 2021."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896305696"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2004.01.016"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/120882597"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/15M1040414"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1515\/rnam-2013-0009"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/120864210"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/140953289"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/19M128689X"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drz034"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1002\/gamm.201310004"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02487-1_16"},{"key":"ref27","unstructured":"L. Grigori  and \nS. Kumar , Parallel tensor train through hierarchical decomposition, 2020, https:\/\/hal.inria.fr\/hal-03081555v2."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28027-6"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/0169-7439(93)E0086-J"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"O. Kaya  and \nB. U\u00e7ar , High performance parallel algorithms for the Tucker decomposition of sparse tensors, in Proceedings of the 45th International Conference on Parallel Processing (ICPP), IEEE, 2016, pp. 103\u2013112.","DOI":"10.1109\/ICPP.2016.19"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"T. G. Kolda , Multilinear Operators for Higher-order Decompositions, Tech. report, Sandia National Laboratories, 2006.","DOI":"10.2172\/923081"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/140968938"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717839"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"J. Li , \nJ. Choi , \nI. Perros , \nJ. Sun  and \nR. Vuduc , Model-driven sparse CP decomposition for higher-order tensors, in Proceedings of the 2017 International Parallel and Distributed Processing Symposium IEEE (IPDPS), IEEE, 2017, pp. 1048\u20131057.","DOI":"10.1109\/IPDPS.2017.80"},{"key":"ref37","first-page":"24299","volume":"34","author":"Ma L.","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.07.024"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"J. Li , \nJ. Choi , \nI. Perros , \nJ. Sun , and \nR. Vuduc , Model-driven sparse CP decomposition for higher-order tensors, in Proceedings of the 2017 International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2017, pp. 1048\u20131057.","DOI":"10.1109\/IPDPS.2017.80"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/090752286"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/090748330"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.90.085139"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/20M1316639"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/130912839"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"V. I. Slyusar , New operations of matrices product for applications of radars, in Proceedings of the Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), pp. 73\u201374.","DOI":"10.1109\/DIPED.1997.710918"},{"key":"ref46","doi-asserted-by":"crossref","unstructured":"S. Smith , \nN. Ravindran , \nN. D. Sidiropoulos , and \nG. Karypis , SPLATT: Efficient and parallel sparse tensor-matrix multiplication, in Proceedings of the 2015 International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2015, pp. 61\u201370.","DOI":"10.1109\/IPDPS.2015.27"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.06.002"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/19M1257718"},{"key":"ref49","unstructured":"Y. Sun , \nY. Guo , \nJ. A. Tropp  and \nM. Udell , Tensor random projection for low memory dimension reduction, in Proceedings of the 32nd Conference on Neural Information Processing Systems, 2018."},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2018.02.025"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"M. A. O. Vasilescu  and \nD. Terzopoulos , Multilinear analysis of image ensembles: Tensorfaces, in Proceedings of the European Conference on Computer Vision, Springer, 2002, pp. 447\u2013460.","DOI":"10.1007\/3-540-47969-4_30"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2020.2967768"},{"key":"ref54","first-page":"1","volume":"30","author":"Zolotarev E.","year":"1877","journal-title":"Zap. Imp. Akad. Nauk. St. Petersburg"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M146079X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:52:40Z","timestamp":1787334760000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M146079X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/21M146079X"],"URL":"https:\/\/doi.org\/10.1137\/21m146079x","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,7]]}}}