Implementing a polynomial factorization and GCD package

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementing a polynomial factorization and GCD package

Full text

Pdf (383 KB)

Source

Symposium on Symbolic and Algebraic Manipulation archive
Proceedings of the fourth ACM symposium on Symbolic and algebraic computation table of contents

Snowbird, Utah, United States

Pages: 109 - 116

Year of Publication: 1981

ISBN:0-89791-047-8

Authors

P. M. A. Moore
A. C. Norman

Sponsor

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 6, Citation Count: 11

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800206.806379 What is a DOI?

ABSTRACT

This paper describes the construction of a rational function package where the GCD and factorization routines are well integrated and consistent with each other and both use state of the art algorithms. The work represents an exercise in producing a service rather than an experimental piece of code, where portability, reliability and clear readable code are important aims in addition to the obvious desire for speed. Measurements on the initial version of our package showed that even though it was based on the best of previously published methods its performance was uneven. The causes of the more notable bottle necks and the steps we took to avoid them are explained here and illustrate how apparently very fine details of coding can sometimes have gross effects on a system's overall behaviour.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Damerell, M. Private Communication
	2	Arthur Norman, Towards a REDUCE solution to SIGSAM problem 7, ACM SIGSAM Bulletin, v.12 n.4, p.14-18, November 1978 [doi>10.1145/1088276.1088278]
	3	David Rea Musser, Algorithms for polynomial factorization., 1971
	4	Wang, P.S., "An Improved Multivariable Polynomial Factorising Algorithm", Math. Comp. 32(1978) pp. 1215-1231.
	5	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
	6	A. C. Norman , P. M. A. Moore, The initial design of a vector based algebra system, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.258-265, June 01, 1979

CITED BY 11

	Paul S. Wang, Parallel univariate p-adic lifting on shared-memory multiprocessors, Papers from the international symposium on Symbolic and algebraic computation, p.168-176, July 27-29, 1992, Berkeley, California, United States
	James H. Davenport , Barry M. Trager, Factorization over finitely generated fields, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.200-205, August 05-07, 1981, Snowbird, Utah, United States
	Michael Lucks, A fast implementation of polynomial factorization, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.228-232, July 21-23, 1986, Waterloo, Ontario, Canada
	Masayuki Noro , Taku Takeshima, Risa/Asir—a computer algebra system, Papers from the international symposium on Symbolic and algebraic computation, p.387-396, July 27-29, 1992, Berkeley, California, United States
	J. A. Abbott , R. J. Bradford , J. H. Davenport, The Bath algebraic number package, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.250-253, July 21-23, 1986, Waterloo, Ontario, Canada
	P. S. Wang, Parallel univariate polynomial factorization on shared-memory multiprocessors, Proceedings of the international symposium on Symbolic and algebraic computation, p.145-151, August 20-24, 1990, Tokyo, Japan
	James H. Davenport, Fast reduce: the trade-off between efficiency and generality, ACM SIGSAM Bulletin, v.16 n.1, p.8-11, February 1982
	Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982
	Arthur C. Norman , Paul S. Wang, A comparison of the Vaxima and Reduce factorization packages, ACM SIGSAM Bulletin, v.17 n.1, p.28-30, February 1983
	J. A. Abbott , R. J. Bradford , J. H. Davenport, A remark on factorisation, ACM SIGSAM Bulletin, v.19 n.2, p.31-33, May 1985
	James H. Davenport, What do we want from a high-level language?, ACM SIGSAM Bulletin, v.16 n.4, p.6-9, November 1982