On the Power of Discontinous Approximate Computations

TitleOn the Power of Discontinous Approximate Computations
Publication TypeTechnical Report
Year of Publication1992
AuthorsAberer, K., & Codenotti B.
Other Numbers731

The set of operations S_1={+,-,*,/,>} is used in algebraic computations to avoid degeneracies (e.g., division by zero), but is also used in numerical computations to avoid huge roundoff errors (e.g., division by a small quantity). On the other hand, the classes of algorithms using operations from the set S_2={+,-,*,/} or from the set S_3={+,-,*} are the most studied in complexity theory, and are used, e.g., to obtain fast parallel algorithms for numerical problems. In this paper, we study, by using a simulation argument, the relative power of the sets S_1, S_2, and S_3 for computing with approximations. We prove that S_2 does very efficiently simulate S_1, while S_3 does not; this fact shows and measures the crucial role of division in computations introducing roundoff errors. We also show how to construct algorithms using operations {+,-,*,/} which achieve for most inputs the same error bounds as algorithms using operations {+,-,*,/,>}. To develop our simulation strategy we combine notions imported from approximation theory and topology with complexity and error bounds. More precisely, to find conditions under which this simulation can take place, we quantitatively describe the interplay between algebraic, approximation, topological, and complexity notions and we provide lower and upper bounds on the cost of simulation.

Bibliographic Notes

ICSI Technical Report TR-92-026

Abbreviated Authors

K. Aberer and B. Codenotti

ICSI Publication Type

Technical Report