{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:41:30Z","timestamp":1787503290864,"version":"build-2736575974"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,9,26]],"date-time":"2016-09-26T00:00:00Z","timestamp":1474848000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10208-016-9332-x","type":"journal-article","created":{"date-parts":[[2016,9,26]],"date-time":"2016-09-26T13:10:07Z","timestamp":1474895407000},"page":"45-95","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Fast Structured Matrix Computations: Tensor Rank and Cohn\u2013Umans Method"],"prefix":"10.1007","volume":"18","author":[{"given":"Ke","family":"Ye","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lek-Heng","family":"Lim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,9,26]]},"reference":[{"key":"9332_CR1","doi-asserted-by":"crossref","unstructured":"W. A. Adkins and S. H. Weintraub, Algebra: An approach via module theory, Graduate Texts in Mathematics, 136, Springer, New York, 1992.","DOI":"10.1007\/978-1-4612-0923-2"},{"issue":"2","key":"9332_CR2","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/0216021","volume":"16","author":"D Bini","year":"1987","unstructured":"D.\u00a0Bini and M.\u00a0Capovani, \u201cTensor rank and border rank of band Toeplitz matrices,\u201d SIAM J. Comput., 16 (1987), no.\u00a02, pp.\u00a0252\u2013258.","journal-title":"SIAM J. Comput."},{"key":"9332_CR3","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611971484","volume-title":"Numerical Methods for Least Squares Problems","author":"\u00c5 Bj\u00f6rck","year":"1996","unstructured":"\u00c5.\u00a0Bj\u00f6rck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, PA, 1996."},{"key":"9332_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1201\/9781420035377","volume-title":"Mathematics of Quantum Computation","author":"J-L Brylinski","year":"2002","unstructured":"J.-L.\u00a0Brylinski, \u201cAlgebraic measures of entanglement,\u201d pp.\u00a03\u201323, G.\u00a0Chen and R.\u00a0K.\u00a0Brylinski (Eds), Mathematics of Quantum Computation, CRC, Boca Raton, FL, 2002."},{"issue":"2","key":"9332_CR5","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1016\/j.laa.2012.05.001","volume":"438","author":"J Buczy\u0144ski","year":"2013","unstructured":"J.\u00a0Buczy\u0144ski and J.\u00a0M.\u00a0Landsberg, \u201cRanks of tensors and a generalization of secant varieties,\u201d Linear Algebra Appl., 438 (2013), no.\u00a02, pp.\u00a0668\u2013689.","journal-title":"Linear Algebra Appl."},{"key":"9332_CR6","volume-title":"Algebraic Complexity Theory, Grundlehren der Mathematischen Wissenschaften","author":"P B\u00fcrgisser","year":"1997","unstructured":"P.\u00a0B\u00fcrgisser, M.\u00a0Clausen, and M.\u00a0A.\u00a0Shokrollahi, Algebraic Complexity Theory, Grundlehren der Mathematischen Wissenschaften, 315, Springer-Verlag, Berlin, 1997."},{"key":"9332_CR7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718850","volume-title":"An Introduction to Iterative Toeplitz Solvers, Fundamentals of Algorithms","author":"RH-F Chan","year":"2007","unstructured":"R.\u00a0H.-F.\u00a0Chan and X.-Q.\u00a0Jin, An Introduction to Iterative Toeplitz Solvers, Fundamentals of Algorithms, 5, SIAM, Philadelphia, PA, 2007."},{"key":"9332_CR8","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1109\/SFCS.2005.39","volume":"46","author":"H Cohn","year":"2005","unstructured":"H.\u00a0Cohn, R.\u00a0Kleinberg, B.\u00a0Szegedy, and C.\u00a0Umans, \u201cGroup-theoretic algorithms for matrix multiplication,\u201d Proc. IEEE Symp. Found. Comput. Sci. (FOCS), 46 (2005), pp.\u00a0379\u2013388.","journal-title":"Proc. IEEE Symp. Found. Comput. Sci. (FOCS)"},{"key":"9332_CR9","first-page":"438","volume":"44","author":"H Cohn","year":"2003","unstructured":"H.\u00a0Cohn and C.\u00a0Umans, \u201cA group-theoretic approach to fast matrix multiplication,\u201d Proc. IEEE Symp. Found. Comput. Sci. (FOCS), 44 (2003), pp.\u00a0438\u2013449.","journal-title":"Proc. IEEE Symp. Found. Comput. Sci. (FOCS)"},{"key":"9332_CR10","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1137\/1.9781611973105.77","volume":"24","author":"H Cohn","year":"2013","unstructured":"H.\u00a0Cohn and C.\u00a0Umans, \u201cFast matrix multiplication using coherent configurations,\u201d Proc. ACM\u2013SIAM Symp. Discrete Algorithms (SODA), 24 ( 2013), pp.\u00a01074\u20131087.","journal-title":"Proc. ACM-SIAM Symp. Discrete Algorithms (SODA)"},{"key":"9332_CR11","unstructured":"S. A. Cook, On the Minimum Computation Time of Functions, Ph.D. thesis, Harvard University, Cambridge, MA, 1966."},{"issue":"90","key":"9332_CR12","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","volume":"19","author":"JW Cooley","year":"1965","unstructured":"J.\u00a0W.\u00a0Cooley and J.\u00a0W.\u00a0Tukey, \u201cAn algorithm for the machine calculation of complex Fourier series,\u201d Math. Comp., 19 (1965), no.\u00a090, pp.\u00a0297\u2013301.","journal-title":"Math. Comp."},{"issue":"3","key":"9332_CR13","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D Coppersmith","year":"1990","unstructured":"D.\u00a0Coppersmith and S.\u00a0Winograd, \u201cMatrix multiplication via arithmetic progressions,\u201d J. Symbolic Comput., 9 (1990), no.\u00a03, pp.\u00a0251\u2013280.","journal-title":"J. Symb. Comput."},{"key":"9332_CR14","volume-title":"Circulant Matrices","author":"PJ Davis","year":"1979","unstructured":"P.\u00a0J.\u00a0Davis, Circulant Matrices, John Wiley, New York, NY, 1979."},{"issue":"3","key":"9332_CR15","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.1137\/06066518X","volume":"30","author":"V Silva De","year":"2008","unstructured":"V.\u00a0De\u00a0Silva and L.-H.\u00a0Lim, \u201cTensor rank and the ill-posedness of the best low-rank approximation problem,\u201d SIAM J. Matrix Anal. Appl., 30 (2008), no.\u00a03, pp.\u00a01084\u20131127.","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"2","key":"9332_CR16","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s00211-007-0061-6","volume":"106","author":"J Demmel","year":"2007","unstructured":"J.\u00a0Demmel, I.\u00a0Dumitriu, O.\u00a0Holtz, and R.\u00a0Kleinberg, \u201cFast matrix multiplication is stable,\u201d Numer. Math., 106 (2007), no.\u00a02, pp.\u00a0199\u2013224.","journal-title":"Numer. Math."},{"key":"9332_CR17","unstructured":"S. Friedland and L.-H. Lim, \u201cNuclear norm of higher-order tensors,\u201d (2016). http:\/\/arxiv.org\/abs\/1410.6072 ."},{"issue":"3","key":"9332_CR18","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M F\u00fcrer","year":"2009","unstructured":"M.\u00a0F\u00fcrer, \u201cFaster integer multiplication,\u201d SIAM J. Comput., 39 (2009), no.\u00a03, pp.\u00a0979\u20131005.","journal-title":"SIAM J. Comput."},{"key":"9332_CR19","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix Computations","author":"G Golub","year":"2013","unstructured":"G.\u00a0Golub and C.\u00a0Van\u00a0Loan, Matrix Computations, 4th Ed., Johns Hopkins University Press, Baltimore, MD, 2013.","edition":"4"},{"key":"9332_CR20","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718027","volume-title":"Accuracy and Stability of Numerical Algorithms","author":"NJ Higham","year":"2002","unstructured":"N.\u00a0J.\u00a0Higham, Accuracy and Stability of Numerical Algorithms, 2nd Ed., SIAM, Philadelphia, PA, 2002.","edition":"2"},{"key":"9332_CR21","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717778","volume-title":"Functions of Matrices","author":"NJ Higham","year":"2008","unstructured":"N.\u00a0J.\u00a0Higham, Functions of Matrices, SIAM, Philadelphia, PA, 2008."},{"issue":"3","key":"9332_CR22","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/0613043","volume":"13","author":"NJ Higham","year":"1992","unstructured":"N.\u00a0J.\u00a0Higham, \u201cStability of a method for multiplying complex matrices with three real matrix multiplications,\u201d SIAM J. Matrix Anal. Appl., 13 (1992), no.\u00a03, pp.\u00a0681\u2013687.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9332_CR23","unstructured":"Intel 64 and IA-32 Architectures Optimization Reference Manual, September 2015. http:\/\/www.intel.com\/content\/dam\/www\/public\/us\/en\/documents\/manuals\/64-ia-32-architectures-optimization-manual"},{"issue":"1","key":"9332_CR24","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/S0895479889169042","volume":"15","author":"T Kailath","year":"1994","unstructured":"T.\u00a0Kailath and J.\u00a0Chun, \u201cGeneralized displacement structure for block-Toeplitz, Toeplitz-block, and Toeplitz-derived matrices,\u201d SIAM J. Matrix Anal. Appl., 15 (1994), no.\u00a01, pp.\u00a0114\u2013128.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9332_CR25","unstructured":"A. Karatsuba and Yu. Ofman, \u201cMultiplication of many-digital numbers by automatic computers,\u201d Dokl. Akad. Nauk SSSR, 145 (1962), pp. 293\u2013294 [English translation: Soviet Phys. Dokl., 7 (1963), pp. 595\u2013596]."},{"key":"9332_CR26","unstructured":"D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical algorithms, 3rd Ed., Addison\u2013Wesley, Reading, MA, 1998."},{"key":"9332_CR27","unstructured":"V. K. Kodavalla, \u201cIP gate count estimation methodology during micro-architecture phase,\u201d IP Based Electronic System Conference and Exhibition (IP-SOC), Grenoble, France, December 2007. http:\/\/www.design-reuse.com\/articles\/19171\/ip-gate-count-estimation-micro-architecture-phase.html"},{"key":"9332_CR28","volume-title":"Tensors: Geometry and Applications, Graduate Studies in Mathematics","author":"JM Landsberg","year":"2012","unstructured":"J.\u00a0M.\u00a0Landsberg, Tensors: Geometry and Applications, Graduate Studies in Mathematics, 128, AMS, Providence, RI, 2012."},{"key":"9332_CR29","doi-asserted-by":"crossref","unstructured":"S.\u00a0Lang, Algebra, Rev. 3rd Ed., Graduate Texts in Mathematics, 211, Springer, New York, NY, 2002.","DOI":"10.1007\/978-1-4613-0041-0_1"},{"key":"9332_CR30","first-page":"296","volume":"39","author":"F Gall Le","year":"2014","unstructured":"F.\u00a0Le\u00a0Gall, \u201cPowers of tensors and fast matrix multiplication,\u201d Proc. Internat. Symp. Symbolic Algebr. Comput. (ISSAC), 39 (2014), pp.\u00a0296\u2013303.","journal-title":"Proc. Int. Symp. Symbolic Algebr. Comput. (ISSAC)"},{"key":"9332_CR31","volume-title":"Handbook of Linear Algebra","author":"L-H Lim","year":"2013","unstructured":"L.-H.\u00a0Lim, \u201cTensors and hypermatrices,\u201d in: L.\u00a0Hogben (Ed.), Handbook of Linear Algebra, 2nd Ed., CRC Press, Boca Raton, FL, 2013.","edition":"2"},{"key":"9332_CR32","doi-asserted-by":"crossref","unstructured":"J. C. McConnell and J. C. Robson, Noncommutative Noetherian Rings, Rev. Ed., Graduate Studies in Mathematics, 30, AMS, Providence, RI, 2001.","DOI":"10.1090\/gsm\/030"},{"issue":"2","key":"9332_CR33","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1137\/0204009","volume":"4","author":"W Miller","year":"1975","unstructured":"W.\u00a0Miller, \u201cComputational complexity and numerical stability,\u201d SIAM J. Comput., 4 (1975), no.\u00a02, pp.\u00a097\u2013107.","journal-title":"SIAM J. Comput."},{"key":"9332_CR34","volume-title":"Iterative Methods for Toeplitz Systems","author":"MK Ng","year":"2004","unstructured":"M.\u00a0K.\u00a0Ng, Iterative Methods for Toeplitz Systems, Oxford University Press, New York, NY, 2004."},{"key":"9332_CR35","first-page":"315","volume":"21","author":"G Ottaviani","year":"2007","unstructured":"G.\u00a0Ottaviani, \u201cSymplectic bundles on the plane, secant varieties and L\u00fcroth quartics revisited,\u201d Quad. Mat., 21 (2007), pp.\u00a0315\u2013352.","journal-title":"Quad. Mat."},{"key":"9332_CR36","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0129-8","volume-title":"Structured Matrices and Polynomials: Unified Superfast Algorithms","author":"VY Pan","year":"2001","unstructured":"V.\u00a0Y.\u00a0Pan, Structured Matrices and Polynomials: Unified superfast algorithms, Birkh\u00e4user, Boston, MA, 2001."},{"issue":"3","key":"9332_CR37","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1137\/0210032","volume":"10","author":"A Sch\u00f6nhage","year":"1981","unstructured":"A.\u00a0Sch\u00f6nhage, \u201cPartial and total matrix multiplication,\u201d SIAM J. Comput., 10 (1981), no.\u00a03, pp.\u00a0434\u2013455.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9332_CR38","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A Sch\u00f6nhage","year":"1971","unstructured":"A.\u00a0Sch\u00f6nhage and V.\u00a0Strassen, \u201cSchnelle Multiplikation gro\u00dfer Zahlen,\u201d Computing, 7 (1971), no.\u00a03, pp.\u00a0281\u2013292.","journal-title":"Computing"},{"issue":"3","key":"9332_CR39","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1137\/120897572","volume":"56","author":"G Strang","year":"2014","unstructured":"G.\u00a0Strang and S.\u00a0MacNamara, \u201cFunctions of difference matrices are Toeplitz plus Hankel,\u201d SIAM Rev., 56 (2014), no.\u00a03, pp.\u00a0525\u2013546.","journal-title":"SIAM Rev."},{"issue":"4","key":"9332_CR40","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"V.\u00a0Strassen, \u201cGaussian elimination is not optimal,\u201d Numer. Math., 13 (1969), no.\u00a04, pp.\u00a0354\u2013356.","journal-title":"Numer. Math."},{"issue":"53","key":"9332_CR41","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1016\/0024-3795(83)80041-X","volume":"52","author":"V Strassen","year":"1983","unstructured":"V.\u00a0Strassen, \u201cRank and optimal computation of generic tensors,\u201d Linear Algebra Appl., 52\/53 (1983), pp.\u00a0645\u2013685.","journal-title":"Linear Algebra Appl."},{"issue":"376","key":"9332_CR42","first-page":"406","volume":"375","author":"V Strassen","year":"1987","unstructured":"V.\u00a0Strassen, \u201cRelative bilinear complexity and matrix multiplication,\u201d J. Reine Angew. Math., 375\/376 (1987), pp.\u00a0406\u2013443.","journal-title":"J. Reine Angew. Math."},{"key":"9332_CR43","first-page":"184","volume":"264","author":"V Strassen","year":"1973","unstructured":"V.\u00a0Strassen, \u201cVermeidung von Divisionen,\u201d J. Reine Angew. Math., 264 (1973), pp.\u00a0184\u2013202.","journal-title":"J. Reine Angew. Math."},{"key":"9332_CR44","unstructured":"A. L. Toom, \u201cThe complexity of a scheme of functional elements realizing the multiplication of integers,\u201d Dokl. Akad. Nauk SSSR, 150 (1963), pp. 496\u2013498 [English translation: Soviet Math. Dokl., 4 (1963), pp. 714\u2013716]."},{"issue":"1\u20132","key":"9332_CR45","first-page":"85","volume":"123","author":"CF Loan Van","year":"2000","unstructured":"C.\u00a0F.\u00a0Van Loan, \u201cThe ubiquitous Kronecker product,\u201d J. Comput. Appl. Math., 123 (2000), no.\u00a01\u20132, pp.\u00a085\u2013100.","journal-title":"J. Comput. Appl. Math."},{"key":"9332_CR46","first-page":"887","volume":"44","author":"V Vassilevska\u00a0Williams","year":"2012","unstructured":"V.\u00a0Vassilevska\u00a0Williams, \u201cMultiplying matrices faster than Coppersmith\u2013Winograd,\u201d Proc. ACM Symp. Theory Comput. (STOC), 44 (2012), pp.\u00a0887\u2013898.","journal-title":"Proc. ACM Symp. Theory Comput. (STOC)"},{"key":"9332_CR47","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717808","volume-title":"The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods","author":"DS Watkins","year":"2007","unstructured":"D.\u00a0S.\u00a0Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM, Philadelphia, PA, 2007."},{"key":"9332_CR48","doi-asserted-by":"crossref","unstructured":"S. Winograd, \u201cSome bilinear forms whose multiplicative complexity depends on the field of constants,\u201d Math. Syst. Theory, 10 (1976\/77), no. 2, pp. 169\u2013180.","DOI":"10.1007\/BF01683270"},{"key":"9332_CR49","doi-asserted-by":"crossref","unstructured":"K. Ye and L.-H. Lim, \u201cAlgorithms for structured matrix-vector product of optimal bilinear complexity,\u201d Proc. IEEE Inform. Theory Workshop (ITW), 16 (2016), to appear.","DOI":"10.1109\/ITW.2016.7606846"},{"issue":"3","key":"9332_CR50","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s10208-015-9254-z","volume":"16","author":"K Ye","year":"2016","unstructured":"K.\u00a0Ye and L.-H.\u00a0Lim, \u201cEvery matrix is a product of Toeplitz matrices,\u201d Found. Comput. Math., 16 (2016), no.\u00a03, pp.\u00a0577\u2013598.","journal-title":"Found. Comput. Math."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-016-9332-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-016-9332-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-016-9332-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T03:32:34Z","timestamp":1692502354000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-016-9332-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,26]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9332"],"URL":"https:\/\/doi.org\/10.1007\/s10208-016-9332-x","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,26]]}}}