On the Power of Discontinous Approximate Computations
Title | On the Power of Discontinous Approximate Computations |
Publication Type | Technical Report |
Year of Publication | 1992 |
Authors | Aberer, K., & Codenotti B. |
Other Numbers | 731 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1992/tr-92-026.pdf |
Bibliographic Notes | ICSI Technical Report TR-92-026 |
Abbreviated Authors | K. Aberer and B. Codenotti |
ICSI Publication Type | Technical Report |