Re: [Axiom-developer] Symbolic Algorithms Standards

[daly]

Paul, Burcin,

Excellent. Thanks for the pointers.

Keith Geddes, Stephen Czapor, and George Labahn did an excellent job
with their book "Algorithms for Computer Algebra". It would be good to
have something similar coupled with actual executable algorithms so they
can be tested and used. There also needs to be an ongoing effort to 
connect to the published literature to keep the algorithms up to date.

I have started a depth-first literature collection at
http://axiom-developer.org/axiom-website/lattice.html
(mouse over items for the bibliography data).
I plan to link to open versions of papers.

Once the raw citation data starts converging a bit the next step
seems to be to create "threads" from recent publications back to
the earlier algorithms so people can see how the Risch-with-Dilogarithms
is connected to prior Risch work. There needs to be some creative GUI
work done to make this nagivation intuitive (a lattice?).

Crucial to the whole effort, in my mind, are clear explanations of
the algorithms. This is mathematics, after all, so there should be
no magic involved.

>> A wikipedia-like collection would be nice, where everybody could
>> contribute, discuss, add pointers, ...

My experience with Wikis is that this is where information goes to die.
Wikipedia is an exception to that observation but their mental model
existed already. Wikis don't have a mental model for people to follow
so they tend to get lost. Wikis also suffer from the "commons" problem
in that everyone uses but almost no-one contributes. 

A book-like model seems to fit better, something along the lines of
the Geddes book. 

It is important to have a "standards" approach to the effort, hence
the appeal to the "NIST-Standard" mental model. One could reasonably
expect to get the same answer from different systems. On any given
system there might be "extensions" (e.g. answers for multiple branch
cuts, etc) but the "standard" algorithm should be available.

>> 
>> Note we already have the Collected Algorithms from the ACM:
>> http://calgo.acm.org/.

The ACM Collected Algorithms is excellent as far as it goes.  It is
really necessary to have working code for an algorithm repository.
And they do provide literature references.

The ACM Collected Algorithms seems to target numerical algorithms,
at least all of the ones I downloaded. There doesn't seem to be 
any attempt at organization beyond collection.

Symbolic algorithms tend to have much deeper "towers" of algorithms
than numeric ones. Symbolic integration depends on, say, symbolic
factoring. There is a need for organization to take advantage of
lower-level standard algorithms.

Beyond that, there needs to be a good test suite. I've spent some time
on a "Computer Algebra Test Suite" (CATS). See
http://axiom-developer.org/axiom-website/CATS/index.html 
which has tests against published collections of integrals and
differential equations. As an aside, I've found some mistakes in the
published works. I've also been building some tests against the 
"CRC Standard Curves and Surfaces" for the graphics.

These tests should be tightly coupled to the published "standard"
algorithms. That way we know what the expected results of a correct
implementation should be. After all, the goal is to get the same
answer no matter which system is used.

>> Also in Sage you have the related "get_systems" command, which tells
>> you which systems were used when you perform a computation:
>> 
>> sage: from sage.misc.citation import get_systems
>> sage: get_systems('random_matrix(ZZ,250).determinant()')
>> ['MPFR', 'GMP']
>> 
>> We could imagine a similar "get_algorithms" command:
>> 
>> sage: get_algorithms('integrate(1/tan(1+x), x)')
>> ['Risch', 'Liouville', 'arxiv079645',
>> 'http://hal.inria.fr/hal-00644166']

Indeed. I am currently instrumenting Axiom to show exactly which
algorithms are used at any level of detail. The 'Risch' algorithm
has many different implementation details depending on which kind
of expression you're trying to implement. Axiom lists 33 different
"integrate" functions, depending on the domain of the arguments.
Unwinding and documenting this is expected to take a fair amount
of time.

Tim