tag:blogger.com,1999:blog-8781383461061929571.post8809133007327464446..comments2024-03-14T09:08:19.035-04:00Comments on OR in an OB World: Numerical Analysis: Size MattersPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-8781383461061929571.post-70504835539815070792013-08-09T20:32:34.941-04:002013-08-09T20:32:34.941-04:00I see now. That explains the "stochastic"...I see now. That explains the "stochastic" part of "stochastic arithmetic". I had thought it was a reference to how my former students did computations. :-)Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-71838449871533796212013-08-09T19:28:55.857-04:002013-08-09T19:28:55.857-04:00That is correct : "exact" interval arith...That is correct : "exact" interval arithmetic is too pessimistic and very soon reaches a ]-inf..+inf[ confidence interval. The difference with stochastic (interval) arithmetics is that computations are randomized - that wasn't obvious from my explanations. As a result you really have a probabilistic confidence interval meaning the result is in [a,b] with a 95% confidence. The more times you compute each computation with randomized rounding modes, the more precise is your interval. With 3 computations you can get around 90% if I remember correctly. And to gain a few percentages more you have to start increasing in a very significant way the number of samplings, making the method unpractical.DOFPnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-33447567337432025042013-08-09T15:04:18.998-04:002013-08-09T15:04:18.998-04:00Thanks for the comment (and link!). I vaguely reca...Thanks for the comment (and link!). I vaguely recall some mention of "interval arithmetic" when I took numerical analysis (while basking in the warmth from the mainframe's vacuum tubes). IIRC, propagating the intervals seemed to quickly achieve results along the lines of 0.0 +/- infinity; but precisions were quite a bit lower then and the number of numerical operations in any given chain (from input value to final result) may not have grown commensurately, so propagation may not hemorrhage accuracy quite so fast these days.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-70144598996647818832013-08-09T14:23:33.088-04:002013-08-09T14:23:33.088-04:00There is a technique called CESTAC based on stocha...There is a technique called CESTAC based on stochastic arithmetic to correct the rounding errors.<br />The idea is that you can control the rounding method in modern processors due to the IEEE754 norm and do each computation 3 times (low rounding, average, up rounding) which gives you a confidence interval. Once that's done you can propagate the confidence interval to have information of how precise your computation really is.<br /><br />In your example it would give you something like (x - y) = 0 +/- 10^-12<br />Then you can see when computations are unstable and use a better algorithm (or live with it...)<br /><br />http://www-pequan.lip6.fr/cadna/Cadna_Dir/What_is_CADNA.phpDOFPnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-65926964864634527572013-08-04T17:33:24.344-04:002013-08-04T17:33:24.344-04:00David: Thank your for the comment. I taught those ...David: Thank your for the comment. I taught those recurrence relations in a previous life (not that I recall them precisely), but had very limited experience with applying them, so it had not occurred to me that rounding errors could seriously degrade the results. Working outward from the largest probability is an interesting idea. I'm not sure it would have occurred to me.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-29294338873199167852013-08-04T15:49:41.196-04:002013-08-04T15:49:41.196-04:00One of the areas of OR where this might matter is ...One of the areas of OR where this might matter is concerned with steady state probabilities for queue models. Solving the equations in many cases leads to a recurrence relation p_{n+1}=(some expression)*p_n, and then an explicit formula for p_0.<br /><br />However, for multiple server queues with limited waiting room, p_0 may be very small, and this made the recurrence subject to numerical errors of the kind discussed. I found that a good way round the problem was to find N such that p_N was maximal, and calculate that explicitly, then use the recurrence to find the other steady state probabilities.lookatstlshttps://www.blogger.com/profile/16624138600581153624noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-18043852883712896962013-08-02T10:27:00.836-04:002013-08-02T10:27:00.836-04:00Oops! You are of course correct. (Just heard a kno...Oops! You are of course correct. (Just heard a knock on the door. I think they've come to rescind my math degrees.)Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-5560059814208790102013-08-01T23:37:28.818-04:002013-08-01T23:37:28.818-04:00One minor error in your posting- it's not that...One minor error in your posting- it's not that floating point addition isn't commutative (it is), but rather that it isn't associative. That is, a+b and b+a will always give you the same answer, but (a+b)+c and a+(b+c) may give different answers due to rounding of the intermediate result. Brian Borchershttps://www.blogger.com/profile/18216044824246034466noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-65617030800998307372013-08-01T18:11:20.955-04:002013-08-01T18:11:20.955-04:00Thomas, thanks for the links. I was unaware of eit...Thomas, thanks for the links. I was unaware of either example.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-38745196301596774242013-08-01T17:46:16.969-04:002013-08-01T17:46:16.969-04:00Some additional links for the readers that do not ...Some additional links for the readers that do not know which consequences such errors can have:<br /><br />http://en.wikipedia.org/wiki/Ariane_5_Flight_501#Launch_failure<br />http://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dhahran<br /><br />Best regards,<br />ThomasThomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.com