Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

Re: Symbolic Computation



At 12:36 PM 5/17/99 -0400, Bob Sciamanda wrote:
I am a big user of MathCad and am mystified by its powers of symbolic
computation - a subset of Maple. (Other software packages also have
this capability.)

How do they do this? I would like to have at least an overview
understanding of how this is done. Is it some clever implementation of
a lookup table algorithm? Can anyone elaborate or point to a URL?

At 01:39 PM 5/17/99 -0500, Ludwik Kowalski wrote:
My naive guess (a model) is that the process is similar to OCR
(optical character recognition).

I've written symbolic analysis code and OCR code, and I see no great
similarity between them. OCR is much harder, partly because the problem is
much less well specified.

Anyway, here are some Gedankenexperimente that may demystify some if it for
you. Imagine writing a simple symbolic-analysis system of your own....

1) Start with just polynomials of a single variable.
P(x) = sum A sub n X^n
The first step is to choose a representation. The simplest thing is to
keep an array of the coefficients A sub n, indexed by n. To do a
professional job, you need to consider the possibility that n is very
large. Automatic array allocation is easy in Perl and C++; in other
languages you may have to do fuss with your own array management.

Given this representation, it is no great trick to do
-- addition of two polynomials
-- subtraction "" ""
-- multplication "" ""
-- long division "" ""
-- differentiation
-- integration

2) For a more advanced version, consider more general expressions such as
F(X) = X^3 + cos(5*X/(2-X))
i.e. addition, subtraction, multiplication, division, exponentiation,
nested parentheses, and function calls.

The first step again is to choose a representation. I recommend Polish
postfix. The example expression becomes
2 X sub 5 X mul div cos X 3 pow plus

There are some very cute algorithms for parsing generic infix expressions
into Polish postfix. The code is quite tiny even if you do it by hand, and
if you don't mind smashing flies with a sledgehammer you can use Lex and
Yacc. In postfix form it is no great trick to do all sorts of formal
operations. For instance, to subtract 17 from the previous expression you
just write
2 X sub 5 X mul div cos X 3 pow plus 17 sub

Differentiation is no great strain either, since we know the derivatives of
all the elementary operations.

The hard parts include
a) simplification, i.e. knowing that 5 * X / 5 can be simplified to just
X, and
b) integration.

Even without simplification and/or integration, there's lots of useful
stuff you can do with the system just described. For instance, once I
wrote a general-purpose multi-dimensional search routine that needed all
the directional deriviatives of the function being searched. The users
(Ivy-League physics grad students) seemed to have a really hard time doing
the derivatives by hand and typing them into my program, and then they
would gripe at me when the search failed. So it was really much easier to
do the differentiation automatically as described above.

Integration is *not* done the way integration is taught in typical
textbooks (i.e. recognize this pattern, perform this tricky substitution,
hope and pray). Instead, integration is done more-or-less the way people
*really* do it: namely write the integral on one side, write all the known
functions on the other side, differentiate both sides, and see what matches
up. This has the nice property that in bounded time it will either tell
you the antiderivative, or tell you it can't be done in terms of known
functions.

Note that if Erf is among the known functions, Gaussians are integrable,
and not otherwise.