Complexity of Bezout's theorem. III: Condition number and packing
Bezout's theoremcomplexitycondition numbererror analysispackingpolynomialsensitivity of output error relative to input error
Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of matrix norms, conditioning, scaling (65F35) Error analysis and interval analysis (65G99) Complexity and performance of numerical algorithms (65Y20)
[For part I see J. Am. Math. Soc. 6, No. 2, 459-501 (1993; Zbl 0821.65035).] The best known example of a condition number is that for the problem of solving a linear system \(Ax= b\). The condition number is \(\kappa_A= |A||A^{- 1}|\), wehre an operator norm on the matrix \(A\) is used. It measures the sensitivity of output error relative to input error. Since \(\kappa_A\geq 1\), \(\log \kappa_A\) is positive and measures the ``loss of precision. For finding a root of a polynomial \(f\), or solving \(f(\zeta)= 0\), the condition number has been taken as \(W_{f, \zeta}= 1/|f'(\zeta)|\). Again it measures sensitivity relative to input error. This condition number lacks certain naturality properties as invariance under the transformations \(f\to \lambda f\), or \(\zeta\to \alpha\zeta\) for \(\lambda\), \(\alpha\in \mathbb{C}- 0\). Moreover, \(W_{f, \zeta}\) does not satisfy \(W_{f, \zeta}\geq 1\). For these and other reasons, we are motivated to define a new notion of condition number \(\mu(f, \zeta)\) of a polynomial at \(\zeta\in \mathbb{C}\).
- Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- Mysteries of mathematics and computation
- On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
- Complexity of Bezout's theorem. V: Polynomial time
- Lower bounds for diophantine approximations
- Distributing many points on a sphere
- Polar varieties, real equation solving, and data structures: the hypersurface case
- Mathematical problems for the next century
- Real computations with fake numbers
- Equidistribution of jellium energy for Coulomb and Riesz interactions
- Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
- Grid methods in computational real algebraic (and semialgebraic) geometry
- Discrete and continuous Green energy on compact manifolds
- An open global optimization problem on the unit sphere
- Perturbation theory for homogeneous polynomial eigenvalue problems
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Linear programming, complexity theory and elementary functional analysis
- Harmonic properties of the logarithmic potential and the computability of elliptic Fekete points
- Deformation techniques for efficient polynomial equation solving.
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- A Wasserstein inequality and minimal Green energy on compact manifolds
- Central limit theorem for the volume of the zero set of Kostlan-Shub-Smale random polynomial systems
- The Diamond ensemble: a constructive set of spherical points with small logarithmic energy
- Optimal \(N\)-point configurations on the sphere: ``magic numbers and Smale's 7th problem
- On the geometry of the set of symmetric matrices with repeated eigenvalues
- Computing the homology of semialgebraic sets. I: Lax formulas
- Random fields and the enumerative geometry of lines on real and complex hypersurfaces
- Distributing many points on spheres: minimal energy and designs
- On the condition of the zeros of characteristic polynomials
- On the expected number of zeros of nonlinear equations
- Probabilistic enumerative geometry over \(p\)-adic numbers: linear spaces on complete intersections
- Low-energy points on the sphere and the real projective plane
- Low-degree approximation of random polynomials
- On a condition number of general random polynomial systems
- Minimizing the discrete logarithmic energy on the sphere: the role of random polynomials
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant
- Energy and discrepancy of rotationally invariant determinantal point processes in high dimensional spheres
- scientific article; zbMATH DE number 3843076 (Why is no real title available?)
- Smale 17th Problem: Advances and Open Directions
- On the probability distribution of condition numbers of complete intersection varieties and the average radius of convergence of Newton's method in the underdetermined case
- Bounds for the condition number of polynomials systems with integer coefficients. (invited talk)
- The probability that a slightly perturbed numerical analysis problem is difficult
- On the efficiency of algorithms of analysis
- Smale's fundamental theorem of algebra reconsidered
- Asymptotics for minimal discrete energy on the sphere
- On simple double zeros and badly conditioned zeros of analytic functions of đ variables
- Equilibrium charge distribution on a finite straight one-dimensional wire
- Geometry of polynomials and root-finding via path-lifting
- Distributing Points on the Sphere, I
- The unavoidable condition\dots A report on the book. Book review of: P. BĂźrgisser and F. Cucker, Condition. The geometry of numerical algorithms
- Multihomogeneous Newton methods
- Newton's method for overdetermined systems of equations
- A sharp Bombieri inequality, logarithmic energy and well conditioned polynomials
- On the minimum value of the condition number of polynomials
- A reverse Thomson problem on the unit circle
- Foreword. What is numerical algebraic geometry?
- On 7th Smale's problem
- A sequence of polynomials with optimal condition number
- A theory of complexity, condition, and roundoff
- Statistical mechanics of interpolation nodes, pluripotential theory and complex geometry
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- Sensitivity analysis of nonlinear eigenproblems
- Numerical computation of the genus of an irreducible curve within an algebraic set
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- STACS 2005
- Finding elliptic Fekete points sets: Two numerical solution approaches
- Kronecker's and Newton's approaches to solving: a first comparison
- Condition numbers of a nearly singular simple root of a polynomial
- On the geometry of Graeffe iteration
- High probability analysis of the condition number of sparse polynomial systems
- Deformation techniques to solve generalised Pham systems
- Rigid continuation paths II. structured polynomial systems
- A lower bound for the logarithmic energy on \(\mathbb{S}^2\) and for the Green energy on \(\mathbb{S}^n\)
- On Gegenbauer point processes on the unit interval
- A continuation method to solve polynomial systems and its complexity
- A numerical algorithm for zero counting. III: Randomization and condition
- Expectation of a random submanifold: the zonoid section
- On a problem posed by Steve Smale
- Computing the homology of real projective sets
- A fast and stable algorithm for splitting polynomials
- Nonarchimedean integral geometry
- The work of Steve Smale
- \(\mathrm{GL}(n, \mathbb{Z}_p)\)-invariant Gaussian measures on the space of \(p\)-adic polynomials
- Branch points of homotopies: distribution and probability of failure
- Expected energy of zeros of elliptic polynomials
- QMC strength for some random configurations on the sphere
- Optimal transport between algebraic hypersurfaces
- Characterization of logarithmic Fekete critical configurations of at most six points in all dimensions
- Characterization of logarithmic Fekete critical configurations of at most six points in all dimensions
- A deterministic global optimization algorithm for the Thomson and Tammes problems
- On the logarithmic energy of solutions to the polynomial eigenvalue problem
- Points on \(\operatorname{SO}(3)\) with low logarithmic energy
- Smoothed analysis of complex conic condition numbers
- On the probability distribution of data at points in real complete intersection varieties
- A numerical algorithm for zero counting. I: Complexity and accuracy
This page was built for publication: Complexity of Bezout's theorem. III: Condition number and packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2365839)
