In this setting, the polynomial equations have exact rational or algebraic coefficients. The homotopy continuation is done exactly using suitable resultants. At the end of the homotopy, the solutions of the system are again given exactly, as the solutions of simpler systems. The theory was developed in [GHMP95, GHH+97, Lec01, Dur08] and a concrete implementation is available in the Kronecker system [Lec01].
Section 3 is devoted to preliminaries from the area of reliable computation. In section 3.1, we start by recalling the basic principles of ball arithmetic [Hoe09], which is a more suitable variant of interval arithmetic for our purposes. In section 3.2, we pursue by recalling the concept of a Taylor model [MB96, MB04], which is useful in order to compute with reliable enclosures of multivariate analytic functions on polydisks. We also introduce a variant of Taylors models in section 3.3, which simultaneously encloses an analytic function and a finite number of its derivatives. In sections 3.4 and 3.5, we discuss the well known problem of overestimation which is inherent to ball arithmetic. We will provide some techniques to analyze, quantify and reduce overestimation.
In section 7, we first consider the more difficult problem of certifying multiple roots in the univariate case. We will describe two methods based on Rouché's theorem and a third method which rather aims at certifying a local factorization. The last method also serves as an important ingredient for making the Weierstrass preparation theorem effective in an analytic context.
Before we turn our attention to the certification of multiple roots in the multivariate case, it will be convenient to have a general toolbox for effective complex analysis in several variables. In sections 8.1 and 8.2, we first propose two ways how to formalize “computable analytic functions” We next propose several basic algorithms for computations with such functions.
In section 9, we consider the more difficult problem of certifying multiple roots in the multivariate setting. Several algorithms have been proposed for this problem [OWM83, Lec02, GLSY05, GLSY07, LVZ06, LVZ08, RG10, MM11]. However, most existing strategies require the computation of a large number of derivatives of the system, which becomes prohibitive for large clusters of solutions. In the simplest case when the Jacobian matrix of the polynomial system has corank at most one at the singularity, our solution is based on the simultaneous consideration of all solution paths in a herd. The general case will essentially be reduced to this case using analytic elimination techniques which are similar to the geometric resolution method of polynomial systems [GHMP95, GHH+97, Dur08]. In section 9.8, we will also outline a bridge between numeric and algebraic solutions which provides an alternative way to certify solutions.
In section 10, we study generalizations to the resolution of systems of analytic equations in a given polydisk. In section 10.2, we first consider a system of analytic equations as a perturbation of a system of polynomial equations. If, for each of the solutions to the system of polynomial equations, we can control the speed with which the solution moves under perturbations, then we can solve the perturbed system. Unfortunately, this forces us to keep track of solutions which are far away from the region of interest. In section 10.3, we present an alternative strategy based on incremental resolution, as in [GHMP95, GHH+97, Dur08]. Although this strategy also may require to work outside the region of interest, it does stay closer.
where , and are reliable bounds for the rounding errors induced by the corresponding floating point operations on the centers; see [Hoe09] for more details.
Consider an analytic function on some open subset of and assume that admits a ball lift. Given an isolated root of , it is well known that Newton's method converges to in a small neighbourhood of . It is a natural question to explicitly compute a ball neighbourhood for which this is the case (where we notice that a “ball” in is really a compact polydisk). One method which is both efficient and quite tight was proposed by Krawczyk [Kra69]. Recall that denotes the Jacobian of .
We insist once more on the importance of performing all certifications as late as possible rather than along with the numeric computations themselves. One should regard the numeric computation (the spearhead) as an educated guess of what is happening and the certification as an independent problem at a second stage. In particular, only the numeric results which interests us (i.e. the solutions of the polynomial system) need to be certified and not the way we obtained them (i.e. the homotopies).
Even in the case when we are interested in certifying the homotopies themselves, it is best to do so once the numeric computations have already been completed. This allows for instance for more parallelism in the computations. Indeed, we may cut the entire homotopy path in several pieces and certify these pieces in parallel. More numeric data may also be available once all numeric computations have been completed, which might be useful for guiding and accelerating the certification stage.
Similar remarks apply more generally for certified integration of dynamical systems. In that setting, one is often interested in the flow in the neighbourhood of some initial condition. The sequential part of such a computation resides in the numeric integration for a particular initial condition. Once the corresponding numeric trajectory is known numerically, we may again cut it in pieces which and compute the corresponding flows and certifications in parallel. Whenever the dependence on the initial conditions is very strong, the actual numeric integration should be done using accurate high order Taylor methods using a multiple working precision.
In section 5.1, we have studied in detail the numeric determination of a multiple root of a univariate polynomial. It is instructive to take up this study and examine how we certify such multiple roots. Since the property of being an -fold root is lost under small perturbations, this is actually impossible using ball arithmetic. The best we can hope for is to certify the existence of roots in a small ball, or the existence of an -fold root of a small perturbation of the polynomial (see also [Rum10]).
for all with . By Rouché's theorem [Lan76, page 158], it follows that and admit the same number of roots on . If becomes large, or if admits other roots close to , then the bound (25) often does not hold. In that case, one may use more sophisticated techniques from [Sch82, Hoe11] in order to certify that admits roots in . From the complexity point of view, the series expansion method requires evaluations of , where denotes the cost of multiplying two polynomials of degrees .
Whenever a polynomial admits roots in a disk, then the polynomial is a monic factor of . Instead of trying to determine and certify the roots individually, another idea is to determine and certify this monic factor of .
Assuming that admits no other roots near , we will show in this section that forms an isolated zero of , when regarding this equation as a system of equations in variables . On one hand, this approach has the advantage that we may apply Corollary 7 in order to certify the factorization. On the other hand, we may use fast polynomial arithmetic for the actual evaluation of .
Theorem 10. Let be roots of a polynomial of multiplicities , and . Then is an isolated zero of the system , when considered as a system of equations in variables .
Proof. Given the euclidean division of by , we have for small perturbations of , with . Consequently,
For the sequel, it will sometimes be convenient to consider the more general context of analytic functions instead of mere polynomials. We provide two formalizations of computable multivariate analytic functions: an abstract one relying on analytic continuation in section 8.1, as well as a more concrete evaluation based one in section 8.2. In the remainder of the section, we will discuss evaluation of analytic functions in zero dimensional algebras, effective Weierstrass preparation, and computable meromorphic functions.
We recall [Wei00] that a real number is said to be left (resp. right) computable if there exists an increasing (resp. decreasing) computable sequence with . We say that is computable if is both left and right computable. We denote the sets of computable, left computable and right computable real numbers by , and . We define to be the set of computable complex numbers. The definitions also adapt in a straightforward way to extended real numbers . The theory of computable real numbers provides a suitable abstract framework for studying which analytic problems can be solved.
In [Hoe05, Hoe07], we proposed a similar concept of computable analytic functions. Given an analytic function at the origin, we say that is computable if there exists methods for computing the power series expansion of , a lower bound for its convergence radius, an upper bound for on any closed disk on which converges, and a method for the analytic continuation of . Formally speaking, denoting by the set of such functions, this means that we may compute
The computable power series expansion of (this means that we have an algorithm for the computation of the coefficients of ).
A computable partial function , which yields the analytic continuation of (with ) as a function of with .
Given , we call its computable radius of convergence. Usually, is smaller than the genuine radius of convergence of .
This definition admits several variants. In practice, it is usually most convenient to provide a method for the computation of bounds using ball arithmetic and allow for infinite bounds. In that case, we automatically obtain an algorithm for the computation of , by taking . This definition is also convenient to extend to the case of multivariate analytic functions in . In this case, we require algorithms for the computation of:
Recall that the function is necessarily upper continuous (e.g. [Hoe07, Theorem 2.3]). In particular, for every with there exists an with .
In practice, multivariate analytic functions such as are often built up as dags from univariate analytic functions such as and . In that case, it would be very expensive to systematically use power series expansions in several variables in order to compute with such functions. Instead, it would be better to represent such multivariate analytic functions as objects which can be evaluated at analytic functions in an arbitrary number of variables, or even at points in more general algebras.
More precisely, let be an effective Banach algebra over . This means that is the set of computable points in a Banach algebra over , and that the operations and the norm can be computed by algorithm. Recall that
for all . We do not necessarily assume to be commutative. Given a multivariate analytic function in with and pairwise commuting with for , the evaluation
is well defined. What is more: if and , then . Indeed, we start by computing and such that . For fixed and
Conversely, assume now that, in the definition of computable multivariate analytic functions, we replace the method by an evaluation method for any effective Banach algebra over . In particular, given , we may take to be the algebra of all formal power series for which
is finite. Given with , it follows that the evaluation is well defined, and this evaluation yields the power series expansion of at the origin. This shows that providing an evaluation method is essentially equivalent to providing a method for series expansion.
Remark 11. In fact, analytic continuation and bound computation can also be regarded as evaluations in suitable “Banach algebras”. Indeed, the analytic continuation at corresponds to the evaluation at the analytic function . The computation of the bound can be done by evaluating at the ball and taking , where . Nevertheless, explicit methods for analytic continuation and bound computations are usually of a better quality. They may also be needed for the implementation of more general evaluation methods.
Following the same line of ideas, it may also be useful to consider the evaluation of analytic functions at broken line paths (or more general piecewise analytic paths) instead of ordinary points, thereby combining analytic continuation and ordinary evaluation in a single method. One might even consider evaluations at “paths” of successive Banach algebras of a similar type, such as with the and the sufficiently close, and .
In order to simplify notations, we will now stop our digression on the abstract notions of computability and drop the superscripts “com”. In view of what we have seen in section 9.2, it is particularly interesting to evaluate multivariate analytic functions in commutative zero dimensional algebras over . Therefore, we will now study this special case in more detail.
Let be a finite dimensional -algebra. Given any basis for , the elements of can be represented by matrices, so may be identified with a commutative subalgebra of the algebra of matrices for some . In particular, any matrix norm on induces a norm on .
Given a multivariate analytic function at the origin which is convergent on a polydisk of polyradius , we may use (27) in order to evaluate at any points with for all . Since the commute, it is actually possible to do a bit better. Indeed, it is classical that there exists an invertible matrix (corresponding to a base change), such that
For any with , we notice that the evaluation reduces to an evaluation at an ordinary point. If , then we also notice that
Let us start with a special case of Weierstrass preparation: the implicit function theorem. Consider a computable analytic function in in the neighbourhood of a point . Assume that but . Then the implicit function theorem states that there exists a unique analytic function in such that in a neighbourhood of and . It is not hard to check that is computable, for instance in the sense of section 8.1:
More generally, given analytic functions such that the Jacobian matrix has full rank at , then it can be shown in a similar way that the system of equations in unknowns
admits a unique analytic solution at which is again computable. Notice that this more general case also follows through a -fold application of the case of a single function.
Let us still consider a computable analytic function in in the neighbourhood of a point . Assume now that but . Then the Weierstrass preparation theorem states that there exist unique analytic functions in and an invertible analytic function in such that
We may regard (28) as a local factorization of the analytic function in , which depends on as parameters. Now Theorem 10 for the computation of local factorizations readily generalizes to computable analytic functions. More precisely, is the solution of the system , which we consider as a system of analytic equations in unknowns . It can be checked that this system of equations admits full rank, so that we may compute by applying the effective implicit function.
Effective Weierstrass preparation as described in the previous section can only be applied on rare occasions. Indeed, the assumption that we have an exact multiple cancellation is too ambitious, and needs to be replaced by the weaker condition that has a multiplicity in in a small neighbourhood of . This condition is still enough for the existence of a unique solution to the system in a neighbourhood of .
This naturally leads us to the question how to certify that has multiplicity in , in a small neighbourhood of , and uniformly in . In fact, paying some care, all methods from section 7 can be generalized to this setting. First of all, when using ball arithmetic, the parameters are simply replaced by small balls around , which reduces the problem to a univariate one. Secondly, when working with Taylor models at any chosen truncation order , the tail of an analytic function near is replaced by a ball of the form or . This reduction allows us to work with polynomials instead of series.
We also notice that the above certification methods can actually prove something slightly stronger than a uniform multiplicity: they can usually be used to verify that the zero set does not intersect . If such is the case, then we say that the equation is equisolvable in on .
Given a ball (and where we recall that such a “ball” is really a polydisk) such that we can certify a constant multiplicity of in on , the unique (and computable) analytic function such that is an analytic unit on will be called the Weierstrass normalization of on .
Given two analytic functions and on , assume that we can certify a constant multiplicity for at least one of them, say for , and let be as above. Then Weierstrass division of by yields unique analytic functions and such that and is polynomial in with . We may obtain (the residue class of) as a computable analytic function through evaluation of in the quotient algebra of computable analytic functions in by the relation .
Having computed the remainder of the Weierstrass division of by , we may finally form the resultant of the polynomials and in . This resultant is a computable analytic function in whose zeros are precisely the projections of the common zeros of and on . We will also call the analytic resultant of and on . Whenever is also defined, it can be checked that for some analytic unit on . Indeed, writing and for analytic units and , and is a unit. Similarly, .
A computable meromorphic function is simply the quotient of two computable analytic functions such that the denominator is non zero. The computable meromorphic functions on a given domain form an effective field (but without a zero test). Using an external argument, we sometimes know that a computable meromorphic function is actually analytic on some domain. In this case, we would like to conclude that is computably analytic on this domain.
Let us first consider the case when and are both univariate computable analytic functions in , in the neighbourhood of a single isolated zero . We start with the subcase when on a ball with . Let be the ball evaluation of at . For all , we then we have
It would be interesting to know whether there exist generalizations of (29) to higher multiplicities or involving the successive derivatives of . In this section we will present a more ad hoc strategy for computing a reliable Taylor series expansion of in the case when , and are all analytic.
Let and be all small and a larger ball with the same center and radii and . Assume that admits exactly zeros both on and on . Let and . Writing , and for each , we have
For the small balls, we may thus use (32) for the computation of an enclosure for , and switch to (31) whenever this enclosure becomes better.
More generally, it is in principle possible to recover any analytic function on a closed disk from its values on its boundary using Cauchy's formula. We will now describe an efficient method to do this effectively. When applied to computable meromorphic functions as above, this method has the advantage that we do not need to know the numerator and denominator explicitly; it is sufficient that we can compute its ball values on the boundary circle. Without loss of generally, we may assume that is the unit disk.
For a given number of evaluation points (preferably a power of two) and with , we evaluate at the disks for , yielding . We next compute ball enclosures for the coefficients of the unique polynomial with and for all using one reliable discrete Fourier transform. The remainder is bounded by on the unit circle, whence on the unit disk. This yields a Taylor model for . Taking sufficiently large, the so computed Taylor model can be made as accurate as needed.
Let us now consider a meromorphic function in several variables which is actually analytic on some small ball. Modulo a linear change of coordinates and shrinking the domain to a smaller ball , we may first ensure that has constant multiplicity in on . We may then use any of the methods from the previous section for computing as an analytic function in , which depends analytically on the parameters .
Consider a system (11) and assume that we have numerically isolated a solution of multiplicity . Based on numerical computations, assume also that the Jacobian is expected to have corank at most one at .
In a small ball around (and where we recall that is really a polydisk) we may certify the corank assumption by computing using ball arithmetic and then checking that an submatrix admits a non zero determinant (still using ball arithmetic).
At the next stage, we would like to certify that there exist indeed exactly solutions in a suitable neighbourhood of , when counted with multiplicities. Now using our effective version of the implicit function theorem from section 8.4.1, we may analytically eliminate at least variables from the equations (11), say from the equations . This yields computable analytic functions such that
Using the techniques from section 8.4.3, we finally check that has multiplicity in a suitable neighbourhood of .
Remark 12. One of the simplest examples when the corank one hypothesis fails is the following system:
Let us still consider the system (11) and assume that we are given a herd of numeric solution paths which all tend to the same limit . In this section, we will investigate the problem of simultaneously certifying each of the paths in the herd.
We would like the follow the same strategy as in section 7.3, where we certified a single factor of order instead of separate roots. In the current setting, instead of viewing the as distinct individual paths, this amounts to regarding the whole herd as a single multivalued path. From the algebraic point of view, this means that we need to consider the ideal which annihilates . There are several ways to represent this ideal by a system of polynomial equations. We will use so called univariate representations.
we notice that is invariant if we turn once around the origin. This means that is really an analytic function in at the origin. Assuming general position, is actually the minimal annihilator of . Furthermore, for sufficiently small, the roots are pairwise distinct, so there are unique interpolating polynomials of degree with
Solving the original system for of this form now amounts to a new system of equations in the unknowns and . This system can also be considered as a system of equations in unknowns over the algebra , augmented with one special unknown and one special equation . In analogy with Theorem 10, we may hope that this new system is non singular near , so that we can certify the herd using Corollary 7. It can be checked that this is always so in the corank one case from the previous section. Unfortunately, Theorem 10 fails to generalize in general. In particular, the new system remains singular whenever several herds converge to the same singularity.
Let us now return to the general case when the corank of the Jacobian matrix at the solution may be larger than one. First of all, it will be useful to generalize the notion of equisolvability from section 8.4.3 to the case of several equations. Consider the system
on , where might actually be analytic functions instead of mere polynomials. We say that (34) is equisolvable in on if the zero set
does not intersect , where and . In particular, this means that the number of solutions of (34) as a function of does not depend on . Furthermore, the following lemma shows that there are no exceptional fibers with an infinite number of solutions.
Lemma 13. Assume that (34) is equisolvable in on and that is the zero set of a non zero analytic function on . Then none of the components of can be contained entirely in the set .
Proof. Assume for contradiction that has dimension . Taking , the intersection has dimension , whence it contains an analytic solution curve whose image has dimension one. Since (34) is equisolvable in on , the curve is entirely contained in . Consequently, the analytic functions are all bounded, whence constant. This contradicts our assumption that has dimension one.
is not equisolvable, since the equation has one solution for , but no solutions for . Of course, is equisolvable on for on a larger disk (or on a smaller disk). Graphically speaking, an equation is equisolvable if and only if all solution curves are “nicely horizontal” in .
where the coefficients and are computable analytic functions in on , such that (with ) and the system (34) is equivalent to
Lemma 15. Assume that the system admits a finite number of solutions in and that the -coordinates of these solutions are pairwise distinct. Then there exists a Kronecker representation for on .
Proof. Let be such that are pairwise distinct. Then we define the Kronecker representation for to be the unique -tuple of univariate polynomials with , , , such that is annihilated by the system
We may compute such a Kronecker representation as follows. If , then we simply take and for all . For , we decompose with and compute in terms of and using
This yields an efficient dichotomic algorithm for the computation of . The result follows by applying the method to the solutions of in .
for the system (34) with . Moreover, the equisolvability assumption implies that the degree of does not depend on . Furthermore, since for , the way we compute the functions depends analytically on . We thus obtain a “Kronecker representation” for (34) on the subset instead of .
Let be such that . Expanding and with , we have for all . Consequently, remains bounded on . Since is a removable isolated singularity, it follows that admits a unique analytic continuation on . It also follows that we may also choose to be the zero set of .
It remains to be shown that the with can also extended analytically from to . For this, we consider a new coordinate where are parameters. For sufficiently close to , we may apply the above result to the system rewritten as equations in . Notice that this new system is defined on a domain which is slightly smaller than . We thus obtain a Kronecker representation
which is equivalent to for with , where . The function is defined on and analytic both in and . Differentiating the equation with respect to with , we obtain
Proposition 17. Assume that is equisolvable in on . Assume that we are given a Kronecker representation (36) for (34) such that is equisolvable in on and such that vanishes on . Then (34) is equisolvable in on .
Proof. Assume for contradiction that . Since is equisolvable in on , we cannot have . Consequently, . Hence, we both have and . This contradicts the assumption that is equisolvable in on .
The univariate representation is a variant of the Kronecker representation. It consists of polynomials
such that the coefficients are computable analytic functions in on , the coefficients are computable meromorphic functions in which are analytic on , where and . Finally, the system (34) is assumed to be equivalent to
for all . Given a Kronecker representation, we may compute a univariate representation as follows. We first compute the inverse of modulo , whose coefficients are meromorphic and analytic on . Taking , we may then retrieve the univariate representation from the Kronecker representation.
Given a Kronecker representation satisfying the hypothesis of Proposition 17, let us now study the intersection problem with a new equation . We first compute a univariate representation for (34), as detailed in section 9.5. Now consider the resultant
In practice, we may compute by evaluating at in the algebra where is the set of computable analytic functions on , and then take the norm of this evaluation. Let denote the solutions of (34) in as a function of , considered as analytic functions in on some Riemann surface above . By a classical property of resultants, we have
on . Whereas the functions generally admit a non trivial monodromy, the value of is uniquely determined as a function on on . Moreover, since for , the analytic function is bounded on . Since the complement of in is isolated, this means that extends uniquely into an analytic function on .
Lemma 18. Given a Kronecker representation (36) for and assuming that is equisolvable in on , the resultant vanishes on .
Proof. If , then (38) directly yields . For general , let be a vector such such that for all sufficiently small . Then is a bounded function, given by a Puiseux series of valuation in . Since is equisolvable in on , one of the curves tends to for . Since , it follows that and therefore tend to for . We conclude that , using the analyticity of .
We have shown above how to find an analytic relation for which is implied by on . We still need to show how to express as a function of . For this we use a similar technique as in the proof of Theorem 16. Consider formal variables with for all and new coordinates such that
and prove that are analytic functions in on . The common zeros of (34) and correspond to the zeros of this resultant with respect to the new coordinates. Setting and leads to
where . Assuming that is not the zero function on , this almost yields a Kronecker representation for .
In order to obtain an actual Kronecker representation, we finally compute the Weierstrass normal form of with respect to , together with an invertible analytic function in such that . Setting , we then obtain the Kronecker representation
We are now in a position to certify the multiplicity of the system (11) on a sufficiently small ball. We first construct a homotopy for the system (11) which is in sufficiently general position. For notational reasons, it will be convenient to use instead of for the time parameter. We take
For our main objective is to certify that the system is equisolvable in on a sufficiently small ball with around a numerical solution. For , we proceed as in section 8.4.3. Assume now that we have proved equisolvability in for the system on and that we also have a Kronecker representation
for the same system, where . Using the algorithms from section 8.4.3, we may again ensure that is equisolvable in on . Using the algorithm from section 9.6, we next compute a Kronecker representation
for the intersection , where . We will show below that on . Furthermore, vanishes on , by Lemma 18. We conclude that the system is equisolvable in on , by Proposition 17. By induction, this completes our algorithm to certify (almost) multiple roots on a sufficiently small polydisk around .
We still have to check that is not identical to zero on . Assume the contrary, so that vanishes everywhere, by analytic continuation. In other words, for any fixed , the equation admits a multiple solution in . In particular, taking , the generator of the ideal admits a multiple solution. Denoting by the solutions of the system , we have . Now was taken sufficiently small so as to ensure that for all , contradicting the assumption that admits a multiple root.
The Kronecker representation provides one useful exact representation for the set of solutions. Modulo a generic linear change of coordinates, we may assume without loss of generality that for any distinct solutions of (11), their first coordinates and are also distinct. Using the algorithm in the proof of Lemma 15, we may then compute a Kronecker representation for the system (11).
Assume now that (11) has rational coefficients and that we have computed numeric approximations of with bit precision . Using the above method, we may thus compute a numeric approximation of the Kronecker representation with an accuracy of approximately bits. We apply rational number reconstruction [GG02, Chapter 5] in order to provide a guess for the Kronecker representation with rational coefficients. We may check whether this guess is correct by evaluating at over . If the check fails, then we double the bit precision, use Newton's method to improve the approximations , and keep iterating.
In the case that we suspect our system to admit multiple roots, which means that we have at least one herd of numerical solutions, the centers of herds of solutions are still known numerically with a precision of approximately bits. Consequently, we may use the above method in order to compute the radical of the zero dimensional ideal generated by the . By evaluating the over suitable algebras with nilpotent elements, we may check in a similar way as above whether the multiplicity of each root matches with the numeric multiplicity and obtain an exact algebraic representation for . In the projective setting with no solutions at infinity, this strategy can be used to provide a full algebraically certification of all solutions.
It is possible to generalize the techniques of this paper to the local resolution of a system of analytic equations on a polydisk. In this section, we outline some ideas for generalizations of this kind. As a general rule, such generalizations usually work better when the local solutions in the polydisk are well separated from the other solutions outside the polydisk.
where is an effective analytic function on the closed unit disk , without any roots on the unit circle. Assume that we wish to find all roots of in . Using the methods from section 8.4.3, the first step is to compute and certify the number of roots in .
Having determined the exact number of roots inside , most standard numerical methods for finding the roots of a polynomial of degree can be mimicked. For instance, we may use the homotopy
for and . In the unlucky case that we only find a subset of the roots with , we set and keep repeating the algorithm using a homotopy of the form
and for a new random choice of with . This method will ultimately pick random sufficiently close to any of the roots, thereby ensuring the termination of the method. We may also use Aberth's method, while resetting points that fall outside the unit disk to random points inside the disk.
of equations, where are computable analytic functions on the closed unit polydisk . From now on, our aim is to determine the solutions of this system in .
Using the homotopy methods from this paper, we may compute the solutions of this system and keep only those ones which are in . At a second stage, we form the homotopy
and follow the solutions of the truncated systems from to . This yields an uncertified candidate for the set of solutions to (39).
for suitable and with . While following the homotopies, we may also decide to drop any paths which lead “too far” outside .
Typically, we now take to be the degree for which is maximal (and in any case larger than this value). We may determine this degree by first computing a bound for on a polydisk with , so that for all , whence for all . Starting with and , we now repeat the following: if , then . Else, if , then we stop and take . Otherwise, set and continue.
Let us now investigate how to certify that we found all solutions in . Since (39) is really a perturbation of (40), one idea would be ensure that for each solution of (40), the solutions remain either inside or outside for small perturbations. More precisely, for each , we start by computing a bound for on (for instance, we may take with the above notations, but is sometimes better to take more explicit coefficients for a sharper bound). We next consider the system
For each solution to (40), we now compute a ball enclosure of this solution such that any solution to with near lies in . This can be done using the ball version of Newton's method. We next check whether each of the obtained enclosures is either entirely contained in or in its complement. If this is the case, then we have obtained the desired certification. Indeed, consider a solution to (39). Then setting , we have and , for all . Hence for one of the above enclosures.
Remark 20. One disadvantage of the above certification method is that we have to keep track of both the solutions inside and outside for small perturbations of (40). An alternative idea would be to consider the set of all solutions to (39) inside as a generalized point which is the solution of a suitably deflated system, as in we did in section 9.2 for the certification of herd homotopies. This generalized solution is usually unique in a large polydisk, corresponding to large perturbations of the system of equations for . With some luck, this polydisk actually contains all sets of points in , thereby certifying that is the set of all solutions to (39) inside .
Unfortunately, this idea only works in dimension . For instance, in dimension two, the ball of systems with and does not contain a system which admits the set as its solutions. Nevertheless, it can be checked that any set of two elements in is the solution of a system in either or , where with for any .
As noticed in remark 20, one major disadvantage of the certification method from the previous section is that we need to consider the behaviour of all solutions to (40) under small perturbations, and even of those which lie far outside .
The incremental geometric resolution technique from the section 9.7 for the certification of multiple roots can also be used for finding and certifying an arbitrary set of roots in a polydisk . For this to work, it is necessary that the system (40) is equisolvable on , which means in practice that we chose a sufficiently general position and that the other roots of (40) outside are sufficiently far away from .
Remark 21. In the analytic setting, it can be interesting to compute the numeric solutions to (40) in an incremental way as well. A heuristic way to do the intersection step numerically goes as follows. We assume general position and consider the last intersection (the other intersections are done similarly, in fibers with ). Suppose that we are given a Kronecker representation
for the system , in the fiber where . Let be an upper bound for the number of roots of . For each of the roots of the equation , we continue our Kronecker representation to a new one in the fiber with . We finally use the homotopy
In the case when our method fails to prove equisolvability, we need to decompose the system (39) into simpler systems which are equisolvable. This can be done using the following techniques:
By covering by a finite number of polydisks, each on which the system is equisolvable. For instance in the case of the function from example 14, we may cover by the polydisk , or by the polydisk and several other polydisks of the form .
By applying a permutation of the coordinates. For instance the function from example 14 is equisolvable in with respect to . We may also consider other linear changes of coordinates modulo adjustment of the regions. For instance, the equation cannot be made equisolvable by one of the above means. Nevertheless, after setting and , the equation becomes equisolvable on .
By factoring the equation. Especially when an analytic function is restricted to a small region, it frequently occurs that it can be factored into simpler functions on this region. For instance, the equation can be factored as on into two equations and which are equisolvable in resp. .
In principle, it is always possible to reduce to the equisolvable case using these techniques, but the number of required subdivisions may quickly grow out of hands. Indeed, for each solution (which we assumed to be single), there exists a sufficiently small neighbourhood where the are essentially linear functionals. The design of a good algorithm for keeping the number of subdivisions as small as possible is beyond the scope of this paper.