A numerical absolute primality test for bivariate polynomials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A numerical absolute primality test for bivariate polynomials

Full text

Pdf (1.30 MB)

Source

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

Kihei, Maui, Hawaii, United States

Pages: 217 - 224

Year of Publication: 1997

ISBN:0-89791-875-4

Authors

André Galligo	Laboratoire de Mathématiques, Université de Nice, France
Stephen Watt	IBM T.J. Watson Research Center and INRIA Sophia Antipolis, France

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): 4, Downloads (12 Months): 11, Citation Count: 17

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/258726.258788 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	C. Bajaj , J. Canny , R. Garrity , J. Warren, Factoring rational polynomials over the complexes, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.81-90, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74551]
	2	CHISTOV, A. L., AND GRIGORIEV, D. Y. Subexponential time solving of systems of algebraic equations i. Technical Report E-9 83, Steklov Mathematical Institute, Leningrad, 1983.
	3	Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
	4	Dominique Duval, Absolute factorization of polynomials: a geometric approach, SIAM Journal on Computing, v.20 n.1, p.1-21, Feb. 1991 [doi>10.1137/0220001]
	5	HARMS, J. A bound on the geometric genus of projective varieties. Ann. Sc. Norm. Sup. Pisa Cl.Sci. IV Ser. 8 (1981), 35-68.
	6	J. Håstad , B. Just , J. C. Lagarias , C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM Journal on Computing, v.18 n.5, p.859-881, Oct. 1989 [doi>10.1137/0218059]
	7	Joos Heintz , Malte Sieveking, Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.16-28, July 13-17, 1981
	8	Erich Kaltofen, Fast parallel absolute irreducibility testing, Journal of Symbolic Computation, v.1 n.1, p.57-68, March 1985 [doi>10.1016/S0747-7171(85)80029-8]
	9	Erich Kaltofen, Effective Noether irreducibility forms and applications, Journal of Computer and System Sciences, v.50 n.2, p.274-295, April 1995
	10	N. Karmarkar , Y. N. Lakshman, Approximate polynomial greatest common divisors and nearest singular polynomials, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.35-39, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236892]
	11	LENSTRA, A., LENSTRA JR., H., AND LOVACZ, L. Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515-534.
	12	Victor S. Miller, Factoring polynomials via relation-finding, Symposium proceedings on Theory of computing and systems, p.115-121, June 1992, Haifa, Israel
	13	MUMFORD, D. Algebraic Geometry I--Complex projective varieties. Springer Verlag, 1976.
	14	NOETHER, E. Ein algebraisches Kriterium fiir absolute Irreduzibilit~it. Math. Ann. 85 (1922), 25-33.
	15	R.AGOT, J. F. A method of absolute factorization of polynomials in two variables over Q -- improvement and implementation, Dec. 1994. Preprint, presented as a poster at AAECC'95.
	16	SASAKI, T., Susvgl, M., KOL~,R, M., AND SASAKI, M. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indus. Appl. Math. 8 (1991), 357-375.
	17	TRAGER, B. Integeration of algebraic functions. PhD thesis, MIT, 1984.
	18	TRAVERSO, C. A study on algebraic algorithms: the normalization. In Rend. C. Sere. Mat. Torino (1986), pp. 111-130.
	19	Joachim von zur Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.225-264, Sept. 1985 [doi>10.1016/0022-0000(85)90043-1]
	20	David Y.Y. Yun, On square-free decomposition algorithms, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.26-35, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806320]
	21	ZIPPEL, a. Effective Polynomial Computatwn. Kluwer Acad., 1993.

CITED BY 17

	Tateaki Sasaki, Approximate multivariate polynomial factorization based on zero-sum relations, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.284-291, July 2001, London, Ontario, Canada
	Markus A. Hitz , Erich Kaltofen , Y. N. Lakshman, Efficient algorithms for computing the nearest polynomial with a real root and related problems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.205-212, July 28-31, 1999, Vancouver, British Columbia, Canada
	André Galligo , David Rupprecht, Semi-numerical determination of irreducible branches of a reduced space curve, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.137-142, July 2001, London, Ontario, Canada
	Robert M. Corless , André Galligo , Ilias S. Kotsireas , Stephen M. Watt, A geometric-numeric algorithm for absolute factorization of multivariate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.37-45, July 07-10, 2002, Lille, France
	Robert M. Corless , Mark W. Giesbrecht , Mark van Hoeij , Ilias S. Kotsireas , Stephen M. Watt, Towards factoring bivariate approximate polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.85-92, July 2001, London, Ontario, Canada
	Olivier Cormier , Michael F. Singer , Barry M. Trager , Felix Ulmer, Linear differential operators for polynomial equations, Journal of Symbolic Computation, v.34 n.5, p.355-398, November 2002
	André Galligo , David Rupprecht, Irreducible decomposition of curves, Journal of Symbolic Computation, v.33 n.5, p.661-677, May 2002
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Yuzhen Huang , Wenda Wu , Hans J. Stetter , Lihong Zhi, Pseudofactors of multivariate polynomials, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.161-168, July 2000, St. Andrews, Scotland
	Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain
	Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA
	Kosaku Nagasaka, Towards certified irreducibility testing of bivariate approximate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.192-199, July 07-10, 2002, Lille, France
	Sonia Pérez-Díaz , Juana Sendra , J. Rafael Sendra, Parametrization of approximate algebraic curves by lines, Theoretical Computer Science, v.315 n.2-3, p.627-650, 6 May 2004
	Erich Kaltofen , John P. May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials using singular value decomposition, Journal of Symbolic Computation, v.43 n.5, p.359-376, May, 2008
	André Galligo , Adrien Poteaux, Continuations and monodromy on random riemann surfaces, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan
	Tateaki Sasaki , Yasutaka Ookura, Approximate factorization of polynomials over Z, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan
	Annie Cuyt , Wen-shin Lee, Extracting numerical factors of multivariate polynomials from taylor expansions, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan