Re: Steps towards writing a computer algebra system /bad ideas from books

From: Richard Fateman (fateman_at_cs.berkeley.edu)
Date: 01/19/05 

Date: Wed, 19 Jan 2005 16:51:22 GMT

parisse@domain.invalid wrote:

> Richard J. Fateman wrote:
>
>> These books would definitely not tell you how to write
>> a computer algebra system.
>>
>
> I would rather say that they describe some mathematical
> algorithms. Then you must add data structures to hold symbolics,
> implement long integers and polynomials, a parser and write a (G)UI.

It is not so simple as choosing data structures, sometimes.

The mathematical algorithms
that are described are not necessarily the right ones for practical
computation. To be more specific, the algorithms, and especially shortcuts and
heuristics that are really used in a system may not even be described!
They may not even be known to the authors these books, who tend to be
theorists and not system builders.

The encyclopedic Modern Computer Algebra
book (785 pages!), in its analysis of polynomial GCD analyzes some (very) bad
polynomial remainder sequence (PRS) methods, and then some modular methods,
  that are good only for very large and very dense problems, ignoring the
c. 1968 improvements developed by Collins and Brown. The rather practical Heuristic
GCD used by Maple is described only in an exercise, and the subresultant
PRS, which has been known since the early 1970s to be the best PRS,
is left out, in favor of several inferior ones.

The very important Hensel-based or sparse modular GCD algorithms, implemented
in Macsyma in the early 1970s and now used in other systems as default,
are not, as far as I can tell,
  mentioned in the 60 page chapter on resultant and gcd computation.

Thus it is not a matter of picking the right algorithm out of this
book. The right algorithm isn't even in the book!

>
<...snip>
>>
>
> I agree. For example, an algorithm on symbolic matrices
> that is faster for e.g. N>1000, is likely not to be implemented...

yes! This too is true.

Relevant Pages

  • Re: Mathematical Algorithms
    ... There are lots of books on algorithms for computer algebra systems. ... expressions probabilistic modular methods. ...
    (sci.math)
  • Re: Gama Function
    ... You do not give a general formula for arbitrary rational arguments 0 < ... compare with the algorithms currently used in computer algebra ...
    (sci.math.symbolic)
  • Re: Symbolic programming for dummies
    ... but written in a language like C or C++ or other. ... And is there like a book which teaches symbolic math programming (I ... Computer Algebra and Symbolic Computation: Elementary Algorithms ISBN ...
    (sci.math.symbolic)
  • Re: Steps towards writing a computer algebra system
    ... These books would definitely not tell you how to write ... but a careful reading ... > Computer Algebra, Systems and Algorithms for Algebraic ...
    (sci.math.symbolic)
  • Re: Symbolic factorization algorithm
    ... there are algorithms for polynomial factoring. ... >> in books on the subject of computer algebra. ... Handbook of Computer Algebra, JOHANNES GRABMEIER, ERICH KALTOFEN & ...
    (sci.math.symbolic)
Quantcast