[Trilinos-Users] Floating-point arithmetic is non-associative

[Mark Hoemmen]

On Jun 15, 2011, at 10:53 AM, Conjeepuram Subramanian, Natarajan wrote:
> Mark, I understand your logic about FP arithmetic not being associative
> and that being the reason for different answers but I am still a little
> unsure how you can guarantee it to be commutative?

The IEEE floating-point standard guarantees commutativity of individual operations.  See e.g., IEEE 754-2008, Section 10.4.  Specifically, a+b and b+a should always produce the same answer on the same machine when run twice.  This was true before IEEE 754-1985 except for a few anomalous machines.

Combinations of operations may result in apparent non-commutative behavior, depending on how rounding is performed.  (a*b) + (c*d) will produce the same result as (c*d) + (a*b) on the same machine and compiler, but different results on different machines or compilers, depending on how rounding is done.  See e.g., F. Ris, E. Barkmeyer, C. Schaffert, & P. Farkas 1993.  (Factors causing this include 80-bit vs. 64-bit temporaries, and fused multiply-add.)

> I am going to be an ignoramus and ask a naive question.
> Say a reduce with 3 procs, predefined op. as product and values a(p0),
> b(p1), c(p2). a, c very large and b very small (All floats with ac >
> max(float) and ab and bc <<< max(float)). I would think this would work
> and give correct results only if a, b, and c are in procs 0, 1, and 2 or
> some good combination thereof where the prod. ac is guaranteed to be not
> computed before ab/bc!
> 
> Is this not correct? As I know all predefined operations are assumed to
> be both associative and commutative and you can turn of commutative by
> creating your own op. but not associative. so in this case would the
> previous example be considered a case of non-associative behaviour?

Yes, it would be, if I understand correctly.  Let me restate your question, just to make sure that I understand:  

1. a and c are very large, and b is very small.  a, b, c > 0. 
2. In particular, fl(ac) = Inf, fl(ab) < Inf, fl(bc) < Inf.  
3. Compute a*b*c.

Associativity, or the lack thereof, relates to the choice of parenthesization: (ab)c  vs.  a(bc).  Commutativity only comes into play if you rearrange the terms in the product.  However, you can't get (ac)b (for example) without using associativity as well.  For example:

a(bc) -> a(cb) (commutativity) -> (ac)b (associativity)
(ab)c -> (ba)c (commutativity) -> b(ac) (associativity) -> (ac)b (commutativity)

A simpler example of non-associative floating-point behavior would be this: let e = (machine precision / 2).  Let fl( x+y ) denote the floating-point representation of the result of x + y, where x and y each can be represented exactly in floating-point arithmetic (fl(x) = x, fl(y) = y).  Then fl( (1+e) + e ) = 1, but fl( 1+(e+e) ) = 1 + 2e != 1.

mfh