Complexity estimates depending on condition and round-off error
From MaRDI portal
Publication:3158534
DOI10.1145/300515.300519zbMath1065.68533OpenAlexW2092920739MaRDI QIDQ3158534
Publication date: 25 January 2005
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/300515.300519
Analysis of algorithms and problem complexity (68Q25) Roundoff error (65G50) Numerical computation of solutions to single equations (65H05) Complexity and performance of numerical algorithms (65Y20)
Related Items (19)
Generalized polar varieties: geometry and algorithms ⋮ Positive root isolation for poly-powers by exclusion and differentiation ⋮ Faster \(p\)-adic feasibility for certain multivariate sparse polynomials ⋮ Condition number based complexity estimate for solving polynomial systems ⋮ Unrealistic models for realistic computations: how idealisations help represent mathematical structures and found scientific computing ⋮ Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\) ⋮ Limits of theory sequences over algebraically closed fields and applications. ⋮ A numerical algorithm for zero counting. III: Randomization and condition ⋮ Computing the homology of real projective sets ⋮ Fast computation of zeros of polynomial systems with bounded degree under finite-precision ⋮ A numerical algorithm for zero counting. I: Complexity and accuracy ⋮ Grid methods in computational real algebraic (and semialgebraic) geometry ⋮ A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ Condition number based complexity estimate for computing local extrema ⋮ Unnamed Item ⋮ Complexity lower bounds for approximation algebraic computation trees ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ Real computations with fake numbers
Uses Software
This page was built for publication: Complexity estimates depending on condition and round-off error
