Why does information-based complexity use the real number model?

DOI10.1016/S0304-3975(98)00300-4zbMATH Open0916.68075OpenAlexW2135282115MaRDI QIDQ1292417FDOQ1292417

Authors: H. Woźniakowski 

Publication date: 21 June 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00300-4

Recommendations

• The real number model in numerical analysis
• A refined model of computation for continuous problems
• scientific article; zbMATH DE number 1246413

zbMATH Keywords

nonlinear equationsbisectionreal number modelinformation-based complexityfloating point arithmetic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• How to multiply matrices faster
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast Multiple-Precision Evaluation of Elementary Functions
• Title not available (Why is that?)
• Explicit cost bounds of algorithms for multivariate tensor product problems
• Title not available (Why is that?)
• On the topology of algorithms. I
• Title not available (Why is that?)
• Topological complexity with continuous operations
• The computable multi-functions on multi-represented sets are closed under programming
• Optimal solution of nonlinear equations
• The real number model in numerical analysis
• Average-Case Optimality of a Hybrid Secant-Bisection Method
• Computational Complexity and Numerical Stability
• Bisection is optimal
• Title not available (Why is that?)
• Computation of π Using Arithmetic-Geometric Mean
• Theory of Multivariate Secant Methods
• An efficient algorithm for the complex roots problem
• Title not available (Why is that?)
• Asymptotic near optimality of the bisection method
• Round-off error analysis of iterations for large linear systems
• Numerical stability for solving nonlinear equations
• Numerical stability of descent methods for solving linear equations
• Roundoff-error analysis of a new class of conjugate-gradient algorithms
• Numerical stability of the Chebyshev method for the solution of large linear systems
• Title not available (Why is that?)
• A refined model of computation for continuous problems
• Topological complexity of zero-finding
• 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
• Schemes using preliminary treatment of coefficients for polynomial calculation. A program for automatic determination of parameters

Cited In (5)

• Title not available (Why is that?)
• Unrealistic models for realistic computations: how idealisations help represent mathematical structures and found scientific computing
• Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
• The real number model in numerical analysis
• Complexity of linear problems with a fixed output basis

Uses Software

• mctoolbox

This page was built for publication: Why does information-based complexity use the real number model?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1292417)