6 MARTIJN BAARTSE AND KLAUS MEER by first partitioning the problem’s variables into groups and then applying B´ezout’s theorem to each group. In many cases like the eigenvalue problem mentioned above the resulting bound is much closer to the true number of zeros than it is the case for the ezout number. However, the question then again is how difficult it is to find an optimal grouping of the variables such that the resulting upper bound is minimal. Though we deal with solving numerically systems of polynomials over the complex numbers, the above question leads to a typical problem about a combi- natorial optimization problem and thus into the framework of classical complexity theory. This is due to the structure of multi-homogeneous ezout numbers. More precisely, the optimal grouping mentioned above only depends on the support of the given system, i.e., the structure of monomials with non-zero coefficients. It is not important how these coefficients look like. As consequence, the problem changes to a purely combinatorial one. The question of how difficult it is to compute the op- timal variable partitioning has been answered in [66] which gives a hardness result for the problem. It is therefore sufficient to focus on particular polynomial systems, namely systems F := (f1,...,fn) = 0 in which all fi have the same support. More precisely, consider n N, a finite A Nn and a polynomial system f1(z) = α∈A f1αz1 α1 zα2 2 · · · znn α , . . . , fn(z) = α∈A fnαz1 α1 zα2 2 · · · znn,α where the fiα are non-zero complex coefficients. Thus, all fi have the same sup- port A. A multi-homogeneous structure is a partition of {1,...,n} into k subsets (I1,...,Ik) , Ij {1,...,n}. For each such partition we define the block of vari- ables related to Ij as Zj = {zi|i Ij} the corresponding degree of fi with respect to Zj is dj := max α∈A l∈Ij αl. It is the same for all polynomials fi because all have the same support. Definition 2.1. a) The multi-homogeneous ezout number with respect to support A and partition (I1,...,Ik) is the coefficient of k j=1 ζ|Ik| j in the formal polynomial (d1ζ1 + · · · + dkζk)n, which is ez(A, I1,...,Ik) = n |I1| |I2| · · · |Ik| k j=1 d |Ij| j . Here, we assume the fi to be not yet homogeneous with respect to variable group Zj otherwise, replace dj’s exponent by |Ij| 1. b) The minimal multi-homogeneous ezout number for a system having support A is min I partition ez(A, I). It is known that this minimal number bounds the number of isolated solutions in a suitable product of projective spaces and trivially is never worse than the ezout number, see [64, 100] for a proof. Unfortunately, as it is the case with Bernstein’s bound computing such an optimal partition is a hard task. Even if one would be satisfied with only approximating the minimal multi-homogeneous ezout number using an efficient Turing algorithm this is not likely possible. More precisely, the following holds: Theorem 2.2 ([66]). a) Given a polynomial system F : Cn Cn with support A there is no polynomial time Turing-algorithm that computes the minimal multi- homogeneous ezout number for A unless P = NP.
Previous Page Next Page