1

Is there any algorithm that finds all zeros(roots) of a continuous function $F:\mathbb R^n\to\mathbb R^n$?
I've seen some algorithms that find one zero, such as Newton's method. But I need to find all zeros (I need this because I want my computer to use Lagrange's mutiplier theorem).

If that's impossible, then adding the following restriction is okay:
$F$ is composed only of polynomial functions. For example, $F:(x_1,x_2)\mapsto(x_1x_2+1,x_1^2+x_2^2)$.

zxcv
  • 1,445
  • 1
    $F$ is merely continuous? So, for example, the set of zeros could be a Cantor set? Not likely to succumb to a numerical method. Second question: Zeros of sets of polynomials are, indeed, studied in classical algebra. Theory of elimination and such. – GEdgar Oct 30 '18 at 23:38
  • @GEdgar Well, if I don't restrict $F$ to be composed only of polynomials, maybe there has to be some more restrictions on $F$; I haven't thought about it deeply. For your second comment, I didn't know there were such theories (perhaps because I only studied half of abstract algegbra). It's a good news that there is such theories and I'll look it up. Thanks! – zxcv Oct 31 '18 at 00:26
  • @GEdgar The zeros of a polynomial $F : \mathbb{C}^n \to \mathbb{C}^n$ are intersections of $n$ hyper-surfaces. Is there a condition guarantying the intersection are isolated points ? (Gröbner basis ?) – reuns Oct 31 '18 at 00:51
  • For polynomials, use this magma code R<x,y> := PolynomialRing(Rationals(),2); I := ideal< R| x*y+1,x^2+y^2>; GroebnerBasis(I); you get $\mathbb{R}[x,y]/(xy+1,x^2+y^2) =\mathbb{R}[x,y]/(x-y^3,y^4+1)\simeq \mathbb{R}[y]/(y^4+1)$ so the zeros of $F(x,y)=xy+1,x^2+y^2,\mathbb{C}^2\to \mathbb{C}^2$ are $(a_m^3,a_m)$ with $a_m = i^m e^{2i \pi /8}$ the four roots of $y^4+1$. – reuns Oct 31 '18 at 01:03
  • To find all real roots of a polynomial system you need (in general) to find all complex roots. In general, there are $d^n$ complex roots for degree $d$ polynomials in $n$ variables. To reduce this to the solution of a univariate polynomial of corresponding high degree, Gröbner algorithms need time measured in constructs from $d^{n^2}$ to $d^{2^n}$. So yes, that is finite with a guarantee for success, but may take very long even for $d=n=10$, or even $d=2$, $n=20$. – Lutz Lehmann Oct 31 '18 at 08:51
  • @LutzL So the algorithm you're mentioning seems to go like this: First, You reduce the system of multivariate polynomials into one univariate polynomial. Second, you find all roots of that univariate polynomial. Am I right? Then what part of the algorithm takes a long time, the first part or the second part? – zxcv Oct 31 '18 at 11:46
  • The first part, the computation of a triangular or even worse primary decomposition. The reduction process of the Gröbner computation is a heuristic process that computes an hyperexponential amount of intermediate polynomials, with correspondingly large coefficients, ... Finding the roots of an univariate polynomial is well-understood and has a well-bounded complexity. Note however that the precision of the root finding process has to be compatible with the degree and coefficient size of the polynomial. – Lutz Lehmann Oct 31 '18 at 11:53
  • @LutzL You mean a polynomial map $f:\mathbb{C}^n \to \mathbb{C}^n$ extended to $\mathbf{P}^n(\mathbb{C})\to \mathbf{P}^n(\mathbb{C})$, if its zeros are isolated, then there are at most $\deg(f)^n$ zeros of $f$ in $\mathbf{P}^n(\mathbb{C})$ ? – reuns Oct 31 '18 at 19:49
  • @reuns : Yes, that is the more exact formulation of the Bezout bound on the number of roots. Counted with multiplicity, exactly $\prod deg(f_k)$ roots. – Lutz Lehmann Oct 31 '18 at 20:05
  • @LutzL Do you know how to find the vanishing hypersurfaces of $f_1(x,y)$ using magma ? – reuns Oct 31 '18 at 20:07
  • @reuns: You mean the geometric solution resp. Rational Univariate Representation, or reduction to a linear primitive element? There is the Kronecker package by the TERA group (Giusti, Lecerf et al.) and a paper by Rouillier on the RUR. It may even be described in the book by Basu/Pollack/Roy on computational algebraic geometry. I do not know if there is an available Magma implementation of the latter. – Lutz Lehmann Oct 31 '18 at 21:14

0 Answers0