Controlled iterative methods for solving polynomial systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Controlled iterative methods for solving polynomial systems

Full text

Pdf (379 KB)

Source

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

Rostock, Germany

Pages: 252 - 259

Year of Publication: 1998

ISBN:1-58113-002-3

Authors

Didier Bondyfalat	INRIA, SAGA, 2004 route des Lucioles, B.P. 93, 06902 Sophia Antipolis, France
Bernard Mourrain	INRIA, SAGA, 2004 route des Lucioles, B.P. 93, 06902 Sophia Antipolis, France
Victor Y. Pan	Dept. of Math. and Computer Science, Lehman College, City Univ. of New York, Bronx, NY

Sponsors

German Comp Soc : GI - Gesellshaft for Informatik
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): 17, Citation Count: 3

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/281508.281629 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	AUZINGER, W., AND STETTER, H. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Proc. Intern. Conf. on Numerical Math. (1988), vol. 86 of Int. Series of Numerical Math., Birkh/iuser, pp. 11-30.
	2	Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
	3	John F. Canny , Ioannis Z. Emiris, An Efficient Algorithm for the Sparse Mixed Resultant, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.89-104, May 10-14, 1993
	4	J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74556]
	5	Robert M. Corless , Patrizia M. Gianni , Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.133-140, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258767]
	6	Cox, D., LITTLE, J., AND O'SHEA, D. Ideals, Varieties, and Algorithms: An Introduction to Cornputational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, 1992.
	7	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 [doi>10.1145/258726.258779]
	8	Ioannis Z. Emiris , Ashutosh Rege, Monomial bases and polynomial system solving (extended abstract), Proceedings of the international symposium on Symbolic and algebraic computation, p.114-122, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190374]
	9	EMSALEM, J. G6om6trie des points 6pais. Bull. Soc. Math. France 106 (1978), 399-416.
	10	Olivier Faugeras, Three-dimensional computer vision: a geometric viewpoint, MIT Press, Cambridge, MA, 1993
	11	GELFAND, I., KAPRANOV, M., AND ZELEVINSKY, A. Discrirninants, Resultants and Multidimensional Deterrninants. Birkh/iuser, Boston-Basel-Berlin, 1994.
	12	GIANNI, P., AND TRAGER, B. Computations with approximate ideals. Preprint, SNAP'96, 1997.
	13	GIUSTI, M., AND HEINTZ, J. La d6termination des points isol6s et de la dimension d'une vari6t6 algebrique peut se faire en temps polynomial. In Proc. Intern. Meeting on Commutative Algebra (Cortona, 1991), vol. XXXIV of Syrnp. Mathernatica, pp. 216-255.
	14	GOLUB, G. H., AND VAN LOAN, C. F. Matrix Cornputations, Johns Hopkins Univ. Press, Baltimore, Maryland (1996) (third edition).
	15	LAZARD, D. R~solution des syst~mes d'~quations alg~briques. Theor. Cornp. Science 15 (1981), 77-110.
	16	MACAULAY, F. Some formulae in elimination. Proc. London Math. Soc. 1, 33 (1902), 3-27.
	17	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 [doi>10.1145/190347.190349]
	18	Dinesh Manocha , John F. Canny, Multipolynomial resultant algorithms, Journal of Symbolic Computation, v.15 n.2, p.99-122, Feb. 1993 [doi>10.1006/jsco.1993.1009]
	19	Maria Grazia Marinari , Teo Mora , Hans Michael Möller, Gröbner duality and multiplicities in polynomial system solving, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.167-179, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220368]
	20	MOUaaAIN, B. Isolated points, duality and residues. J. Pure Applied Algebra. Special Issue on Algorithms for Algebra 117 ~ 118 (May 1997), 469-494.
	21	MOURRAIN, B. Solving polynomial systems by matrix computations. Manuscript. INRIA Sophia-Antipolis, France. Submitted for publication, 1997.
	22	MOURRAIN, B., AND PAN, V. Multivariate polynomials, duality and structured matrices, submitted, 1997.
	23	MOURRAIN, B., AND PAN, V. Y. Multidimensional structured matrices and polynomial systems. Calcolo, Special Issue, workshop on Toeplitz matrices: Structure, Algorithms and Applications 33 (1996), 389-401.
	24	Bernard Mourrain , Victor Y. Pan, Solving special polynomial systems by using structured matrices and algebraic residues, Selected papers of a conference on Foundations of computational mathematics, p.287-304, September 1997, Rio de Janeiro, Brazil
	25	Bernard Mourrain , Victor Y. Pan, Asymptotic acceleration of solving multivariate polynomial systems of equations, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.488-496, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276862]
	26	PEDERSEN, P. S., AND STURMFELS, B. Mixed monomial basis. In Effective Methods in Algebraic Geornetry (MEGA'9~) (Santander (Spain), 1994), vol. 143 of Progress in Math., Birkh/iuser, pp. 285-306.
	27	James Renegar, On the worst-case arithmetic complexity of approximating zeros of systems of polynomials, SIAM Journal on Computing, v.18 n.2, p.350-370, April 1989 [doi>10.1137/0218024]
	28	Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
	29	Hans J. Stetter, Matrix eigenproblems are at the heart of polynomial system solving, ACM SIGSAM Bulletin, v.30 n.4, p.22-25, Dec. 1996 [doi>10.1145/242961.242966]
	30	STURMFELS, B. Sparse elimination theory. In Cornputational Algebraic Geometry and Commutative Algebra (1993), D. Eisenbud and L. Robianno, Eds., Cambridge Univ. Press, pp. 264-298. (Proc. Cortona, June 1991).
	31	VAN DER WAERDEN, B. Modern algebra, Vol. II. Frederick Ungar Publishing Co., 1948.

CITED BY 3

	Victor Y. Pan , Zhao Q. Chen, The complexity of the matrix eigenproblem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.507-516, May 01-04, 1999, Atlanta, Georgia, United States
	Marc Giusti , Éric Schost, Solving some overdetermined polynomial systems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.1-8, July 28-31, 1999, Vancouver, British Columbia, Canada
	Bernard Mourrain , Philippe Trebuchet, Solving projective complete intersection faster, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.234-241, July 2000, St. Andrews, Scotland