Re: Ann: symbolic multinomial algebra

[Craig Carey <research@ijs.co.nz>]

On Mon, 31 May 2004 22:56:58 GMT, tmoran@acm.org wrote:

>I couldn't find a simple, easy to integrate, symbolic algebra
>package, so I've posted one at http://home.comcast.net/~twmoran
>The sample program includes the Knuth 2.2.4 example:
...
>  B : Polys.Multinomials := x**2 - 2.0*x**1*y**1 + y**2;
>  ...
>  Put_Line("Product is " & Image(A*B));


I have an Ada 95 symbolic algebra program ('Tope') targetted to solve
linear quantifier elimination problems such as this:

  Inp: (Exists x)(a<x)(b<=x)(x<=c)(x<=d)
  Out: (a<c)(a<d)(b<=c)(b<=d)

Online at: http://www.ijs.co.nz/code/software.html
The Ada Yacc parser with UMASS extensions is used.

The existing REDLOG led into a breakdown in failing to simplify the
symbolic output "Exists", and better could by using an operations
research algorithm to compute dual polytopes thrice.

The dual polytope can be computed with the Chernikova algorithm
of Mr LeVerge of 'irisa.fr', which is a small hard-to-port C program
online here (at the Parma Polyhedra website):
   http://www.cs.unipr.it/ppl/Documentation/chernikova.c
   (Mentioned on http://www.cs.unipr.it/ppl/Credits/ )
It is curious how such a tiny 'satisfactory' C program can be at the
centre of a lack of good progress of C programmers and also really quite
hard to port to good Ada code.

The Italian research project is testing out the use of a C++ style for
the syntax interface.
At Irisa (France), the Polka project uses real Ocaml for the front end
which actually wouldn't compile for me: 
   http://www.irisa.fr/prive/bjeannet/newpolka.html

The symbols are Real-valued.

---------

I got my Fast Strings package fixed: it speeded up by a staggeringly
large factor of 5.3 times when I replaced
    Str : String:
    ...
    Str := ...
with a call to C memmove() routine. It far from obvious that a CPU
cache size explanation would explain the (somewhat tricky-to-reproduce)
problem with performance.
Custom string package replacing Ada.Strings.Unbounded might be better if
avoiding the ":=" (some prob not required by Ada 95's RM7.6 rule saying
that no program can implement ":=" while seeing both variables for
good reasons that CLA might never get).



Craig Carey