Solving systems of nonlinear polynomial equations faster

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving systems of nonlinear polynomial equations faster

Full text

Pdf (814 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation table of contents

Portland, Oregon, United States

Pages: 121 - 128

Year of Publication: 1989

ISBN:0-89791-325-6

Authors

J. F. Canny	Univ. of California, Berkeley
E. Kaltofen	Rensselaer Polytechnic Institute, Troy, NY
L. Yagati	Rensselaer Polytechnic Institute, Troy, NY

Sponsor

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 116, Citation Count: 24

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/74540.74556 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	AGNARSSON, S., KANDRI-RODY, A., KAPVR, D., NARENDRAN, P., and SAUNt)rFtS, B. D., "Complexity of testing whether a polynomial ideal is nontrivial,' Proc. 1984 MACSYMA Users' ConE, pp. 452- 458 (1984).
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	BAjAJ, C., GnRRITY, T., and WARREN, J., "On the applications of multi-equational resultants," Tech. Report CSD-TR-826, Comput. Sci. Dept., Purdue University, November 1988.
	4	BAUR, W. and STRASSEN, V., "The complexity of partial derivatives," Theoretical Comp. Sci. 22, pp. 317- 330 (~983).
	5	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]
	6	BR~.~T, R. P., GUSTAVSOS, F. G., and YVN, D. Y. Y., "Fast solution of Toeplitz systems of equations and computation of Pad6 approximants," J. Algorithms 1, pp. 259-295 (1980).
	7	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]
	8	BUCtqBERCER, B., "GrSbner bases: An algorithmic method in polynomial ideal theory," in Recent Trends in Multidimensional Systems Theory, edited by N. K. Bose; D. Reidel Publ. Comp., Dordrecht (Holland), pp. 184-2321985.
	9	CA~;mLtA, L., GALLIaO, A., and HEINTZ, J., "Some new effectivity bounds in Computational Geometry," Proc. AAECC-6, Springer Leer. Notes in Comp. Sci., to appear (1988).
	10	John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
	11	John F. Canny, Generalized Characteristic Polynomials, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.293-299, July 04-08, 1988
	12	John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
	13	DREXLEa, F. J., "Eine Methode zur Berechnung s~imtlicher L'6sungen yon Polynomgleichungssystemen," Numer. Math. 29, pp. 45-58 (1977). (In Germall.)
	14	GARCIA, C. B. and ZANGWILL, W. I., "Finding all solutions to polynomial systems and other systems of equations," Math. Program. 16, pp. 159-176 (1979).
	15	GPdaORYEV, D. Yu. and CHISTOV, A. L., "Fast decomposition of polynomials into irreducible ones and the solution of systems of algebraic equations," Soviet Math. Dokl. (AMS Translation)29, pp. 380-383 (1984).
	16	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
	17	KALTOFEN, E. and TRAGE~, B., "Computing with polynomials given by black boxes for their evalua. tions: Greatest common divisors, factorization, separation of numerators and denominators," Proc. 29th Annum Syrup. Foundations of Comp. Sci., pp. 296- 305 (1988).
	18	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	19	LAZArtD, D., "Resolution des systemes d'equation algebriques," Theoretical Comput. Sci. 15, pp. 77-110 (1981). (In French).
	20	LI, T.-Y., SAOEP,, T., and YORKE, J. A., "Numerically determining solutions of systems of polynomial equations," AMS Bulletin 18/2, pp. 173-177 (1988).
	21	MACAULAY, F. S., "Algebraic theory of modular systerns," Cambridge Tracts 19, Cambridge, 1916.
	22	J. Renegar, On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials, Mathematics of Operations Research, v.12 n.1, p.121-148, Feb. 1987 [doi>10.1287/moor.12.1.121]
	23	RENAGAR, J., "On the worst case arithmetic complexity of approximating zeros of systems of polynomials," Tech. Rep. 748, School of OR, Cornell Univ., 1987b.
	24	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]
	25	SCHSNHAaE, A., "Schnelle Multiplikation yon Polynomen ilber K5rpern der Charakteristik 2," Acta Inf. 7, pp. 395-398 (1977). (In German).
	26	VAN DER WAERDEN, $. L., Modern Algebra; F. Ungar Publ. Co., New York, 1953.
	27	D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
	28	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]
	29	ZULEHNER, W., "A simple homotopy method for determining all isolated solutions to polynomial systems," Math. Comp. 50/181, pp. 167-177 (1988).

CITED BY 24

	Hoon Hong , Manfred Minimair, Sparse resultant of composed polynomials I^* mixed-unmixed case, Journal of Symbolic Computation, v.33 n.4, p.447-465, April 2002
	Didier Bondyfalat , Bernard Mourrain , Victor Y. Pan, Controlled iterative methods for solving polynomial systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.252-259, August 13-15, 1998, Rostock, Germany
	Victor Shoup, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.14-21, July 15-17, 1991, Bonn, West Germany
	Dinesh Manocha, Computing selected solutions of polynomial equations, Proceedings of the international symposium on Symbolic and algebraic computation, p.1-8, July 20-22, 1994, Oxford, United Kingdom
	J. Maurice Rojas, On the complexity of diophantine geometry in low dimensions (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.527-536, May 01-04, 1999, Atlanta, Georgia, United States
	Ioannis Z. Emiris , Victor Y. Pan, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, Journal of Symbolic Computation, v.33 n.4, p.393-413, April 2002
	Ioanis Z. Emiris , Victor Y. Pan, The structure of sparse resultant matrices, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.189-196, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	A. Bostan , G. Lecerf , É. Schost, Tellegen's principle into practice, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.37-44, August 03-06, 2003, Philadelphia, PA, USA
	Joris Van der Hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, v.34 n.6, p.479-542, December 2002
	Erich Kaltofen , Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.398-406, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Manfred Minimair, Sparse Resultant under Vanishing Coefficients, Journal of Algebraic Combinatorics: An International Journal, v.18 n.1, p.53-73, July 2003
	Manfred Minimair, Factoring sparse resultants of linearly combined polynomials, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.207-214, August 03-06, 2003, Philadelphia, PA, USA
	Manfred Minimair, Dense resultant of composed polynomials mixed-mixed case, Journal of Symbolic Computation, v.36 n.6, p.825-834, December 2003
	Manfred Minimair, Sparse resultant of composed polynomials II unmixed--mixed case, Journal of Symbolic Computation, v.33 n.4, p.467-478, April 2002
	Joris van der Hoeven, The truncated fourier transform and applications, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.290-296, July 04-07, 2004, Santander, Spain
	Chionh Eng Wee , Ronald N. Goldman, Elimination and Resultants - Part 1: Elimination and Bivariate Resultants, IEEE Computer Graphics and Applications, v.15 n.1, p.69-77, January 1995
	V. Y. Pan, Concurrent Iterative Algorithm for Toeplitz-like Linear Systems, IEEE Transactions on Parallel and Distributed Systems, v.4 n.5, p.592-600, May 1993
	Alin Bostan , Éric Schost, On the complexities of multipoint evaluation and interpolation, Theoretical Computer Science, v.329 n.1-3, p.223-235, 13 December 2004
	Ioannis Z. Emiris , Victor Y. Pan, Improved algorithms for computing determinants and resultants, Journal of Complexity, v.21 n.1, p.43-71, February 2005
	Manfred Minimair, Resultants of skewly composed polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Y. N. Lakshman, On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.555-563, May 13-17, 1990, Baltimore, Maryland, United States
	Alin Bostan , Claude-Pierre Jeannerod , Éric Schost, Solving toeplitz- and vandermonde-like linear systems with large displacement rank, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Alin Bostan , Bruno Salvy , Éric Schost, Power series composition and change of basis, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, July 20-23, 2008, Linz/Hagenberg, Austria
	Alin Bostan , Claude-Pierre Jeannerod , Éric Schost, Solving structured linear systems with large displacement rank, Theoretical Computer Science, v.407 n.1-3, p.155-181, November, 2008