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

[Conjeepuram Subramanian, Natarajan]

Mark,
       Thanks for the response and making the question more
understandable! This cleared a misconception I have been carrying; I do
need to read the standards a lot better too!

Thanks again,

C.S.N
        

-----Original Message-----
From: trilinos-users-bounces at software.sandia.gov
[mailto:trilinos-users-bounces at software.sandia.gov] On Behalf Of Mark
Hoemmen
Sent: Wednesday, June 15, 2011 1:44 PM
To: Conjeepuram Subramanian, Natarajan
Cc: Heroux, Michael A; trilinos-users at software.sandia.gov
Subject: Re: [Trilinos-Users] Floating-point arithmetic is
non-associative

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





_______________________________________________
Trilinos-Users mailing list
Trilinos-Users at software.sandia.gov
http://software.sandia.gov/mailman/listinfo/trilinos-users