Algorithms for near solutions to polynomial equations
type: Item
instance of: scholarly article
title: Algorithms for near solutions to polynomial equations
zbMATH Open document ID: 1201.13009
author: N. E. Zubov
published in: Journal of Symbolic Computation
publication date: 2009-09-14T00:00:00Z
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)].
Mathematics Subject Classification ID: 13P15
zbMATH DE Number: 5603613
zbMATH Keywords: near solutions
zbMATH Keywords: polynomial equations
zbMATH Keywords: algorithms
reviewed by: Vilmar Trevisan
MaRDI profile type: Publication
full work available at URL: j.jsc.2009.04.002
OpenAlex ID: W2044092136
cites work: On the computational power of pushdown automata
cites work: Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time
cites work: Q4406533
cites work: Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
cites work: Factoring Multivariate Polynomials over Algebraic Number Fields
cites work: Factoring polynomials with rational coefficients
cites work: Q4252162
cites work: Approximate solutions of polynomial equations.
cites work: Near solutions of polynomial equations
DOI: 10.1016/J.JSC.2009.04.002
description: scientific article; zbMATH DE number 5603613