Publication Details
Title: Checking Approximate Computations Over the Reals
Author: S. Ar, M. Blum, B. Codenotti, and P. Gemmell
Group: ICSI Technical Reports
Date: May 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-030.pdf
Overview:
This paper provides the first systematic investigation of checking approximate numerical computations, over subsets of the reals. In most cases, approximate checking is more challenging than exact checking. Problem conditioning, i.e., the measure of sensitivity of the output to slight changes in the input, and the presence of approximation parameters foil the direct transformation of many exact checkers to the approximate setting. We can extend exact checkers only if they have a very smooth dependence on the sensitivity of the problem. Furthermore, approximate checking over the reals is complicated by the lack of nice finite field properties such as the existence of a samplable distribution which is invariant under addition or multiplication by a scalar. We overcome the above problems by using such techniques as testing and checking over similar but distinct distributions, using functions' random and downward self-reducibility properties, and taking advantage of the small variance of the sum of independent identically distributed random variables.
Bibliographic Information:
ICSI Technical Report TR-92-030
Bibliographic Reference:
S. Ar, M. Blum, B. Codenotti, and P. Gemmell. Checking Approximate Computations Over the Reals. ICSI Technical Report TR-92-030, May 1992
Author: S. Ar, M. Blum, B. Codenotti, and P. Gemmell
Group: ICSI Technical Reports
Date: May 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-030.pdf
Overview:
This paper provides the first systematic investigation of checking approximate numerical computations, over subsets of the reals. In most cases, approximate checking is more challenging than exact checking. Problem conditioning, i.e., the measure of sensitivity of the output to slight changes in the input, and the presence of approximation parameters foil the direct transformation of many exact checkers to the approximate setting. We can extend exact checkers only if they have a very smooth dependence on the sensitivity of the problem. Furthermore, approximate checking over the reals is complicated by the lack of nice finite field properties such as the existence of a samplable distribution which is invariant under addition or multiplication by a scalar. We overcome the above problems by using such techniques as testing and checking over similar but distinct distributions, using functions' random and downward self-reducibility properties, and taking advantage of the small variance of the sum of independent identically distributed random variables.
Bibliographic Information:
ICSI Technical Report TR-92-030
Bibliographic Reference:
S. Ar, M. Blum, B. Codenotti, and P. Gemmell. Checking Approximate Computations Over the Reals. ICSI Technical Report TR-92-030, May 1992