Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average

DOI10.1137/0215026zbMath0622.68038OpenAlexW2162322294MaRDI QIDQ3759937

Michael Shub, Lenore Blum

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ff3fbc0b101f9ce693f402f3f3490fae191e4912

zbMATH Keywords

computational complexityrational functionintegral geometrygeometric measure theoryaverage caseloss of precisionmodels of real computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Length, area, volume, other geometric measure theory (28A75) Error analysis and interval analysis (65G99) Real rational functions (26C15)

Related Items

Average condition number for solving linear equations, On the efficiency of algorithms of analysis, A new simple homotopy algorithm for linear programming. I, Complexity theory of numerical linear algebra, Invertibility of random fredholm operators, Computational complexity of kernel-based density-ratio estimation: a condition number analysis, Recent developments in information-based complexity, Condition numbers of random matrices, Characterizations of the distribution of the Demmel condition number of real Wishart matrices