tl;dr we need to raise the standards and "get it right".
On getting different answers...
Some algorithms in computational mathematics use random
values. Depending on the source of random values you might
get different but correct answers. Random algorithms can
be very much faster than deterministic ones and might even
be the only available algorithms.
In Axiom the test is marked as using a random value so a
test which does not produce the same result every time is
still considered valid.
I do not know if Sage uses such algorithms and I do not
know if that is the source of your failure. If not, then
as you point out, the result is quite troubling. This might
be hard to establish in Sage as it uses several different
subsystems in some computations and who knows if they use
random algorithms?
On software engineering....
One needs to understand a problem to write correct software.
What is not understood will be where the problems arise.
Sage has the advantage of being written by domain experts
so the algorithms are likely of high quality. Unfortunately,
they rest on many layers of algorithms with many assumptions
(it is kittens all the way down).
Most current systems, at least in this generation, have the
participation of some of the original authors so problems
can be understood and fixed. That will not be true in the
future (some of the Axiom's many authors have died).
In software engineering terms the question is, what happens
when the world expert in some area, such as Gilbert Baumslag
in Infinite Group Theory, writes a program to solve a problem
which later fails? The failure could be due to his lack of
understanding of underlying implementation details or it could
be because an upstream system has changed an assumption, as
is being discussed on another thread. That is, "code rot".
Without Gilbert, who can debug it? Do you throw the subsystem
away, as has been discussed with SYMPOW? If you do then you
have given up real expertise. If you don't then you can't trust
the results. It could be many years before another infinite
group theory AND computational mathematics expert can find and
fix the bug. Meanwhile, the code will continue to rot as more
things change under it.
Who can debug this in 30 years? ...
There are three potential attacks on this problem, documentation,
standard test suites, and program proofs.
Sage has been making doctests which are useful for bringing
potential failures to attention. Other than simple checks and
possible user examples they are useless for other purposes.
*Documentation* should consist of a detailed discussion of
the algorithm. Since we are doing computational mathematics the
discussion has to have both a mathematical part and an implementation
part. Since "computational mathematics" is not (yet) a widespread
and recognized department of study at many U.S. universities,
the authors of today are likely weak in either the mathematics or
the implementation. Hopefully this will change in the future.
*Standard test suites*, which involves testing the results against
published reference books (Schaums, Luke, A&S, Kamke, etc) This can
make the testing less ad-hoc. These tests also allow all of the
other systems to publish their compliance results. All software
engineers know that you can't write your own tests so this is a
good way to have a test suite and an excellent way to show users
that your system gets reasonable results.
*Program proofs* are important but not yet well established in this
area. In prior centuries a "proof" in mathematics involved a lot
of "proof by authority" handwaving. In the 20th century the standard
of a mathematical proof was much more rigorous. In computational
mathematics, if we have proofs at all they are likely just some
pre-rigorous handwaving that ignores implementation details.
Worse yet, almost none of the systems so far have any kind of
theoretical scaffolding on which to hang a proof. If you don't
know what a Ring is and you don't have a strong definition of a
Ring underlying your implementation choices, how can you possibly
proof the code correct?
Developing computational mathematics for the long term....
For *documentation*, I believe that we should require literate programs
which contain both the theory and the implementation. Each algorithm
should be of publication quality and peer-reviewed. (Carlo Traverso and
I have proposed a computational mathematics journal that accepts only
literate programs.) You should be able to go to a conference talk,
download the literate paper from a URL (hopefully a peer-reviewed
journal), and "execute the paper" during the presentation on your
system. Imagine the power of pointing out an algorithm failure
"in real time" and the pressure to make sure you get it right.
For *standard test suites*, I believe we should have these in many
different areas. We should collect a set of reference books that are
fairly comprehensive and jointly develop tests that run on all systems.
Rubi is doing this with rule based integration.
http://www.apmaths.uwo.ca/~arich/
Axiom is doing this with the Computer Algebra Test Suite
http://axiom-developer.org/axiom-website/CATS/index.html
If we publish and maintain the test suite results for all systems
there will be great pressure to conform to these results, great
pressure to develop standard algorithms that everyone uses, and
great pressure to improve areas of weakness.
For *program proofs* I can see where ACL2 and COQ can be integrated
into systems so that a published paper can include an automated
proof. This will raise the standard expected for professional
publications in computational mathematics. It will also move us
away from depending on domain experts who have the unfortunate
tendency to die off, both personally and professionally.
The 30 year horizon ...
We are nearly 50 years into computational mathematics.
It is time to develop departments and textbooks, raise the level
of expectation for peer-reviewed publications, develop not only
software engineering practices but also computational engineering
practices. Computational mathematics is the one area of software
where you can independently check your answers and you can expect
to write timeless software that gets the same answers 30 years later.
It really is worth the time to get it right.
To bring this diatribe back to earth and the original subject,
you have identified a symptom of a much larger problem with the
current systems. Unfortunately there is no peer-pressure to have
higher standards. I was hoping that the NIST Digital Library of
Mathematical Functions would be the touchstone of algorithms but
that is clearly not the case.
Perhaps someday there will be sub-department of the NSF that
tried to organize, guide, and fund it but nobody there has
"the vision and the will" to get it done. Maybe we should
nominate William as an NSF director :-)
Tim Daly
Dr. David Kirkby wrote:
On 08/24/10 02:06 PM, kcrisman wrote:
Anyway, I think (as you have correctly noted before) we have a bit of
a culture clash between software engineering and mathematics.
<SNIP>
Just have patience with those of us who aren't from a software
background - and trust that we are trying hard to internalize your
lessons, but that we have more immediate needs to fill as well for our
next course or paper. I think that just as Minh's messages about
documentation are slowly taking hold in the whole ecosystem, so are
yours about software engineering.
- kcrisman
Just to make a point, my own background is not software engineering.
My first degree is in electrical and electronic engineering, my
masters in microwaves and optoelectronics and my PhD in medical
physics. Apart from a very brief spell (about 6 months), I have never
worked in the IT industry.
I first became aware of the subject of software engineering when an
Australian guy joined the department I worked at University College
London. Russel's task was to develop some hardware and software for a
research project. He quite rightly realised that developing software
"by the seat of your pants" as he called it was not the way to go
about it. So before starting to write the software, he purchased a
book on the subject of software engineering.
I never gave this topic much more thought until I started working on
Sage. I then because to realise that Sage needs to take a more
professional approach to the development, as it seems a bit add-hock
to me.
My own view is I'd rather have something with less features, which I
could rely on, than lots of features I don't trust. When there is
little in the way of project management, and a culture of not doing
anything properly, then attitude tends to spread like a virus.
I'm currently running the doctests 100 times on a machine, with the
same build of Sage that passed all doc tests. This is an interesting
failure I observed:
sage -t -long devel/sage/doc/en/constructions/linear_algebra.rst
**********************************************************************
File
"/export/home/drkirkby/sage-4.5.3.alpha2/devel/sage-main/doc/en/constructions/linear_algebra.rst",
line 202:
sage: A.eigenvalues()
Expected:
[3, 2, 1]
Got:
[3, 1]
**********************************************************************
The tests have been run 41 times now, and only once has that test
failed. The answer looks quite reasonable, but I assume is wrong, as
the other 40 times the code gave the expected value. It's these sorts
of things that concern me. Why should the same build of Sage, running
exactly the same doctests each time, not produce repeatable results?
There's been a few failures, though that is the only one I've noticed
where the answer looks very reasonable, but is in fact incorrect.
Dave
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
