{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:42:01Z","timestamp":1776829321034,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540167839","type":"print"},{"value":"9783540399094","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/bfb0016236","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"93-112","source":"Crossref","is-referenced-by-count":44,"title":["Parallel arithmetic computations: A survey"],"prefix":"10.1007","author":[{"given":"Joachim","family":"von zur Gathen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Lower bounds for algebraic computation trees. Proc. 15th Ann. ACM Symp. Theory of Computing, Boston MA, 1983, 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, E. Feig, D. Kozen, and P. Tiwari, A fast parallel algorithm for determining all roots of a polynomial with real roots. To appear in Proc. 18th Ann. ACM Symp. Theory of Computing, Berkeley CA, 1986.","DOI":"10.1145\/12130.12165"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, D. Kozen, and J. Reif, The complexity of elementary algebra and geometry. Proc. 16th Ann. ACM Symp. Theory of Computing, Washington DC, 1984, 457\u2013464.","DOI":"10.1145\/800057.808712"},{"key":"7_CR4","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1137\/0213019","volume":"13","author":"D. Bini","year":"1984","unstructured":"D. Bini, Parallel solution of certain Toeplitz linear systems. SIAM J. Computing 13 (1984), 268\u2013276.","journal-title":"SIAM J. Computing"},{"key":"7_CR5","unstructured":"D. Bini and V. Pan, Fast parallel algorithms for polynomial division over arbitrary field of constants. Nota interna, Dipartimento di Informatica, Universit\u00e0 di Pisa, 1984."},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"D. Bini and V. Pan, Polynomial division and its computational complexity. Tech. Rep. TR 86-2, Computer Science Department, SUNY Albany NY, 1986.","DOI":"10.1016\/0885-064X(86)90001-4"},{"key":"7_CR7","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","volume":"18","author":"S.J. Berkowitz","year":"1984","unstructured":"S.J. Berkowitz, On computing the determinant in small parallel time using a small number of processors. Information Processing Letters 18 (1984), 147\u2013150.","journal-title":"Information Processing Letters"},{"key":"7_CR8","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"A. Borodin, On relating time and space to size and depth. SIAM J. Comput. 6 (1977), 733\u2013744.","journal-title":"SIAM J. Comput."},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0019-9958(82)90766-5","volume":"52","author":"A. Borodin","year":"1982","unstructured":"A. Borodin, J. von zur Gathen, and J. Hopcroft, Fast parallel matrix and GCD computations. Information and Control 52 (1982), 241\u2013256.","journal-title":"Information and Control"},{"key":"7_CR10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"R.P. Brent, The parallel evaluation of general arithmetic expressions. J. ACM 21 (1974), 201\u2013206.","journal-title":"J. ACM"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"A.L. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. Proc. Int. Conf. Foundations of Computation Theory, Springer Lecture Notes in Computer Science 199, 1985, 63\u201369.","DOI":"10.1007\/BFb0028792"},{"key":"7_CR12","first-page":"380","volume":"29","author":"A.L. Chistov","year":"1984","unstructured":"A.L. Chistov and D.Yu. Grigoryev, Fast decomposition of polynomials into irreducible ones and the solution of systems of algebraic equations. Soviet Math. Dokl 29 (1984), 380\u2013383.","journal-title":"Soviet Math. Dokl"},{"key":"7_CR13","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A. Cook, A taxonomy of problems with fast parallel algorithms. Information and Control 64 (1985), 2\u201322.","journal-title":"Information and Control"},{"key":"7_CR14","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L. Csanky","year":"1976","unstructured":"L. Csanky, Fast parallel matrix inversion algorithms. SIAM J. Comput. 5 (1976), 618\u2013623.","journal-title":"SIAM J. Comput."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"W. Eberly, Very fast parallel matrix and polynomial arithmetic. Proc. 25th Ann. IEEE Symp. Foundations of Computer Science, Singer Island FL, 1984, 21\u201330. Tech. Rep. #178\/85, Department of Computer Science, University of Toronto.","DOI":"10.1109\/SFCS.1984.715897"},{"key":"7_CR16","unstructured":"W. Eberly, Very fast parallel polynomial arithmetic. Preprint, University of Toronto, Canada, 1986."},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"F. Fich and M. Tompa, The parallel complexity of exponentiating polynomials over finite fields, Proc. 17th Ann. ACM Sympos. Theory of Computing, Providence RI, 1985, 38\u201347.","DOI":"10.1145\/22145.22150"},{"key":"7_CR18","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, San Francisco, 1979."},{"key":"7_CR19","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1137\/0213050","volume":"13","author":"J. Gathen von zur","year":"1984","unstructured":"J. von zur Gathen [1984a], Parallel algorithms for algebraic problems. SIAM J. Comput. 13 (1984), 802\u2013824.","journal-title":"SIAM J. Comput."},{"key":"7_CR20","unstructured":"J. von zur Gathen [1984b], Computing powers in parallel. Proc. 25th Ann. IEEE Symp. Foundations of Computer Science, Singer Island FL, 1984, 31\u201336."},{"key":"7_CR21","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0022-0000(85)90043-1","volume":"31","author":"J. Gathen von zur","year":"1985","unstructured":"J. von zur Gathen [1985a], Irreducibility of multivariate polynomials. J. Computer System Sciences 31 (1985), 225\u2013264.","journal-title":"J. Computer System Sciences"},{"key":"7_CR22","unstructured":"J. von zur Gathen [1985b], Factoring polynomials and primitive elements for special primes. Preprint, University of Toronto, April 1985."},{"key":"7_CR23","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1137\/0215030","volume":"15","author":"J. Gathen von zur","year":"1986","unstructured":"J. von zur Gathen, Representations and parallel computations for rational functions. SIAM J. Comput 15 (1986), 432\u2013452.","journal-title":"SIAM J. Comput"},{"key":"7_CR24","unstructured":"J. von zur Gathen and G. Seroussi, Boolean circuits versus arithmetic circuits. To appear in Proc. 6th Int. Conf. Computer Science, Santiago, Chile, 1986."},{"key":"7_CR25","unstructured":"R. Glover, Simultaneous Pad\u00e9 approximation. M. Sc. Thesis, University of Toronto, September 1984."},{"key":"7_CR26","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/0208010","volume":"8","author":"L. Hyafil","year":"1979","unstructured":"L. Hyafil, On the parallel evaluation of multivariate polynomials. SIAM J. Computing 8 (1979), 120\u2013123.","journal-title":"SIAM J. Computing"},{"key":"7_CR27","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0020-0190(80)90042-3","volume":"11","author":"O.H. Ibarra","year":"1980","unstructured":"O.H. Ibarra, S. Moran and L.E. Rosier, A note on the parallel complexity of computing the rank of order n matrices. Information Processing Letters 11 (1980), 162.","journal-title":"Information Processing Letters"},{"key":"7_CR28","first-page":"1","volume-title":"Parallel computations","author":"T.L. Jordan","year":"1982","unstructured":"T.L. Jordan, A guide to parallel computation and some Cray-1 experiences. In: Parallel computations, ed. by G. Rodrigues, Academic Press, New York, 1982, 1\u201350."},{"key":"7_CR29","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0747-7171(85)80029-8","volume":"1","author":"E. Kaltofen","year":"1985","unstructured":"E. Kaltofen, Fast parallel absolute irreducibility testing. J. Symb. Computation 1 (1985), 57\u201367.","journal-title":"J. Symb. Computation"},{"key":"7_CR30","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, Uniform closure properties of p-computable functions. To appear in Proc. 18th Ann. ACM Symp. Theory of Computing, Berkeley CA, 1986.","DOI":"10.1145\/12130.12163"},{"key":"7_CR31","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, M. Krishnamoorthy, and B.D. Saunders [1986a], Fast parallel computation of Hermite and Smith forms of polynomial matrices. To appear in SIAM J. Algebraic and Discrete Methods, 1986.","DOI":"10.1137\/0608057"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"E. Kaltofen, M. Krishnamoorthy, and B.D. Saunders [1986b], Fast parallel algorithms for similarity of matrices. To appear in Proc. ACM Symp. Symbolic and Algebraic Computation, Waterloo, Canada, 1986.","DOI":"10.1145\/32439.32452"},{"key":"7_CR33","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1145\/321941.321945","volume":"23","author":"H.T. Kung","year":"1976","unstructured":"H.T. Kung, New algorithms and lower bounds for the parallel evaluation of certain rational expressions and recurrences. J. ACM 23 (1976), 252\u2013261.","journal-title":"J. ACM"},{"key":"7_CR34","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"A.K. Lenstra, H.W. Lenstra, and L. Lov\u00e1sz, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515\u2013534.","journal-title":"Math. Ann."},{"key":"7_CR35","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E.W. Mayr","year":"1982","unstructured":"E.W. Mayr and A.R. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. Math. 46 (1982), 305\u2013329.","journal-title":"Adv. Math."},{"key":"7_CR36","doi-asserted-by":"crossref","unstructured":"G.L. Miller, E. Kaltofen, and V. Ramachandran, Efficient parallel evaluation of straight-line code. To appear in Proc. Aegean Workshop on Computing, VLSI Algorithms and Architectures, Attica, Greece, 1986.","DOI":"10.1007\/3-540-16766-8_21"},{"key":"7_CR37","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1145\/321958.321973","volume":"23","author":"D.E. Muller","year":"1976","unstructured":"D.E. Muller and F.P. Preparata, Restructuring of arithmetic expressions for parallel evaluation. J. ACM 23 (1976), 534\u2013543.","journal-title":"J. ACM"},{"key":"7_CR38","unstructured":"K. Mulmuley, Computing the rank of a matrix over an arbitrary field is in NC (2). To appear in Proc. 18th Ann. ACM Symp. Theory of Computing, Berkeley CA, 1986."},{"key":"7_CR39","doi-asserted-by":"crossref","unstructured":"J. Reif, Logarithmic depth circuits for algebraic functions. Proc. 24th Ann. IEEE Symp. Foundations of Computer Science, Tucson AZ, 1983, 138\u2013145.","DOI":"10.1109\/SFCS.1983.29"},{"key":"7_CR40","first-page":"182","volume":"264","author":"V. Strassen","year":"1973","unstructured":"V. Strassen, Vermeidung von Divisionen. J. reine u. angew. Math. 264 (1973), 182\u2013202.","journal-title":"J. reine u. angew. Math."},{"key":"7_CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0212001","volume":"12","author":"V. Strassen","year":"1983","unstructured":"V. Strassen, The Computational Complexity of Continued Fractions. SIAM J. Comput. 12 (1983), 1\u201327.","journal-title":"SIAM J. Comput."},{"key":"7_CR42","volume-title":"Perspectives in Mathematics","author":"V. Strassen","year":"1984","unstructured":"V. Strassen, Algebraische Berechnungskomplexit\u00e4t. In: Perspectives in Mathematics, Birkh\u00e4user Verlag, Basel, 1984."},{"key":"7_CR43","doi-asserted-by":"crossref","unstructured":"L.G. Valiant, Completeness classes in algebra. Proc. 11th Ann. ACM Symp. Theory of Computing, Atlanta GA, 1979, 249\u2013261.","DOI":"10.1145\/800135.804419"},{"key":"7_CR44","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/0020-0190(80)90033-2","volume":"11","author":"L.G. Valiant","year":"1980","unstructured":"L.G. Valiant, Computing multivariate polynomials in parallel. Information Processing Letters 11 (1980), 44\u201345, and 12, 54.","journal-title":"Information Processing Letters"},{"key":"7_CR45","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"L. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff, Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12 (1983), 641\u2013644.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T20:40:31Z","timestamp":1586551231000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167839","9783540399094"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/bfb0016236","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}