
arXiv: 1507.03331
handle: 10044/1/29366 , 10044/1/42670
Roundoff errors cannot be avoided when implementing numerical programs with finite precision. The ability to reason about rounding is especially important if one wants to explore a range of potential representations, for instance, for FPGAs or custom hardware implementations. This problem becomes challenging when the program does not employ solely linear operations as non-linearities are inherent to many interesting computational problems in real-world applications. Existing solutions to reasoning possibly lead to either inaccurate bounds or high analysis time in the presence of nonlinear correlations between variables. Furthermore, while it is easy to implement a straightforward method such as interval arithmetic, sophisticated techniques are less straightforward to implement in a formal setting. Thus there is a need for methods that output certificates that can be formally validated inside a proof assistant. We present a framework to provide upper bounds on absolute roundoff errors of floating-point nonlinear programs. This framework is based on optimization techniques employing semidefinite programming and sums of squares certificates, which can be checked inside the Coq theorem prover to provide formal roundoff error bounds for polynomial programs. Our tool covers a wide range of nonlinear programs, including polynomials and transcendental operations as well as conditional statements. We illustrate the efficiency and precision of this tool on non-trivial programs coming from biology, optimization, and space control. Our tool produces more accurate error bounds for 23% of all programs and yields better performance in 66% of all programs.
Technology, POLYHEDRA, floating-point arithmetic, Correlation sparsity pattern, correlation sparsity pattern, Numerical & Computational Mathematics, polynomial optimization, proof assistant, FOS: Mathematics, roundoff error, Semidefinite programming, Mathematics - Numerical Analysis, formal verification, GLOBAL OPTIMIZATION, cs.NA, 0802 Computation Theory and Mathematics, Science & Technology, Roundoff error, numerical accuracy, ALGORITHMS, Software Engineering, Numerical Analysis (math.NA), semidefinite programming, 004, sums of squares, hardware precision tuning, SDP-RELAXATIONS, fixed-precision arithmetic, 0806 Information Systems, Physical Sciences, Computer Science, Applied, LIBRARY, transcendental functions, Mathematics
Technology, POLYHEDRA, floating-point arithmetic, Correlation sparsity pattern, correlation sparsity pattern, Numerical & Computational Mathematics, polynomial optimization, proof assistant, FOS: Mathematics, roundoff error, Semidefinite programming, Mathematics - Numerical Analysis, formal verification, GLOBAL OPTIMIZATION, cs.NA, 0802 Computation Theory and Mathematics, Science & Technology, Roundoff error, numerical accuracy, ALGORITHMS, Software Engineering, Numerical Analysis (math.NA), semidefinite programming, 004, sums of squares, hardware precision tuning, SDP-RELAXATIONS, fixed-precision arithmetic, 0806 Information Systems, Physical Sciences, Computer Science, Applied, LIBRARY, transcendental functions, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 70 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
