On computing greatest common divisors with polynomials given by black boxes for their evaluations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On computing greatest common divisors with polynomials given by black boxes for their evaluations

Full text

Pdf (840 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1995 international symposium on Symbolic and algebraic computation table of contents

Montreal, Quebec, Canada

Pages: 232 - 239

Year of Publication: 1995

ISBN:0-89791-699-9

Authors

Angel Díaz	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York
Erich Kaltofen	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 13, Citation Count: 5

Additional Information:

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/220346.220375 What is a DOI?

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	Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
	2	W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
	3	W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
	4	Chan, K. C., Diaz, D., and Kaltofen, E., "A distributed approach to problem solving in Maple," in Maple V: Mathematics and its Application, Proceedings of the Maple Summer Workshop and Symposium, edited by R. J. Lopez; Birkh/iuser, Boston, pp. 13-21, 1994.
	5	Bruce W. Char , Keith O. Geddes , Gaston H. Gonnet, GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation, Journal of Symbolic Computation, v.7 n.1, p.31-48, Jan. 1989 [doi>10.1016/S0747-7171(89)80004-5]
	6	Angel Díaz , Markus A. Hitz , Erich Kaltofen , A. Lobo , T. Valente, Process Scheduling in DSC and the Large Sparse Linear Systems Challenge, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.66-80, September 15-17, 1993
	7	A. Diaz , E. Kaltofen , K. Schmitz , T. Valente, DSC: a system for distributed symbolic computation, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.323-332, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120772]
	8	Drexler, F. J., "Eine Methode zur Berechnung s/imtlicher LSsungen von Polynomgleichungssystemen," Numer. Math 29, pp. 45-58 (1977). (In German.)
	9	Timothy S. Freeman , Gregory M. Imirzian , Erich Kaltofen , Lakshman Yagati, Dagwood: a system for manipulating polynomials given by straight-line programs, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.218-240, Sept. 1988 [doi>10.1145/44128.214376]
	10	von zur Gathen, J., Karpinski, M., and Shparlinski, I., "Counting curves and their projections," Manuscript, June 1994.
	11	Dima Grigoriev , Marek Karpinski, A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.162-169, May 10-14, 1993
	12	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
	13	Grigoriev, D. Yu. and Lakshman Y. N., "Algorithms for computing sparse shifts for multivariate polynomials," Manuscript, Drexel University, Philadelphia, Pennsylvania, December 1994.
	14	Erich Kaltofen, Sparse Hensel Lifting, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.4-17, April 01-03, 1985
	15	Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
	16	Kaltofen, E., "Factorization of polynomials given by straightline programs," in Randomness and Computation, Advances in Computing Research 5, edited by S. Micali; JAI Press, Greenwhich, Connecticut, pp. 375-412, 1989.
	17	Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
	18	E. Kaltofen , Y. N. Lakshman , J.-M. Wiley, Modular rational sparse multivariate polynomial interpolation, Proceedings of the international symposium on Symbolic and algebraic computation, p.135-139, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96912]
	19	Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
	20	Y. N. Lakshman , B. David Saunders, On computing sparse shifts for univariate polynomials, Proceedings of the international symposium on Symbolic and algebraic computation, p.108-113, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190373]
	21	Y. N. Lakshman , B. David Saunders, Sparse Polynomial Interpolation in Nonstandard Bases, SIAM Journal on Computing, v.24 n.2, p.387-397, April 1995 [doi>10.1137/S0097539792237784]
	22	Yishay Mansour, Randomized Interpolation and Approximation of Sparse Polynomials, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.261-272, July 13-17, 1992
	23	Joel Moses , David Y. Y. Yun, The EZ GCD algorithm, Proceedings of the annual conference, p.159-166, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805698]
	24	Mohamed Omar Rayes , Paul S. Wang , Kenneth Weber, Parallelization of the sparse modular GCD algorithm for multivariate polynomials on shared memory multiprocessors, Proceedings of the international symposium on Symbolic and algebraic computation, p.66-73, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190368]
	25	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	26	Paul S. Wang, The EEZ-GCD algorithm, ACM SIGSAM Bulletin, v.14 n.2, p.50-60, May 1980 [doi>10.1145/1089220.1089228]
	27	Stephen M. Watt , Peter A. Broadbery , Samuel S. Dooley , Pietro Iglio , Scott C. Morrison , Jonathan M. Steinbach , Robert S. Sutor, A first report on the A# compiler, Proceedings of the international symposium on Symbolic and algebraic computation, p.25-31, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190356]
	28	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
	29	Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]

CITED BY 5

	Erich Kaltofen , Michael B. Monagan, On the genericity of the modular polynomial GCD algorithm, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.59-66, July 28-31, 1999, Vancouver, British Columbia, Canada
	Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany
	Ming-Deh A. Huang , Ashwin J. Rao, A black box approach to the algebraic set decomposition problem, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.497-506, May 24-26, 1998, Dallas, Texas, United States
	Erich Kaltofen , Pascal Koiran, On the complexity of factoring bivariate supersparse (Lacunary) polynomials, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.208-215, July 24-27, 2005, Beijing, China
	Howard Cheng , George Labahn, On computing polynomial GCDs in alternate bases, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy