{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T01:34:27Z","timestamp":1672968867754},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSAM Bull."],"published-print":{"date-parts":[[1988,4]]},"abstract":"Two significant developments can be distinguished in the theory of algebraic algorithm design. One is that of fast algorithms in terms of counting the arithmetic operations, such as the asymptotically fast matrix multiplication procedures and related linear algebra algorithms or the asymptotically fast polynomial multiplication procedures and related polynomial manipulation algorithms. The other is to observe the actual bit complexity when such algorithms are performed for concrete fields, in particular the rational numbers. It was discovered in the mid-1960s that for rational polynomial GCD operations the classical algorithm can lead to exponential coefficient size growth. The beautiful theory of subresultants by Collins [7] and Brown & Traub [5] explains, however, that the size growth is not inherent but a consequence of over-simplified rational arithmetic. Similar phenomena were observed for the Gaussian elimination procedure [2], [9].<\/jats:p>","DOI":"10.1145\/43876.43880","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"41-49","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Analysis of the binary complexity of asymptotically fast algorithms for linear system solving"],"prefix":"10.1145","volume":"22","author":[{"given":"Brent","family":"Gregory","sequence":"first","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, NY"}]},{"given":"Erich","family":"Kaltofen","sequence":"additional","affiliation":[{"name":"Rensselaer Polytechnic Institute, Troy, NY"}]}],"member":"320","published-online":{"date-parts":[[1988,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Addison and Wesley","author":"Aho A.","year":"1974","unstructured":"Aho , A. , Hopcroft , J. , and Ullman , J ., The Design and Analysis of Algorithms , Addison and Wesley , Reading, MA , 1974 . Aho, A., Hopcroft, J., and Ullman, J., The Design and Analysis of Algorithms, Addison and Wesley, Reading, MA, 1974."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1968-0226829-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90013-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321664"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321662.321665"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0331751-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321371.321381"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28396"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.033"},{"key":"e_1_2_1_10_1","volume-title":"The Theory of Matrices","author":"Gantmacher F. R.","year":"1960","unstructured":"Gantmacher , F. R. , The Theory of Matrices , Vol. 1 , Chelsea Publ. Co., New York, N. Y. , 1960 . Gantmacher, F. R., The Theory of Matrices, Vol. 1, Chelsea Publ. Co., New York, N. Y., 1960."},{"key":"e_1_2_1_11_1","volume-title":"MIT","author":"Leighton F. T.","year":"1980","unstructured":"Leighton , F. T. , \" Gaussian elimination over the rationals,\" Unpublished Manuscript, Applied Math. Dept ., MIT , 1980 . Leighton, F. T., \"Gaussian elimination over the rationals,\" Unpublished Manuscript, Applied Math. Dept., MIT, 1980."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321784.321787"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804045"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90027-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_1_16_1","volume-title":"F. Ungar Publ","author":"Waerden B. L.","year":"1953","unstructured":"Waerden , B. L. van der , Modern Algebra , F. Ungar Publ . Co., New York , 1953 . Waerden, B. L. van der, Modern Algebra, F. Ungar Publ. Co., New York, 1953."}],"container-title":["ACM SIGSAM Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/43876.43880","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T20:04:14Z","timestamp":1672689854000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/43876.43880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,4]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1988,4]]}},"alternative-id":["10.1145\/43876.43880"],"URL":"http:\/\/dx.doi.org\/10.1145\/43876.43880","relation":{},"ISSN":["0163-5824"],"issn-type":[{"value":"0163-5824","type":"print"}],"subject":[],"published":{"date-parts":[[1988,4]]},"assertion":[{"value":"1988-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}