On Sun, Apr 19, 2009 at 10:34 AM, Carl Witty <carl.wi...@gmail.com> wrote:
>
> On Sun, Apr 19, 2009 at 7:44 AM, Maurizio <maurizio.gran...@gmail.com> wrote:
>> Carl, I took advantage of your suggestion, even though I assume I
>> can't still go through the whole process with the current gcd
>> capabilities in Pynac. But before than that, I'd like to point out
>> something strange I did notice, and maybe also Burcin can help with
>> that:
>>
>> reset()
>> P.<x,z> = QQ[]
>>
>> B = x^3 + x
>>
>> var('x, zs', ns = 1)
>> from sage.symbolic.ring import NSR
>> Bs = NSR(B)
>> Bs
>> x^3 + x
>> Bs.diff(x)
>> 0
>>
>> So, the derivative is not working. Which is the cause? It seems that
>> the "x" in Bs is not the "x" I declared, so the derivative gets 0 as a
>> result. Which is the reason?
>
> Looks like a bug to me.
>
> Burcin, any comments?
>
>> Moreover, I don't see this being the right way to do this, because
>> (for this particular problem: integration) I don't like having the
>> numerical representation of things like sqrt(5), even if the result is
>> still correct, so that
>>
>> temp = QQbar(sqrt(5)); temp
>> 2.236067977499790?
>>
>> temp^2
>> 5.000000000000000?
>
> Note that it's only the representation that's numerical; internally
> these are actually exact numbers. (For instance, if you do "temp^2 ==
> 5" and Sage prints "True", then that means that temp really is exactly
> the square root of 5.) I use a numeric representation because not all
> algebraic numbers can be represented with radicals, and solving by
> radicals is much more difficult than the symbolic-numeric algorithms I
> used in QQbar.
>
>> So, please tell me. Which should be the right way to try to approach
>> this indefinite integration problem? You can see that I'm not that
>> good in deep mathematical theory, but approaching the simplest problem
>> (that could be different from this one I'm looking at right now) is
>> fun :)
>
> Unfortunately, I think the right way is a lot of work.
>
> 1) Teach yourself enough math that you can mostly understand the
> algorithm in the paper. (Not just mechanically follow the steps, but
> understand what each step does, and have some idea why the algorithm
> as a whole works.)
>
> For some parts of this task, wikipedia and mathworld.wolfram.com will
> be useful resources (planetmath.org is also interersting); but you'll
> probably also need to read some books, etc.
>
> 2) Implement each missing sub-algorithm in Sage.
>
> 3) Implement the entire algorithm in Sage.
>
> This sounds glib, but it really is possible... I'm implementing
> cylindrical algebraic decomposition in Sage following this program.
> I've been working on it in my spare time for several years; I probably
> spent a couple of years on step 1, then I started step 2 a couple of
> years ago, and now I'm working on step 2 and step 3.
>
> The problem is that the Risch algorithm just is not simple.
Indeed. I finally read up on it a bit, and it involves some ideas
from algebra/differential field theory that are familiar to me because
of my background in number theory and arithmetic geometry. The basic
idea is to generalize the partial fraction decomposition algorithm as
much as possible, first to algebraic extensions of QQ(t), then to
differential and log extensions.
Wikipedia also has a few interesting remarks, e.g., that the Risch
algorithm isn't an algorithm, because it depends on being able to
check equality of general elementary functions, which is evidently an
open problem in general (so in practice you just fake it by evaluating
numerically at lots of points to decide if something is probably equal
to something else). It's also evidently not implemented anywhere,
e.g., a nice example on the Wikipedia page, is that if you let
f = (x^2 + 2*x + 1 +
(3*x+1)*sqrt(x+log(x)))/(x*sqrt(x+log(x))*(x+sqrt(x+log(x))))
then it has the antiderivative
g = 2*(sqrt(x+log(x)) + log(x+sqrt(x+log(x))))
since
sage: h = g.derivative() - f
sage: h.full_simplify()
0
However, Sage, Maple, and Mathematica, all simply give "integral(f)"
back when asked to integrate f. (I just checked this with the latest
versions.)
Fortunately, if one writes a program, using any number of heuristics,
to compute an antiderivative g, one can compute the derivative of g
and test whether it is *probably* equal to f by evaluating at lots of
random points. I wonder if some programs do some of the integration
by working numerically, getting a g with floating point coefficients
to high precision, then using LLL to recognize them as exact algebraic
numbers, then later deduce with high probability (and sometimes with
certainty) that g is correct?
Anyway, I'm personally definitely not at all scared of implementing
some heuristic variant of the Risch procedure, and I don't think other
people should be either. I've certainly encountered more complicated
"algorithms"...
>
> A good integration algorithm probably has a couple of phases -- first
> you try some heuristics, and pattern-match against a database of known
> integrals; if those fail, then you bring out the big guns and apply
> the decision procedure. If you're interested in working on
> integration, maybe you'd rather work on the first phase? That
> probably requires more computer science and less math than the second
> phase.
>
> Carl
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
