×

Complexity of Bezout’s theorem. II: Volumes and probabilities. (English) Zbl 0851.65031

Eyssette, Frédéric et al., Computational algebraic geometry. Papers from a conference, held in Nice, France, April 21-25, 1992. Boston: Birkhäuser. Prog. Math. 109, 267-285 (1993).
This paper gives volume estimates in the space of systems of \(n\) homogeneous polynomial equations of fixed degrees \(d_i\) with respect to a natural Hermitian structure on the space of such systems invariant under the action of the unitary group. It continues the work from Part I [J. Am. Math. Soc. 6, No. 2, 459-501 (1993; Zbl 0821.65035)]. However, it can be read independently of the first part. Additional results about condition numbers of a homogeneous polynomial are explained in Part III [J. Complexity 9, No. 1, 4-14 (1993; Zbl 0846.65018)].
In this paper, the authors show that the average number of real roots of real homogeneous polynomial systems is \(\sqrt D\), where \(D= \prod^n_{i= 1} d_i\) is the Bezout number. Furthermore, in the first section an upper bound for the volume of the subspace of badly conditioned problems is described by a small degree polynomial in \(n\), \(N\) and \(D\) times the reciprocal of the condition number to the fourth power, where \(N\) is the dimension of the space of systems. The background and the proofs are outlined in the following seven sections in a pleasing manner.
For the entire collection see [Zbl 0917.00011].

MSC:

65H10 Numerical computation of solutions to systems of equations
65Y20 Complexity and performance of numerical algorithms
12Y05 Computational aspects of field theory and polynomials (MSC2010)
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
26C10 Real polynomials: location of zeros
PDFBibTeX XMLCite