[Axiom-developer] Re: Rule-based integration

[TimDaly]

On Jul 12, 3:32 pm, Richard Fateman <address@hidden> wrote:
> There are issues in pattern matching that are fairly subtle, and may
> not be obvious to the casual reader (or programmer).
>
> For example, you may have a rule that works to integrate
>
> exp(n*x) * x^m  wrt x.
> Mathematica 7 gives
>
> -E^(-n x) (E^x)^n x^(1 + m) (-n x)^(-1 - m) Gamma[1 + m, -n x]
>
> now if we substitute n->0, we should get something like
>
> If m=-1 then log(x)  else x^(m+1)/(m+1)
>
> but
> mathematica gives
> -0^(-1 - m) x^(1 + m) Gamma[1 + m, 0]
> and actually, for integral of x^m, it still does not include the log
> possibilities.
>
> But back to patterns.  If we try to classify the pattern for
> exp(n*x)*x^m,  we might say that this rule applies to
> products of exponentials and powers.
>
> but perhaps it is also a rule that applies to
> products of exponentials and symbols like x,  where of course x^1 is a
> power, but simplified to x.
>
> or maybe it is a rule that applies just to exponentials, since x^0 is a
> power, but but simplified to 1, after which the "product" disappears
> entirely.
>
> This is all to provide a specific example of a kind of rule that may
> crop up fairly often..
>
> Consider a rule that for particular functions f,g,h   like (say) exp,
> log, sin, power, ...erf, gamma, ... says how to integrate f^n*g^m*h^k ..
>
> given a particular expression to integrate, it might be missing some
> power, or even missing some function entirely.  This makes finding the
> right rules more difficult.
>
> The trick in assembling large numbers of rules is to make sure you don't
> have to run them all, but only that (one hopes) very small subset that
> is likely or even possible to match.
>
> I think it is great that Rubi may be adapted for free software systems.
>
> RJF

There has been some initial discussions between myself, Albert Rich,
and David Parnas about how to think about this problem.

My current thinking involves a tree-structuring of the rule patterns
where each node in the tree represents one or more pattern
tables and each edge is a function (e.g. division operation, etc).
Walking the input expression walks the tree to find applicable
patterns.
Because a pattern table can be reached from many different paths the
"tree" is actually a graph. Each table specifies an input pattern and
an output pattern and the output pattern points to another node.

So far all I have are "paper studies" using index cards as the tables.

I looked at constructing a Rete pattern match (Charles Forgy, OPS5)
but there are only a small number of rules that can be applied so
there is not much depth. I also don't know quite how to factor the
"meta rules" into a Rete network.

There are a lot of interesting questions that arise, such as the
issue of branch cuts and choice of trigonometric identities that
get applied (which can easily lead to cycles).

The problem also seems ideal for a parallel decomposition because
I can see multiple patterns applied in any situation (e.g. making
various choices for integration by parts).

Special functions are also a question... is it better to leave the
result as sin(x)/x or to choose sinc(x). The first is easier to
combine with other results but the second is shorter to represent.
Albert measures the number of leaf nodes as a measure of simplicity.
Unfortunately, "simplicity" is in the eye of the beholder. Axiom
generally deals with the simplicity issue by making different domains.
Thus in the domain of Polynomials with fractional coefficients the
"simple" form is:

(1/3)*x^2+7

but in the domain of fractions of polynomials with integer
coefficients
we see the same answer as:

(x^2+21)/3

The "simple" form depends on the domain. This raises interesting
questions for some intermediate domains to express patterns rather
than using the general "Expression(Integer)" domain. The same
"pattern table" advocated by Parnas might generate multiple results
depending on the target domain. Axiom is ideal for this but it
requires a lot of thought.