Ann: symbolic multinomial algebra

Ann: symbolic multinomial algebra

[tmoran]

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:
  type Vars is (x,y);
  function Image(Var : Vars) return String is ...
  package Polys is new Multinom(Vars, Image);
  use Polys;
  A : Polys.Multinomials
        := X**4 + 2.0*x**3*y**1 + 3.0*x**2*y**2 + 4.0*x**1*y**3 + 5.0*y**4;
  B : Polys.Multinomials := x**2 - 2.0*x**1*y**1 + y**2;
  ...
  Put_Line("Product is " & Image(A*B));

Re: Ann: symbolic multinomial algebra

[tmoran]

It's been pointed out to me that package Sorts was missing from
http://home.comcast.net/~twmoran/multinom.zip
That's now corrected.  Sorry.

Re: Ann: symbolic multinomial algebra

[Craig Carey]

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

Re: Ann: symbolic multinomial algebra

[Craig Carey]

On Thu, 03 Jun 2004 10:53:18 +1200, Craig Carey wrote:
...
Correction: that software URL I gave ought to have ended in ".htm", and
not in ".html".

...
>   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.

Whoops: that's disputable and vague over what 'progress' for dual
polytope projects including: Cdd, Polka, Parma,
 http://www.cs.umd.edu/projects/omega/ ? [integers QE], Polylib, etc.
Cdd duals: http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html

My 'hard to port' seems a bit incorrect and it was about cutting 2
C arrays to leave 4 Ada matrices.


Craig Carey