[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Some other symbolic math programs...

On Mon, 28 Feb 2000, Nils Barth spoketh:
> Thus spake George:
> > I guess gluing together more packages sounds like the best strategy for
> > dr genius anyway.  We get a LOT of functionality with a common interface that
> > way.  Most of these packages have different and usually advanced interfaces
> > (or are just programming libraries).  Which of course sucks for a program
> > like dr genius which should be for people that just want to sit down and do
> > some math without having to learn stuff.  However the functionality is there
> > and rewriting it would be dumb.  (hence me using CLN even though I'm not too
> > crazy about having to use a C++ compiler)
> 
> yeah -- for example, numerical linear algebra problems can be solved using
> LINPACK, EISPACK, and LAPACK. This are available at
> http://www.netlib.org/
> (they have quite a bit of stuff there)
> Only worries are: 
> (1) these were designed for supercomputers, but I think they
> should work fine on workstations.
> (2) these are in fortran (though they've been convert to C, I think)
> (3) licence issues -- I think these are basically free, but there may
>     be some GPL incompatibilities (I hear LINPACK and EISPACK are
>     public domain, but LAPACK might have some LaTeX-style license
>     problems)
> (4) They are BIG! Maybe just some subsets of these or adaptations?
> 
> However, they offer time-tested solutions to QR decompositions and
> singular value decompositions etc. AFAIK, these are -the- standard
> numerical matrix packages.

I don't know where DrGenius is heading to but let me comment on the use of
such packages.  I have been considering this issue for incorporating one
of them into the GiNaC framework and came to the conclusion that it would
be better not to do so.  The problem is: All those packages are designed
for *numerical* linear algebra and almost all of them for some fixed
precision (mostly double precision).  There, the need for stabilization
and conditioning arises.  Also, they don't only want to optimize the
amount of cycles but also the memory usage.  If you want *arbitrary*
precision you are having a problem with those packages anyhow.  I would
rather rewrite some routines and not spend the time on things like
Strassen multiplication for matrices and parallelization.  I assume you
don't want to deal with 1000x1000 matrices in DrGenius anyhow, do you?

Then, there is the issue with symbolic capabilities.  As soon as you add
those you can throw away most of the algorithms from numerical linear
algebra anyhow.  For instance, let us consider the issue of determinants.

* If you implement it using the permutation group, you have about
  factorial(n) multiplications.
* If you implement it using recursive Laplace expansion you end up with
  about Gamma(n+1,1) multiplications where Gamma(n+1,1) is the incomplete 
  Gamma function Gamma(a,z) = int_z^\infty exp^{-t}t^{a-1}, IIRC.  So you
  aren't much better.
* You might be clever, by storing minors somewhere.  Then you end up with 
  only about n*2^(n-1) multiplications.
* If you do Gauss elimination you have only n^3 steps!
* Do fraction free elimiation, and you also control the size of
  intermediary steps.
* Add a scheme for Sasaki-Murao multiplication and you will never have to
  divide something!  This sounds perfect, doesn't it?

Now you plug in a dense symbolic matrix like [[a,b,c],[d,e,f],[h,i,j]].
The result is of course a*e*j-a*f*i+b*f*h-d*b*j+c*d*i-f*i*c.  So there are
n! operations anyhow and you are back with the complexity of the dumbest
approach. Amazingly it turns out that for dense matrices with large
multivariate polynomials method 3 (Laplace expansion w/ storing minors) is
the fastest one.  This should make the difference between symbolic and
numeric calculations clear and obsolete those specialized packages, even
for most kinds of selfmade big integer- or arbitrary precision-schemes.
Those packages become rather worthless once you leave fixed precision.

If you are series about such things I suggest to have a look at
<http://oonumerics.org/>.  If you are serious about attaching some
symbolic stuff I suggest to check out ``Algorithms for Computer Algebra''
by Geddes, Czapor and Labahn from your library and have a look into it.
This wonderful book clarifies a lot.

Regards
     -rbk.
-- 
Richard Kreckel
<Richard.Kreckel@Uni-Mainz.DE>
<http://wwwthep.physik.uni-mainz.de/~kreckel/>