Group Abstract Group Abstract

Message Boards Message Boards

5
|
28.3K Views
|
14 Replies
|
21 Total Likes
View groups...
Share
Share this post:

The Misfortunes of a Trio of Mathematicians Using Computer Algebra Systems

Posted 11 years ago

Please, read the following article to appear in next month's issue of the Notices of the American Mathematical Society: http://www.ams.org/notices/201410/rnoti-p1249.pdf Thank you!

14 Replies

Thank you for the explanation, it clarifies a lot! And good to hear that the determinant bug has been squished...

POSTED BY: Sander Huisman

Well then, here is (considerably) more detail. I'll first remark that this is only my own take on the issues and events, and does not necessarily reflect or represent the views of Wolfram Research.

The main focus of the article was on certain problematic matrix determinant computations. The authors were, understandably, unhappy with the erroneous results they were getting. Suffice it to say that we were too. With the recent release of version 10.0.2 we now, happily, have it fixed. But the concerns run deeper than simply "here is this bug". So I'll address in more detail some of the specific issues raised in that article, and provide a current status report.

Here is some background history. First I should mention that the authors have been in contact with us about this integer determinant problem. They initially alerted us to an example in October 2013, roughly a year before publication of the article. In that instance the erroneous integer matrix determinant was tracked to a simple typo (it happens), and fixed. The repair appeared in Mathematica 10.0.0, released July of this year (that was, to the best of my knowledge, the first release following our becoming aware of the issue).

That should have been the end of the story. So what happened? In this instance we had a superficial problem hiding a deeper one. The latter simply did not manifest itself in the example we first saw. We became aware of this second problem only in August of this year, when the authors let us know there were examples that still gave erroneous results in a somewhat random manner.

As it happens, at the time we learned of this we were nearing the end of a test-and-fix cycle prior to releasing version 10.0.1. Again the bug was found and repaired (well, actually squashed into bug juice, to give the technical description). This fix and numerous others have been released quite recently in version 10.0.2.

The fact that the article appeared before the repair is perhaps unfortunate for us, but that's life. What I take to be the main point of the article remains every bit as important as before: sophisticated mathematical software uses some intricate algorithms, and one should be aware of the potential for erroneous results. That this problem appeared only in version 9 is in fact due to our frequent adaptation of cutting edge methods: earlier versions used a more pedestrian method that was not prone to this particular issue. Not surprisingly, the computations in question were also generally slower.

As one who has often delved into code for symbolic integration I will also comment on the three examples from that area that also were noted in the article. I'll start with a possibly controversial remark. I hold the opinion the three errant integrals do not comprise not terribly serious bugs. Improvements, to be described below, have been made. But the lower severity level should help to explain why these did not show up in version 10.0.2: they simply have nowhere near the priority of the determinant problem, and there are risks to "fixes" that have not had time for thorough testing and assimilation.

So let us have a look at these examples. The first concerns this integral.

Integrate[Sqrt[(2 t)^2 + (4 - 3 t^2)^2], {t, 0, 2}]

The result given is simply wrong. What happens is we calculate the antiderivative (indefinite integral) and try to determine if there are singularities on the path of integration. We find none, evaluate at the endpoints a la the Newton-Leibniz method, and give a (numerically incorrect) result. Why do we miss the path singularities? A rough explanation is that it is borderline hopeless to find these when elliptic functions with complicated innards are involved.

By the time the article appeared we had already made this example instead return unevaluated; that happened in response to a different but related bug report. This change is deemed a relatively minor one and was not ported to version 10.0.2. (When will it appear? More on that presently.) I will remark that this change comes at a cost: we lose closely related integrals that were done just fine when the path did not include singularities. In this case the singularity is larger than 1. So integrating from 0 to 1 was working correctly and yet, in the version currently under development, it is unevaluated.

Here is the second integral.

In[473]:= Integrate[Exp[-p*t]*(Sinh[t])^3, {t, 0, Infinity}]

Out[473]= ConditionalExpression[6/(9 - 10 p^2 + p^4), 0 < Re[p] < 1 && Im[p] == 0]

The authors point out that this is flat-out wrong. The correct result requires that p be real valued and larger than 3. When I first read the article, my reaction was that, of the three integrals, certainly this one should be handled better (the other two posing more serious difficulties). Further analysis showed that the error was due to a simple bug in the code that does the asymptotic analysis. The version in development gives instead the correct conditions: ConditionalExpression[6/(9 - 10*p^2 + p^4), Re[p] > 3 && Im[p] == 0]

The third integral in the article, shown below, incorrectly gives a result of zero.

In[474]:= Integrate[Integrate[Abs[Exp[2*Pi*I*x] + Exp[2*Pi*I*y]], {x, 0, 1}], {y, 0, 1}]

When there is an explicit iterated integral, I generally find it better to put it into the form of a multiple integral, as below.

In[475]:= Integrate[Abs[Exp[2*Pi*I*x] + Exp[2*Pi*I*y]], {x, 0, 1}, {y, 0, 1}]

In[513]:= Integrate[Integrate[Abs[Exp[2*Pi*I*x] + Exp[2*Pi*I*y]], {x, 0, 1},
  Assumptions -> 0 <= y <= 1], {y, 0, 1}]

Out[513]= 4/\[Pi]

Here is my take. The original formulation of this integral goes astray early on, due to a problematic combination of a symbolic parameter, complex values in intermediate computations, and a nonanalytic function (Abs in this case) whose path singularities are difficult to pin down absent knowledge of that parameter. In the development version there have been improvements to this family of integrals although the hardest issue, in this single inner integral, remains.

So when will the these improvements appear? A more subtle question, one often not recognized, is this: Will these be released at all? Whenever changes go into the product there is the potential of a ripple effect. For example, disabling the elliptic integral in that first example could conceivably have a deleterious effect on exact computations involving regions, or probabilities, or... It will take some time, and the ministrations of the QA group, before we decide whether it is preferable to lose working examples or return unevaluated. I am fairly confident that the change resulting in the better outcome for that second integral will survive testing. So that at least should emerge in a future release. The variant of the third example that was addressed falls somewhere in the middle, in terms of risk vs. reward (of the fix). I am cautiously optimistic that it too will not cause damage downstream, and will appear in a future release. But such optimism is never a guarantee, and long experience with definite integration teaches that one should temper one's expectations in this area.

I hope this gives some idea of how we view the specific problems raised in the article, and also some idea of how we triage and address erroneous results in general.

POSTED BY: Daniel Lichtblau

If folks here are interested in more details surrounding the particular issues in question, I could try and see about getting one of our senior developers to write something up (no promises, as we are all pretty busy).

Go ahead! Rest assured that many of the community contributors are senior and many of them are pretty busy too.

POSTED BY: Udo Krause

Just a quick update on the problems the authors encountered in the Durán et al. article:

As we all know, there's an infinite amount of math computations out there, and we do a tremendous amount of testing but it's always possible to miss something. We thank the article's authors for pointing out these particular bugs which have now been fixed with last week's Mathematica 10.0.2 release.

I should note that we ran a blog post in 2007 by Stephen Wolfram that addresses these kinds of issues, and is worth revisiting:

Mathematics, Mathematica, and Certainty

A relevant extract:

"We run millions and millions of tests on every version of Mathematica, trying to exercise every part of the system. And doing that is orders of magnitude more powerful at catching bugs than any kind of pure human testing.

Sometimes we use the symbolic capabilities of Mathematica to analyse the raw code of Mathematica. But pretty quickly we tend to run right up against undecidability: thereÂ’s a theoretical limit to what we can automatically verify."

If folks here are interested in more details surrounding the particular issues in question, I could try and see about getting one of our senior developers to write something up (no promises, as we are all pretty busy).

POSTED BY: Andre Kuzniarek

Hi David, I agree with the general approach and attitude outlined in the first paragraph of your post. But as Frank Kampas indicated, there is a certain "triage" perspective that has to be taken when a product like Mathematica is developed.

More precisely, we can say that the "hierarchical approach" you talk about is basically transparency of the algorithms. That transparency of the "high-power routines" can be done in two ways: (i) with API's of sub-routines, as you suggested, and (ii) by detailed documentation with computation examples, comparisons, etc. WRI tries to do both, but WRI's "triage" might produce different outcomes than what ambitious or power users might expect.

POSTED BY: Anton Antonov
POSTED BY: Leslie Roberts

The part where they state that:

a = Det[bigMatrix];
b = Det[bigMatrix];

give different results is solved in my version of Mathematica (10.0.1.0). Try e.g.:

basicMatrix=Table[Table[RandomInteger[{-99,99}],{i,1,14}],{j,1,14}];
powersMatrix=DiagonalMatrix[10^{123,152,185,220,397,449,503,563,979,1059,1143,1229,1319,1412}];
smallMatrix=Table[Table[RandomInteger[{-999,999}],{i,1,14}],{j,1,14}];
bigMatrix=basicMatrix.powersMatrix+smallMatrix;
Do[
  a=Det[bigMatrix];
  b=Det[bigMatrix];
  Print[a==b]
,
  {10}
]
POSTED BY: Sander Huisman
POSTED BY: Sander Huisman

It could very well be that they implemented a more efficient algorithm in version 8, that works for 99.999% of the cases and therefore got unnoticed.

I am pretty sure that Wolfram does some heavy testing of before bringing out a product (self-tests). You should also note that these calculations were done using large integer arithmetic, for the cases of machine numbers it works fine...

Of course this should never have happened, and I hope that they take this seriously, as this big could affect a lot of other parts of Mathematica too...

POSTED BY: Sander Huisman
POSTED BY: Udo Krause
POSTED BY: Udo Krause

If only there was a paper written for every software bug ever found in a computer algebra system...

POSTED BY: Ilian Gachevski

Due to finite resources, software companies are forced to ignore problems that only affect a very small number of users. One software company I worked for had an explicit "triage" policy. Big problems affecting important customers were fixed immediately; most reported problems were fixed in the next release and some were never fixed.

POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard