Solution of a polynomial system of equations

The next problem, highly important in computer algebra, is a natural extension of Problem 3.1.

Problem 4.1, solution of a polynomial system of equations. Given a positive b , a positive integer D , a vector norm $\vert\vert \cdot \vert\vert$, and the coefficients of a system of n polynomial equations,

 $$p_i (x_1, \dots, x_n)=0, ~i=1, \ldots, n,$$

in n variables $x_1, \dots, x_n$ having at most D unknown common roots, $Z=( {\bf z}^{(1)}, \ldots, {\bf z}^{(d)} )$, ${\bf z}^{(i)} = (z_1^{(i)}, \dots, z_n^{(i)}), ~ i=1, \dots, d;~ d \le D$, compute approximations $\tilde{{\bf z}}^{(1)}, \ldots, \tilde{{\bf z}}^{(d)}$ to the roots satisfying $\vert\vert \tilde{{\bf z}}^{(i)} -{\bf z}^{(i)} \vert\vert \le 2^{-b}$max $\{ 1, \vert\vert {\bf z}^{(i)} \vert\vert \}, ~ i=1, \ldots, n$.

Problem 4.1 is much harder than Problem 3.1. The known upper and lower bounds even on the sequential arithmetic computational cost of its solution remain far apart from each other; namely, they are $O_A(D^3)$[Ren89] and $\Omega(D)$, respectively.

Practically, one frequently needs a solution of various subproblems of Problem 4.1, such as the following ones.

Problem 4.2, counting the roots. Compute the number of the roots of system (4.1).

Problem 4.3, counting the real roots. Compute the number of the real roots of system (4.1).

Problem 4.4, counting the roots that lie in a fixed polytop. Compute the number of the roots of system (4.1) lying in a fixed polytop bounded by H hyperplanes in the complex n -dimensional space $\mathbb{ C} ^n$.

As a particular case of Problem 4.4 for H=2n , one may compute the number of nearly real roots having imaginary parts of all their n coordinates at the distance at most $\epsilon$from 0, for a fixed small positive $\epsilon$.

Problem 4.5. Approximate all roots of system (4.1) that lie in a fixed polytop in $\mathbb{ C} ^n$bounded by H hyperplanes in $\mathbb{ C} ^n$.

Problem 4.6. Approximate a root of the system (4.1) maximizing the value $\vert h({\bf x})\vert$of a fixed polynomial $h({\bf x}) = h(x_1, \ldots, x_n)$.

Problem 4.7. Approximate a root of the system (4.1) minimizing the value $\vert h({\bf x})\vert$of a fixed polynomial $h({\bf x})$.

Until recently, $O_A(D^3)$was the record known upper bound on the sequential arithmetic complexity of all these problems, even assuming generic system (4.1) whose solution is only sought for an algebraically open set in the input coefficient space. A substantial asymptotic acceleration, however, was achieved in our joint work with Bernard Mourrain [MP98], [MP98a], [MP,a] for Problems 4.2-4.7. We summarize this progress in the next theorem.

THEOREM 4.1   There are algorithms supporting the following arithmetic cost estimates : $O_A(3^n D^2 \log D)$for Problems 4.2 and 4.3, $O_A (3^n H D^2 \log D)$for Problem 4.4, $O_A (3^n (\delta +H) ( D^2 \log D) \log b)$ for Problem 4.5, and $O((D^2 \log D) \log^2 b)$for Problems 4.6 and 4.7, assuming all these problems for generic polynomial system of equations (4.1).

The algorithms of [MP98], [MP98a], [MP,a] supporting Theorem 4.1 combine several advanced algebraic and numerical techniques involving dual spaces of linear forms (maps) on the primal linear space of polynomials in $\mathbb{ C} ^n$, algebraic residues, structured matrices, and the iterative processes of repeated squaring and sign iteration in the primal and dual spaces. So far, involvement of such sophisticated tools slowed down the experimental testing and practical implementation of the algorithms, but their simplified versions for Problems 4.6 and 4.7 (supporting the bounds $O_A(D^2 \log D)$in terms of D ) have been successfully tested numerically (cf. [BMP98]).

Some distinct algorithms for the fast and memory space efficient solution of sparse polynomial systems (4.1) were presented in [EP97].