Probabilistic interval-valued computation: Toward a practical surrogate for statistics inside CAD tools

Amith Singhee, Claire F. Fang, James D. Ma, Rob A. Rutenbar

Research output: Contribution to journalArticle

Abstract

Interval methods offer a general fine-grain strategy for modeling correlated range uncertainties in numerical algorithms. We present a new improved interval algebra that extends the classical affine form to a more rigorous statistical foundation. Range uncertainties now take the form of confidence intervals. In place of pessimistic interval bounds, we minimize the probability of numerical "escape"; this can tighten interval bounds by an order of magnitude while yielding 10-100× speedups over Monte Carlo. The formulation relies on the following three critical ideas: liberating the affine model from the assumption of symmetric intervals; a unifying optimization formulation; and a concrete probabilistic model. We refer to these as probabilistic intervals for brevity. Our goal is to understand where we might use these as a surrogate for expensive explicit statistical computations. Results from sparse matrices and graph delay algorithms demonstrate the utility of the approach and the remaining challenges.

Original languageEnglish (US)
Article number4670058
Pages (from-to)2317-2330
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume27
Issue number12
DOIs
StatePublished - Dec 1 2008

Keywords

  • Algorithms
  • Arithmetic
  • Design automation
  • Error analysis
  • Interval arithmetic
  • Simulation
  • Statistics
  • Variational methods

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Probabilistic interval-valued computation: Toward a practical surrogate for statistics inside CAD tools'. Together they form a unique fingerprint.

  • Cite this