How to help sympy integrate sqrt(a**2/(a**2-x**2))

[Ondřej Čertík]

Hi,

Currently SymPy can't do this integral:

integrate(sqrt(a**2/(a**2-x**2)), x)

and I reported it here:

https://code.google.com/p/sympy/issues/detail?id=4010

It seems SymPy cannot even do this integral:

integrate(sqrt(1/(1-x**2)), x)

the solution of which is asin(x), at least for real "x".

Any ideas how to "help" sympy do this kind of integral?

Ondrej

[Aaron Meurer]

The problem is that sqrt(1/x) is not the same as 1/sqrt(x). If you are
working in a situation where it is, you can do integrate(1/sqrt(1 -
x**2), x) and this works.

These algebraic integrals are tricky. They only work with the current
heurisch algorithm "by accident", because they happen to come out to
the right form for it to recognize the antiderivative. But since
algebraic functions have multiple equivalent forms that look
completely different to the algorithm (e.g., sqrt(x)/x == 1/sqrt(x)),
and SymPy's default canonicalization is only based on combining
powers, this doesn't happen in general.

The *right* solution is to implement the algebraic Risch algorithm.
This is a lot of work, though Katja's GSoC project will hopefully
implement some of the needed algorithms in the polys. The workaround
is to modify the heuristics. In heurisch, there is a part that does
some pattern matching and tries to add terms here
https://github.com/sympy/sympy/blob/master/sympy/integrals/heurisch.py#L278.
I suppose we could add a pattern for sqrt(a**2/(a**2 - x**2)) (or
something more general than that). You have to be careful with this,
though, because the more terms you add to the candidate integral, the
more powerful the algorithm becomes, but also, the slower it becomes.

It might also be possible to modify the Meijer G algorithm to work
with this. I don't know enough about how to do this. I think it means
finding and adding some entry to the lookup table (which is currently
http://docs.sympy.org/dev/modules/integrals/g-functions.html#implemented-g-function-formulae).
Tom and/or Raoul can comment more on this approach. Modifying Meijer G
would be preferable to modifying heurisch if it can work, because the
algorithm is not a slow, and it will also automatically make some
definite integrals work.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> For more options, visit https://groups.google.com/groups/opt_out.

[Aaron Meurer]

Another idea would be to implement a basic table lookup for such
integrals (https://code.google.com/p/sympy/issues/detail?id=1393).
This would be the least powerful, as it would only work for
expressions exactly of the form we put in the table, but it would be
fast, and wouldn't require figuring out how to make thing work with
the heurisch or Meijer G algorithms.

Aaron Meurer

[Ondřej Čertík]

On Sun, Sep 8, 2013 at 5:48 PM, Aaron Meurer <asme...@gmail.com> wrote:
> Another idea would be to implement a basic table lookup for such
> integrals (https://code.google.com/p/sympy/issues/detail?id=1393).
> This would be the least powerful, as it would only work for
> expressions exactly of the form we put in the table, but it would be
> fast, and wouldn't require figuring out how to make thing work with
> the heurisch or Meijer G algorithms.

Can the Meijer G be used to integrate any function, or is the the most general
algorithm still the Risch one? I read this:

http://docs.sympy.org/dev/modules/integrals/g-functions.html

and it shows how to do the (0, oo) integrals, but not the general
antiderivatives.
I found some formulas how to integrate G functions, but I don't know if it is
implemented in sympy. I.e. are there functions that cannot be expressed
using the G function?

Ondrej

[Aaron Meurer]

On Sun, Sep 8, 2013 at 9:17 PM, Ondřej Čertík <ondrej...@gmail.com> wrote:
> On Sun, Sep 8, 2013 at 5:48 PM, Aaron Meurer <asme...@gmail.com> wrote:
>> Another idea would be to implement a basic table lookup for such
>> integrals (https://code.google.com/p/sympy/issues/detail?id=1393).
>> This would be the least powerful, as it would only work for
>> expressions exactly of the form we put in the table, but it would be
>> fast, and wouldn't require figuring out how to make thing work with
>> the heurisch or Meijer G algorithms.
>
> Can the Meijer G be used to integrate any function, or is the the most general
> algorithm still the Risch one? I read this:

It depends on what you mean by "general". In my view, the two
algorithms handle different classes of integrals with different
advantages, and therefore they will both always be needed.

Here's a list of facts for each algorithm

# Meijer G

Advantages:

- Can handle a large class of special functions.
- Works particularly well with definite integrals (but it also can
compute indefinite integrals).
- Can compute convergence conditions for definite integrals
- Can split indefinite integrals into conditions as well (for
instance, integrate(1/sqrt(x**2 - 1), meijerg=True)).

Disadvantages:
- Is only a heuristic, so while it is smarter than a basic table
lookup, it still requires some level of pattern matching.
- As with any such algorithm, it can be highly dependent on the form
of the expression.
- As such, won't recognize particularly complicated integrands.
- The indefinite integrator is not particularly strong, at least
compared to the definite one.

# Risch

Advantages:

- Is a complete algorithm, so if an expression fits in the class it
recognizes (and the cases are all implemented), it will compute the
answer.
- Works with arbitrarily complicated expressions.
- Can prove that elementary integrals do not exist.
- Because the algorithm is complete, rather than relying on a pattern
matching heuristic, it doesn't rely on the form of the input
expression. It may end up changing the format of the output, but if an
answer exists, it will find one no matter what the input looks like
(unless the input is in some form that it hasn't been programmed to
recognize, e.g., currently Risch in SymPy doesn't handle hyperbolic
trig functions even though it could, because they are just
exponentials).

Disadvantages:

- Only works with a relatively small class of expressions (elementary
functions, plus there are some extensions for a few special
functions).
- Adding more cases requires quite a bit of work.
- Doesn't work for definite integrals directly.

In general, Meijer G works well for a very large class of functions,
but not very complicated combinations of them, whereas Risch works
well for a small class of functions, but they can be arbitrarily
complex. That's why on the outset, Meijer G will seem to be more
powerful, because if you plug in every integral in an integration
table, it will catch more of them. But if you test the integrator in a
slightly different way, namely, by taking some random expression,
differentiating it, and passing it in, you'll have better luck with
the Risch algorithm (assuming the original expression was elementary).

I didn't mention heurisch, but it falls somewhere in between. It still
uses pattern matching and can be highly sensitive to the form of the
input, but it's based on some of the theory of the Risch algorithm, so
it can work with reasonably complicated expressions, assuming the
answer looks like what it expects it to. It doesn't work so well with
special functions because it works best with functions whose
derivatives can be expressed in terms of itself.

>
> http://docs.sympy.org/dev/modules/integrals/g-functions.html
>
> and it shows how to do the (0, oo) integrals, but not the general
> antiderivatives.

Yes, it can do antiderivatives, and as I showed in that example above,
it can handle at least some algebraic functions.

By the way, the best resource to find some formula, unless you have
one of those table books, is the Wolfram functions site. It's a little
hard to navigate, though (I wonder if you have a copy of Mathematica
if there is an easier way to do a table lookup within the software).

> I found some formulas how to integrate G functions, but I don't know if it is
> implemented in sympy. I.e. are there functions that cannot be expressed
> using the G function?

Tom or Raoul would have to give a more specific answer, but I believe
that there are functions that can't be expressed in terms of the
Meijer G-function.

Aaron Meurer

[someone]

Hi,

> > On Sun, Sep 8, 2013 at 5:48 PM, Aaron Meurer <asme...@gmail.com>
> > wrote:
> >> Another idea would be to implement a basic table lookup for such
> >> integrals (https://code.google.com/p/sympy/issues/detail?id=1393).
> >> This would be the least powerful, as it would only work for
> >> expressions exactly of the form we put in the table, but it would
> >> be fast, and wouldn't require figuring out how to make thing work
> >> with the heurisch or Meijer G algorithms.
> >
> > Can the Meijer G be used to integrate any function, or is the the
> > most general algorithm still the Risch one? I read this:
>
> It depends on what you mean by "general". In my view, the two
> algorithms handle different classes of integrals with different
> advantages, and therefore they will both always be needed.

Yep, this is also my current understanding.

This seems more or less accurate.

Maybe we should put such list into the documentation?

There is a recent extension to Risch to work with much more
of the simpler special functions, see the work of Clemens Raab,
for example "Generalization of Risch’sSpecial Functions".
They can also do definite integration now.

Yes, there are a few although most common special function fit
into the MeijerG framework. One of the simpler examples is AFAIR
the Hermite polynomials where the G parameter get singular.
(I'd have to recheck the formulae to give the full example
if desired.)


-- Raoul