×

zbMATH — the first resource for mathematics

On the efficiency of algorithms for polynomials factoring. (English) Zbl 0348.65045

MSC:
65H05 Numerical computation of solutions to single equations
65G50 Roundoff error
68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
11C08 Polynomials in number theory
11T06 Polynomials over finite fields
Software:
MACSYMA
PDF BibTeX Cite
Full Text: DOI
References:
[1] R. H. RISCH, Symbolic Integration of Elementary Functions, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Manipulation, IBM, R. Tobey (Editor), pp. 133-148.
[2] B. F. CAVINESS, On Canonical Forms and Simplification, Ph.D. Thesis, Carnegie-Mellon Univ., 1967. · Zbl 0193.31302
[3] D. Y. Y. YUN, ”On algorithms for solving systems of polynomial equations,” SIGSAM Bull., No. 27, ACM, New York, September 1973.
[4] B. L. VAN DER WAERDEN, Modern Algebra, Vol. 1, 2nd rev. ed., Springer, Berlin, 1937; English transl., Ungar, New York, 1949. MR 10, 587. · JFM 63.0082.06
[5] D. JORDAN, R. KAIN & L. CLAPP, ”Symbolic factoring of polynomials in several variables,” Comm. ACM, v. 9, 1966. · Zbl 0142.11304
[6] D. R. MUSSER, Algorithms for Polynomial Factorization, Ph.D. Thesis, Univ. of Wisconsin, 1971.
[7] P. S. WANG & L. P. ROTHSCHILD, ”Factoring polynomials over the integers,” SIGSAM Bull., No. 28, ACM, New York, December 1973. · Zbl 0311.10052
[8] Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. · Zbl 0988.94521
[9] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713 – 735. · Zbl 0247.12014
[10] J. D. LIPSON, Chinese Remainder and Interpolation Algorithms, Proc. 2nd SIGSAM Sympos., ACM, New York, 1971.
[11] George E. Collins, Computing multiplicative inverses in \?\?(\?), Math. Comp. 23 (1969), 197 – 200. · Zbl 0191.05605
[12] G. E. COLLINS, Computing Time Analyses of Some Arithmetic and Algebraic Algorithms, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Computation.
[13] Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. · Zbl 0191.18001
[14] J. V. USPENSKY, The Theory of Equations, Chap. 11, McGraw-Hill, New York, 1948.
[15] George E. Collins, The calculation of multivariate polynomial resultants, J. Assoc. Comput. Mach. 18 (1971), 515 – 532. · Zbl 0226.65042
[16] A. Adrian Albert, Fundamental concepts of higher algebra, The University of Chicago Press, Chicago, Ill., 1958. · Zbl 0092.04001
[17] R. T. MOENCK, Studies in Fast Algebraic Algorithms, Ph.D. Thesis, Univ. of Toronto, 1973. · Zbl 0306.68027
[18] Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354 – 356. · Zbl 0185.40101
[19] S. GOLOMB, L. WELCH & A. HALES, ”On the factorization of trinomials over \( {\text{GF}}(2)\),” JPL Memo 20-189 (July 1959)(as referred to in [13]).
[20] Volker Strassen, Die Berechnungskomplexit√§t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math. 20 (1972/73), 238 – 251 (German, with English summary). · Zbl 0251.65036
[21] Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. · Zbl 0193.34701
[22] G. E. COLLINS, The SAC-1 System: An Introduction and Survey, Proc. 2nd SIGSAM Sympos., ACM, New York, 1971.
[23] S. C. JOHNSON & R. L. GRAHAM, ”Problem #7,” SIGSAM Bull., v. 8, No. 1, ACM, New York, February 1974, p. 4.
[24] R. FATEMAN, J. MOSES & P. WANG, ”Solution to problem #7 using MACSYMA,” SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 14-16.
[25] G. E. COLLINS, D. R. MUSSER & M. ROTHSTEIN, ”SAC-1 solution of problem #7,” SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 17-19.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.