Algorithms for near solutions to polynomial equations

DOI10.1016/J.JSC.2009.04.002MaRDI QIDQ840709zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 14 September 2009

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2009.04.002

zbMATH Keywords

algorithmsnear solutionspolynomial equations

Mathematics Subject Classification ID

Solving polynomial systems; resultants (13P15)

Review text

Let \(K\) be a field, \(F(x,y)\) a polynomial over \(K\), and \(m\) a nonnegative integer. We say that a polynomial \(g\) over \(K\) is an \(m\)-near solution of \(F(x,y)\) if there exists an element \(c\in K\) such that \(F(x,g)=cx^m\). In this case we say that \(c\) is an \(m\)-value of \(F(x,y)\) corresponding to \(g\). In particular, for \(c=0\), by viewing the equation \(F(x,y)=0\) as a polynomial equation over \(K[x]\) with variable \(y\), every solution in \(K[x]\) of this equation is also an \(m\)-near solution. In this paper, the author provides an algorithm that gives all \(m\)-near solutions of a given polynomial \(F(x,y)\) over \(K\). This algorithm is polynomial time reducible to solving one-variable equations over \(K\). In order to introduce and analyze the algorithm, the author defines the notions of upper and lower approximate solutions of the equation \(F(x,y)=0\), as well as the notion of independent set of upper (lower) approximate solutions. This paper continues his previous work on near solutions to polynomial equations [J. Symb. Comput. 33, No. 2, 239--254 (2002; Zbl 1046.13020); Acta Arith. 123, No. 2, 163--181 (2006; Zbl 1152.11012)].

Recommendations

• Near solutions of polynomial equations
• Approximate solutions of polynomial equations.
• scientific article; zbMATH DE number 1254271
• Complexity of Bezout's theorem. V: Polynomial time
• On the approximation of some nonlinear equations

Cites work

• Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
• Approximate solutions of polynomial equations.
• Factoring Multivariate Polynomials over Algebraic Number Fields
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 1305293 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• Near solutions of polynomial equations
• On the computational power of pushdown automata
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization

Cited in

(10)

• Approximate solutions of polynomial equations.
• Solving polynomial equations. Foundations, algorithms, and applications
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• The natural algorithmic approach of mixed trigonometric-polynomial problems
• Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem
• Near solutions of polynomial equations
• A non-NP-complete algorithm for a quasi-fixed polynomial problem
• An Algorithm for Solving Polynomial Equations
• scientific article; zbMATH DE number 819105 (Why is no real title available?)
• A Halley‐Like Hybrid Method for Solving Polynomial Equations

This page was built for publication: Algorithms for near solutions to polynomial equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q840709)