{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T13:48:57Z","timestamp":1724852937678},"reference-count":56,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":1755,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2008,11]]},"DOI":"10.1016\/j.tcs.2008.05.014","type":"journal-article","created":{"date-parts":[[2008,6,4]],"date-time":"2008-06-04T12:05:03Z","timestamp":1212581103000},"page":"155-181","source":"Crossref","is-referenced-by-count":26,"title":["Solving structured linear systems with large displacement rank"],"prefix":"10.1016","volume":"407","author":[{"given":"Alin","family":"Bostan","sequence":"first","affiliation":[]},{"given":"Claude-Pierre","family":"Jeannerod","sequence":"additional","affiliation":[]},{"given":"\u00c9ric","family":"Schost","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0377-0427(92)90039-Z","article-title":"A reliable method for computing M-Pad\u00e9 approximants on arbitrary staircases","volume":"40","author":"Beckermann","year":"1992","journal-title":"J. Comput. Appl. Math."},{"issue":"3","key":"10.1016\/j.tcs.2008.05.014_b2","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0895479892230031","article-title":"A uniform approach for the fast computation of matrix-type Pad\u00e9 approximants","volume":"15","author":"Beckermann","year":"1994","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b3","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/S0895479897326912","article-title":"Fraction-free computation of matrix rational interpolants and matrix GCDs","volume":"22","author":"Beckermann","year":"2000","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/j.tcs.2008.05.014_b4","series-title":"20th Annual ACM Symp. Theory Comp.","article-title":"A deterministic algorithm for sparse multivariate polynomial interpolation","author":"Ben-Or","year":"1988"},{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.04.009","article-title":"Factoring into coprimes in essentially linear time","volume":"54","author":"Bernstein","year":"2005","journal-title":"J. Algorithms"},{"key":"10.1016\/j.tcs.2008.05.014_b6","series-title":"Polynomial and Matrix Computations","volume":"vol. 1","author":"Bini","year":"1994"},{"key":"10.1016\/j.tcs.2008.05.014_b7","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0024-3795(80)90161-5","article-title":"Asymptotically fast solution of Toeplitz and related systems of linear equations","volume":"34","author":"Bitmead","year":"1980","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/j.tcs.2008.05.014_b8","series-title":"ISSAC\u201907","first-page":"33","article-title":"Solving Toeplitz- and Vandermonde-like linear systems with large displacement rank","author":"Bostan","year":"2007"},{"key":"10.1016\/j.tcs.2008.05.014_b9","series-title":"ISSAC\u201903","first-page":"37","article-title":"Tellegen\u2019s principle into practice","author":"Bostan","year":"2003"},{"key":"10.1016\/j.tcs.2008.05.014_b10","series-title":"ISSAC\u201989","first-page":"121","article-title":"Solving systems of non-linear polynomial equations faster","author":"Canny","year":"1989"},{"issue":"7","key":"10.1016\/j.tcs.2008.05.014_b11","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","article-title":"On fast multiplication of polynomials over arbitrary algebras","volume":"28","author":"Cantor","year":"1991","journal-title":"Acta Inform."},{"key":"10.1016\/j.tcs.2008.05.014_b12","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/j.camwa.2003.09.028","article-title":"An efficient solution for Cauchy-like systems of linear equations","volume":"48","author":"Chen","year":"2004","journal-title":"Comput. Math. Appl."},{"issue":"3","key":"10.1016\/j.tcs.2008.05.014_b13","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith","year":"1990","journal-title":"J. Symbolic. Comput."},{"issue":"4","key":"10.1016\/j.tcs.2008.05.014_b14","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","article-title":"A probabilistic remark on algebraic program testing","volume":"7","author":"DeMillo","year":"1978","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.tcs.2008.05.014_b15","series-title":"ISSAC\u201902","first-page":"63","article-title":"Finite field linear algebra subroutines","author":"Dumas","year":"2002"},{"key":"10.1016\/j.tcs.2008.05.014_b16","series-title":"ISSAC\u201906","first-page":"63","article-title":"Solving sparse rational linear systems","author":"Eberly","year":"2006"},{"key":"10.1016\/j.tcs.2008.05.014_b17","series-title":"ISSAC\u201907","first-page":"143","article-title":"Faster inversion and other black box matrix computations using efficient block projections","author":"Eberly","year":"2007"},{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b18","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0024-3795(93)90431-M","article-title":"An inversion formula and fast algorithms for Cauchy-Vandermonde matrices","volume":"183","author":"Finck","year":"1993","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/j.tcs.2008.05.014_b19","unstructured":"S. Gao, V.M. Rodrigues, J. Stroomer, Gr\u00f6bner basis structure of finite sets of points, Preprint, 2003"},{"issue":"4","key":"10.1016\/j.tcs.2008.05.014_b20","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1023\/A:1018981505752","article-title":"Polynomial interpolation in several variables","volume":"12","author":"Gasca","year":"2000","journal-title":"Adv. Comput. Math."},{"key":"10.1016\/j.tcs.2008.05.014_b21","series-title":"Modern Computer Algebra","author":"von zur Gathen","year":"2003"},{"issue":"3","key":"10.1016\/j.tcs.2008.05.014_b22","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01272074","article-title":"Computing Frobenius maps and factoring polynomials","volume":"2","author":"von zur Gathen","year":"1992","journal-title":"Comput. Complexity"},{"key":"10.1016\/j.tcs.2008.05.014_b23","series-title":"ISSAC\u201903","first-page":"135","article-title":"On the complexity of polynomial matrix computations","author":"Giorgi","year":"2003"},{"key":"10.1016\/j.tcs.2008.05.014_b24","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0024-3795(94)90189-9","article-title":"Complexity of multiplication with vectors for structured matrices","volume":"202","author":"Gohberg","year":"1994","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b25","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0196-6774(82)90007-4","article-title":"A generalization of the fast LUP matrix decomposition algorithm and applications","volume":"3","author":"Ibarra","year":"1982","journal-title":"J. Algorithms"},{"issue":"2","key":"10.1016\/j.tcs.2008.05.014_b26","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/0022-247X(79)90124-0","article-title":"Displacement ranks of matrices and linear equations","volume":"68","author":"Kailath","year":"1979","journal-title":"J. Math. Anal. Appl."},{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b27","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1145\/42267.45069","article-title":"Greatest common divisors of polynomials given by straight-line programs","volume":"35","author":"Kaltofen","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2008.05.014_b28","series-title":"ISSAC\u201994","first-page":"297","article-title":"Asymptotically fast solution of Toeplitz-like singular linear systems","author":"Kaltofen","year":"1994"},{"issue":"210","key":"10.1016\/j.tcs.2008.05.014_b29","first-page":"777","article-title":"Analysis of Coppersmith\u2019s block Wiedemann algorithm for the parallel solution of sparse linear systems","volume":"64","author":"Kaltofen","year":"1995","journal-title":"Math. Comp."},{"key":"10.1016\/j.tcs.2008.05.014_b30","series-title":"ISSAC\u201988","first-page":"467","article-title":"Improved sparse multivariate polynomial interpolation algorithms","volume":"vol. 358","author":"Kaltofen","year":"1988"},{"key":"10.1016\/j.tcs.2008.05.014_b31","series-title":"AAECC-9","first-page":"29","article-title":"On Wiedemann\u2019s method of solving sparse linear systems","volume":"vol. 539","author":"Kaltofen","year":"1991"},{"issue":"2\u20133","key":"10.1016\/j.tcs.2008.05.014_b32","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1016\/j.tcs.2004.01.004","article-title":"The aggregation and cancellation techniques as a practical tool for faster matrix multiplication","volume":"315","author":"Kaporin","year":"2004","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b33","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1137\/0219006","article-title":"The inverses of block Hankel and block Toeplitz matrices","volume":"19","author":"Labahn","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2008.05.014_b34","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/0024-3795(92)90393-O","article-title":"On practical algorithms for accelerated matrix multiplication","volume":"162\u2013164","author":"Laderman","year":"1992","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/j.tcs.2008.05.014_b35","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0747-7171(85)80035-3","article-title":"Ideal bases and primary decomposition: The case of two variables","volume":"1","author":"Lazard","year":"1985","journal-title":"J. Symbolic. Comput."},{"issue":"177","key":"10.1016\/j.tcs.2008.05.014_b36","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1090\/S0025-5718-1987-0866113-7","article-title":"Speeding the Pollard and elliptic curve methods of factorization","volume":"48","author":"Montgomery","year":"1987","journal-title":"Math. Comp."},{"key":"10.1016\/j.tcs.2008.05.014_b37","unstructured":"M. Morf, Fast algorithms for multivariable systems, Ph.D. Thesis, Stanford University, 1974"},{"key":"10.1016\/j.tcs.2008.05.014_b38","doi-asserted-by":"crossref","unstructured":"M. Morf, Doubling algorithms for Toeplitz and related equations, in: IEEE Conference on Acoustics, Speech, and Signal Processing, 1980, pp. 954\u2013959","DOI":"10.1109\/ICASSP.1980.1171074"},{"issue":"1","key":"10.1016\/j.tcs.2008.05.014_b39","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s002000000037","article-title":"On short multiplications and divisions","volume":"11","author":"Mulders","year":"2000","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"key":"10.1016\/j.tcs.2008.05.014_b40","series-title":"ESA 2004","first-page":"544","article-title":"Fast multipoint evaluation of bivariate polynomials","volume":"vol. 3222","author":"N\u00fcsken","year":"2004"},{"key":"10.1016\/j.tcs.2008.05.014_b41","series-title":"ISSAC\u201989","first-page":"34","article-title":"On some computations with dense structured matrices","author":"Pan","year":"1989"},{"issue":"191","key":"10.1016\/j.tcs.2008.05.014_b42","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1090\/S0025-5718-1990-1023051-7","article-title":"On computations with dense structured matrices","volume":"55","author":"Pan","year":"1990","journal-title":"Math. Comp."},{"issue":"3","key":"10.1016\/j.tcs.2008.05.014_b43","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0898-1221(92)90215-4","article-title":"Parametrization of Newton\u2019s iteration for computations with structured matrices and applications","volume":"24","author":"Pan","year":"1992","journal-title":"Comput. Math. Appl."},{"key":"10.1016\/j.tcs.2008.05.014_b44","series-title":"SODA\u201900","first-page":"953","article-title":"Nearly optimal computations with structured matrices","author":"Pan","year":"2000"},{"key":"10.1016\/j.tcs.2008.05.014_b45","series-title":"Structured Matrices and Polynomials","author":"Pan","year":"2001"},{"issue":"3","key":"10.1016\/j.tcs.2008.05.014_b46","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1137\/S089547980238627X","article-title":"Inversion of displacement operators","volume":"24","author":"Pan","year":"2003","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/j.tcs.2008.05.014_b47","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0024-3795(00)00041-0","article-title":"Superfast algorithms for Cauchy-like matrix computations and extensions","volume":"310","author":"Pan","year":"2000","journal-title":"Linear Algebra Appl."},{"key":"10.1016\/j.tcs.2008.05.014_b48","series-title":"Computer algebra in scientific computing: CASC\u201999","first-page":"323","article-title":"Superfast computations with singular structured matrices over abstract fields","author":"Pan","year":"1999"},{"key":"10.1016\/j.tcs.2008.05.014_b49","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","article-title":"Schnelle Multiplikation gro\u00dfer Zahlen","volume":"7","author":"Sch\u00f6nhage","year":"1971","journal-title":"Computing"},{"issue":"4","key":"10.1016\/j.tcs.2008.05.014_b50","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz","year":"1980","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2008.05.014_b51","unstructured":"A. Storjohann, Algorithms for matrix canonical forms, Ph.D. Thesis, ETH, Z\u00fcrich, 2000"},{"key":"10.1016\/j.tcs.2008.05.014_b52","unstructured":"A. Storjohann, Notes on computing minimal approximant bases, Technical report, Symbolic Computation Group, University of Waterloo, 2006"},{"key":"10.1016\/j.tcs.2008.05.014_b53","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen","year":"1969","journal-title":"Numer. Math."},{"key":"10.1016\/j.tcs.2008.05.014_b54","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/BF02141952","article-title":"A general module theoretic framework for vector M-Pad\u00e9 and matrix rational interpolation","volume":"3","author":"Van Barel","year":"1992","journal-title":"Numer. Algorithms"},{"key":"10.1016\/j.tcs.2008.05.014_b55","series-title":"EUROSAM\u2019 79","article-title":"Probabilistic algorithms for sparse polynomials","volume":"vol. 72","author":"Zippel","year":"1979"},{"issue":"3","key":"10.1016\/j.tcs.2008.05.014_b56","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","article-title":"Interpolating polynomials from their values","volume":"9","author":"Zippel","year":"1990","journal-title":"J. Symbolic. Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397508003940?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397508003940?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2018,12,27]],"date-time":"2018-12-27T21:58:08Z","timestamp":1545947888000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397508003940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":56,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["S0304397508003940"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2008.05.014","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2008,11]]}}}