Article

Free access

Solving some overdetermined polynomial systems

Authors:

Marc Giusti,

Éric SchostAuthors Info & Claims

ISSAC '99: Proceedings of the 1999 international symposium on Symbolic and algebraic computation

Pages 1 - 8

https://doi.org/10.1145/309831.309838

Published: 01 July 1999 Publication History

PDF eReader

References

[1]

BAUR, \~. AND STRASSEN, V. The complcxity of' partial deriwitives. Theo. Comp. Sci. 22 (1983), 317-330.

Crossref

Google Scholar

[2]

BONDYFALAT, D., .X~OURRAIN, B., AND PAN. V. Controlled iterative lnethods tbr solving polynomial systems. In ISSAC'98 (1998), ACM Press., pp. 252 259.

Digital Library

Google Scholar

[3]

CIIISTOV. A. AND G,~IGOaIEV, D. Subexpon(mtial time. solving systems of algebrai(: equations. LOMI preprint, 1983.

Google Scholar

[4]

DED~EU. J., AND SIIUB, M. Newton and predictorcorrector methods for overdetermined systems of eq~tations. Tech. rep., IBM Research Division, 1998.

Google Scholar

[5]

EGNER, S. Semi-m,merical solution to 6/6-Stewart platform kinematics based m, symmetry. Applicable Algebra in Engineering, Communication and Computing 7 (1996), 449 468.

Google Scholar

[6]

GIANNI, P. AND _-~{ORA, T. Algebraic solution of systems of polynomials equations. In AAECC-5 (1989), Springer, pp. 247(}-257.

Crossref

Google Scholar

[7]

GIUSTI, h'i., HAEGELE, K. HE.INTZ, J., h'ION'I'ANA, Z., h'IORAIS, J., AND PARDO, L. Lower bounds for (tiophantine approximations. In .lournal of Pure and App. Algebra (Proc.eedings of MEGA '96) (1997), vol. 117, pp. 277-317.

Google Scholar

[8]

GIUST}, ~'I. AND HEIN'FZ. Z. La ddtermination des points isold.s et de la dimension d'une varidt~ alg6brique peut se fair(: en temps polynomial. In Computational Algebraic Geometry and Commutative Algebra (1993), E. D. and R. L. Eds.: vol. XXXIV of Symposia Matematica, Cambridge University Press, pp. 216--256.

Google Scholar

[9]

GIUSTI. h'I., HEINTZ, J., h:If)R.AIS, J., h.'IOR.(,ENSTEIIN, Z., AND PARD(), L. Straight-line l)rograms in geometric elitnination theory. Journal of Pure and App. Algebra 124 (1998), 101 146.

Crossref

Google Scholar

[10]

GIUSTI, _.X,I., HEINTZ,l., 1VIORAIS, .}., AND PARDO, L. When polynomial eqlm|,ions can be. "'solved" fast: ? In Applied Alge.bra, Algebraic Al.qorithms and Error Col recting Codes, Proceedings AAECC-11 (1995): C. G., G. M. and M. T., E(ls., vol. 948 of LNCS, Springer, I)P. 205-231.

Digital Library

Google Scholar

[11]

HEINTZ, J. Definability and fast quantifier elimination il, algebraically closed fieMs. Theor. Comput. Sci. 2~4, 3 (1983), 239--277.

Google Scholar

[12]

HEINTZ,1., KRICK, T., PL'I-)I')U, S., SARIA. J., AND x~VAISSBEIN. A. Delbrmation techniques for efficient, polynomial equation s()lvir, g. Subnlitted.

Google Scholar

[13]

HEINTZ. J., ANI) SCIINORll, C. Testing polynomials which are easy to c.ompute. In Logic and Al- .qorithmic, vol. 30 of Monograph, ie de l'ensei.qnement mathdmatiqv.e. 1980, pp. 237--254.

Google Scholar

[14]

KRICK: T., AN'I) PAR.DO, L. A coml)utational method for diophantine approximation. In Algorithms in Algebraic Geometry and Applications (Proceedings MEGA '9~) (1996). G. V. L. and R. T., Eds., vol. 143 of Progress in Mathematics, Birk/iuser Verlag, pp. 193- 254.

Crossref

Google Scholar

[15]

KR.ONECKER, L. Grundzfige einer arithmetische~, Theorie der algebraischen Gr5ssen. Journal f~r die re.ine und andcwandte Mathematik (1882).

Google Scholar

[16]

LAZARD: D. Stewart t)latform and GrSbner bases. In Proceedings of the third international workshop on advance.s of robot kinematics (1992), P.-C. V. and L. J., Eds., Ferrare, pp. 136-142.

Google Scholar

[17]

MERLET.J. Parallel manitmlators- 3rd part. research rep. no. 1003. Tech. re.'p., INRIA Sophia-Antipolis, 1988.

Google Scholar

[18]

MORALS,l. Resolucidn eficaz de sistemas de ecuaclones polinomiales. PhD thesis, University of Santander, Spain, 1998.

Google Scholar

[19]

~'IOURRAIN: B. Enumeration problems in Ge.ometry, Robotics and \Zision. In Al!?o'rithm.s in Alge.braic Ge.ometry and Applications (1996), L. Gonzglez and T. Recio, Eds., vol. 143 of Prog. in Math., Birkhguser, Basel, pp. 285-306.

Crossref

Google Scholar

[20]

RONGA. F. AND \rlJS'l". T. Stewart I)latforms without computer '? In International Conference on Real Analytic and AIgebrnic Geometry (1995), F. Broglia, M. Galbiati, and A. Tognoli. Eds., W. de Gruyter.

Google Scholar

[21]

R.ot:lbLIER., F. Algorithmes efficaces pour l'dtude des zdros reSels des systb~mes polynomiaux. PhD thesis, Universitd R.ennes I, 1996.

Google Scholar

[22]

R.oulr.r.IEa. F. Solving zer~-dimensi~nal polynomial systems trough the rational univariate representation. Tcch. R.ep. 3:126, INRIA, Projet Polka, 1998.

Google Scholar

Cited By

View all

Ruatta OSciabica MSzanto A(2015)Overdetermined Weierstrass iteration and the nearest consistent systemTheoretical Computer Science10.1016/j.tcs.2014.10.008562:C(346-364)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.008
Hashemi A(2010)Strong Nœther Position and Stabilized RegularitiesCommunications in Algebra10.1080/0092787090282854638:2(515-533)Online publication date: 18-Feb-2010
https://doi.org/10.1080/00927870902828546
Ayad A(2010)On computing absolutely irreducible components of algebraic varieties with parametersComputing10.1007/s00607-010-0099-789:1-2(45-68)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1007/s00607-010-0099-7
Show More Cited By

Index Terms

Solving some overdetermined polynomial systems

Recommendations

Overdetermined Systems of Sparse Polynomial Equations

In this paper, we show that for a system of univariate polynomials given in sparse encoding we can compute a single polynomial defining the same zero set in quasilinear time in the logarithm of the degree. In particular, it is possible to decide whether ...
Solving systems of polynomial inequalities in subexponential time

Let the polynomials f"1,..., f"k@__ __ @__ __[X"1,..., X"n] have degrees deg (f"i) < d and absolute value of any coetficient off less than or equal to 2^M for all 1 =< i =< k. We describe an algorithm which recognises the existence of a real solution of ...
Solving polynomial least squares problems via semidefinite programming relaxations

A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '99: Proceedings of the 1999 international symposium on Symbolic and algebraic computation

July 1999

314 pages

ISBN:1581130732

DOI:10.1145/309831

Chairmen:
Keith Geddes
Univ. of Waterloo, Waterloo, Ont., Canada
,
Bruno Salvy
INRIA Rocquencourt, France
,
Editor:
Sam Dooley
IBM Research, Yorktown Heights, NY

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC99

Sponsor:

ISSAC99: International Symposium on Symbolic and Algebraic Computation

July 28 - 31, 1999

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
509
Total Downloads

Downloads (Last 12 months)116
Downloads (Last 6 weeks)27

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ruatta OSciabica MSzanto A(2015)Overdetermined Weierstrass iteration and the nearest consistent systemTheoretical Computer Science10.1016/j.tcs.2014.10.008562:C(346-364)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.008
Hashemi A(2010)Strong Nœther Position and Stabilized RegularitiesCommunications in Algebra10.1080/0092787090282854638:2(515-533)Online publication date: 18-Feb-2010
https://doi.org/10.1080/00927870902828546
Ayad A(2010)On computing absolutely irreducible components of algebraic varieties with parametersComputing10.1007/s00607-010-0099-789:1-2(45-68)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1007/s00607-010-0099-7
Durvye CLecerf G(2008)A concise proof of the Kronecker polynomial system solver from scratchExpositiones Mathematicae10.1016/j.exmath.2007.07.00126:2(101-139)Online publication date: May-2008
https://doi.org/10.1016/j.exmath.2007.07.001
Kaltofen EYang ZZhi LWatt SVerschelde J(2007)On probabilistic analysis of randomization in hybrid symbolic-numeric algorithmsProceedings of the 2007 international workshop on Symbolic-numeric computation10.1145/1277500.1277503(11-17)Online publication date: 25-Jul-2007
https://dl.acm.org/doi/10.1145/1277500.1277503
Moroz GTrager B(2006)Complexity of the resolution of parametric systems of polynomial equations and inequationsProceedings of the 2006 international symposium on Symbolic and algebraic computation10.1145/1145768.1145810(246-253)Online publication date: 9-Jul-2006
https://dl.acm.org/doi/10.1145/1145768.1145810
Pardo LMartín J(2004)Deformation techniques to solve generalised Pham systemsTheoretical Computer Science10.1016/j.tcs.2004.01.009315:2-3(593-625)Online publication date: 6-May-2004
https://dl.acm.org/doi/10.1016/j.tcs.2004.01.009
Huang YWu WStetter HZhi L(2000)Pseudofactors of multivariate polynomialsProceedings of the 2000 international symposium on Symbolic and algebraic computation10.1145/345542.345616(161-168)Online publication date: 1-Jul-2000
https://dl.acm.org/doi/10.1145/345542.345616

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Overdetermined Systems of Sparse Polynomial Equations

Solving systems of polynomial inequalities in subexponential time

Solving polynomial least squares problems via semidefinite programming relaxations