6
$\begingroup$

There's tons of research on program transformations for optimization. Is there any research on transformations that improve numeric stability? Examples of such transformations might include:

  • Transform $\log(\exp(a)+\exp(b))$ into $\max(a,b)+\log(\exp(a-\max(a,b))+\exp(b-\max(a,b)))$
  • Convert multiplication of an inverse matrix times a vector into the solution to a linear system solver.
  • Automatically perform multiplications of small numbers in the log domain.

All the tricks I'm aware of for better numeric stability like this are pretty standard and something that every "good" numeric programmer always does. Since the tricks are so standard and always applied, it makes sense that the compiler might be able to do them for us.

$\endgroup$
  • $\begingroup$ there is a lot of research on stability of floating point operations as implemented in arithmetic coprocessors/ ALUs... applicable? maybe too low level in comparison? anyway such optimizations you describe are probably a little "too big" to be done automatically... $\endgroup$ – vzn Aug 6 '15 at 20:40
8
$\begingroup$

There actually is some research on improving the numerical stability of floating point expressions, the Herbie project. Herbie is a tool to automatically improve the accuracy of floating point expressions. It's not quite comprehensive, but it will find a lot of accuracy improving transformations automatically.

Cheers,

Alex Sanchez-Stern

$\endgroup$
  • $\begingroup$ Wouldn't Herbie be a good fit for directly operating on lispy/homoiconic and functional languages such as clojure, where homoiconicity means that any "mathy" program portion can be deterministically and easily parsed into math? as opposed to OO and non-purely-functional languages where code parsing requires compiler-level code replication/mimicking $\endgroup$ – matanster Jun 22 '17 at 4:17
3
$\begingroup$

A quite interesting piece of work is a stochastic approach of Schkufza, Sharma and Aiken. Note that in general, the code is not guaranteed to be correct, but they give a really nice argument for probabilistic correctness. Stochastic Optimization of Floating-Point Programs with Tunable Precision, PLDI 2014.

Edit: The above work is designed to optimize for speed while keeping (stochastic) correctness. It may be possible to use it for the opposite purpose though (see my comment below).


I just thought of some work more related to Alex Stern's reference, by Thomas Wahl and Jaideep Ramachandran that can be found here.

$\endgroup$
  • $\begingroup$ It looks like they want faster programs at the expense of potentially worse stability. This is interesting! But I'm more interested in going the other direction: better stability at the expense of speed. $\endgroup$ – Mike Izbicki Aug 7 '15 at 23:04
  • $\begingroup$ That's true, I'll amend my answer. Note that it isn't clear to me that a modification of the $c({\cal R};{\cal T})$ function on page 3 might allow optimizing for precision while keeping speed acceptable. $\endgroup$ – cody Aug 8 '15 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.