Why does information-based complexity use the real number model?
From MaRDI portal
Publication:1292417
DOI10.1016/S0304-3975(98)00300-4zbMath0916.68075MaRDI QIDQ1292417
Publication date: 21 June 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
nonlinear equations; information-based complexity; floating point arithmetic; bisection; real number model
68Q25: Analysis of algorithms and problem complexity
Related Items
Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy, Complexity of linear problems with a fixed output basis
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- How to multiply matrices faster
- Asymptotic near optimality of the bisection method
- Matrix multiplication via arithmetic progressions
- Numerical stability of descent methods for solving linear equations
- Optimal solution of nonlinear equations
- On the topology of algorithms. I
- Round-off error analysis of iterations for large linear systems
- Roundoff-error analysis of a new class of conjugate-gradient algorithms
- Bisection is optimal
- Numerical stability for solving nonlinear equations
- Numerical stability of the Chebyshev method for the solution of large linear systems
- A refined model of computation for continuous problems
- Numerical stability of a convex hull algorithm for simple polygons
- Computing convex hull in a floating point arithmetic
- Average errors for zero finding: Lower bounds for smooth or monotone functions
- Explicit cost bounds of algorithms for multivariate tensor product problems
- The real number model in numerical analysis
- Topological complexity with continuous operations
- Topological complexity of zero-finding
- Gaussian elimination is not optimal
- An efficient algorithm for the complex roots problem
- Theory of Multivariate Secant Methods
- Computational Complexity and Numerical Stability
- Fast Multiple-Precision Evaluation of Elementary Functions
- Computation of π Using Arithmetic-Geometric Mean
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Average-Case Optimality of a Hybrid Secant-Bisection Method
- Schemes using preliminary treatment of coefficients for polynomial calculation. A program for automatic determination of parameters
