Extended interation

[Waldek Hebisch]

I have now commited new extended integration code. The new code
is still quite incomplete and this is likely to lead to some
regressions. However, the old code was even more incomplete
so that on average we should see improvement. As one example
in fixed.input we have:

integrate(((-x-1)*log((x^2+x))^2+2*log(x))/(x+1),x)

That used to fail, but now produces correct result. Let
me add that old code on hitting incompltenss would silently
claim that function is not integrable. For elementary functions
new code will signal error for unimplemented parts.

Let me add that unimplemented parts are about general algebraic
integrands (completely unhandled by old code), bounds in RDE
(old code makes assumption which may be invalid, new code
tries to solve parametric logarithmic derivative problem for
which no good complete algoritm is known) and RDE in general
algebraic case (again completely unhandled by old code).

In several cases old code took a shortcut (usually via
substitutuin), which may lower execution time or handle
some cases that would be otherwise unhandled. Currently
new code takes almost no shortcuts. One reason is that
I tried to keep code simple (without extra cases). Also,
it is not clear how effective are the shotcuts (I suspect
that they help only a little). If there are performance
regressions I will add faster paths for important special
cases, but I prefer to do this only after having enough
evidence.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

[Ralf Hemmecke]

Hi Waldek,

> integrate(((-x-1)*log((x^2+x))^2+2*log(x))/(x+1),x)

That all sounds great. Do you already have links to articles or maybe an
own article that describe your improvements? It would really be great to
be able to match the description of the paper with the corresponding
places in the code.

Ralf

[Waldek Hebisch]

I am affraid that what I did is considered unpublishable. More
precisely, extended integration is like normal integration,
except that we do not need to look for logaritms (which
makes things easier) and we need to handle several functions
simultaneously (which complicated code a lot but is trivial
from conceptual point of view). Transcendetal case uses
methods mostly form Bronstein "Symbolic Integration" (more so
than old Bronstein code). Base algebraic case uses substitution
to avoid poles, Hermite integration and property that after
hermite intgration without poles logarithmic parts must
exactly cancel. Algebraic extension over exp or log works
only for roots and uses fact that integrating polynomial
part is equivalent to solving Risch differential equation (RDE).
RDE in algebraic case uses reduction to system of differential
equations -- this is essentially Bronstein code, but I had
to generalize it to several functions and fix a few bugs.
For logaritmic derivative problem I use method described
in PhD thesis by Raab (he may be first to describe it but
I am sure that idea is not new).

So in current text related math is considered trivial (trivial
modification of integration algorithm). My improvement is
that instead of saying that this is trivial I actually
implemented it. I was surprised to note how incomplete
the old code was. But explanation may be as follows:
this is sizable piece of code which is considered
conceptually trivial, so it is hard to publish a paper
about it. So Bronstein had little or no incentive to
complete it... I guess my best chance to publish something
about this would be article with title "Current publishing
model considered harmful" expalining pitfals in "trivial"
parts.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

[Ralf Hemmecke]

> I guess my best chance to publish something about this would be
> article with title "Current publishing model considered harmful"
> expalining pitfals in "trivial" parts.

Very right. This whole journal and peer reviewing system is broken.
I more and more like the idea of simply publishing on a website no
matter how trivial or wrong something is. The reviewing processs should
start afterwards. Good and/or important articles will be cited no matter
how "trivial" they are.

In a sense that supports Tim's constant arguing of "put the
documentation into the code". And also for your "trivial" things I would
consider that important. What you find trivial might not be so trivial
to somebody else. It's always better to read about the intention of the
code in text than figuring that out by reading the code.

So please put your "paper" into the repository.

Ralf

[Eddy Xiao]

Hi, I'm trying you new integration code, and

integrate(x^(1/3)/(3*x+1)^(1/3), x)
 
   >> Error detected within library code:
   impossible

what does this "impossible" mean? Is it a bug?

BTW: Is sourceforge.net/p/fricas/bugs/ the proper place to report bug?

Thanks.

xyy


在 2014年11月27日星期四UTC+8下午7时35分21秒，Waldek Hebisch写道：

[Ralf Hemmecke]

> integrate(x^(1/3)/(3*x+1)^(1/3), x)

Would you be satisfied with what

integrate((x/(3*x+1))^(1/3), x)

returns?

> BTW: Is sourceforge.net/p/fricas/bugs/ the proper place to report bug?

Yes. That's what http://fricas.sourceforge.net/ says.

Ralf

[Waldek Hebisch]

Eddy Xiao wrote:
>
> Hi, I'm trying you new integration code, and
>
> integrate(x^(1/3)/(3*x+1)^(1/3), x)

> =20

> >> Error detected within library code:
> impossible
>
> what does this "impossible" mean? Is it a bug?

Yes, it is a bug. "impossible" mean that some condition happened
that author of the code (probably me) thought should never
happen. It may be mistake in a proof or some other place is
passing wrong values.

>
> BTW: Is sourceforge.net/p/fricas/bugs/ the proper place to report bug?

Yes.

BTW: The bug is present from some time, at least from release 1.2.3.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

[xyy]

On 12/10/2014 09:17 AM, Ralf Hemmecke wrote:
>> integrate(x^(1/3)/(3*x+1)^(1/3), x)
> Would you be satisfied with what
>
> integrate((x/(3*x+1))^(1/3), x)
>
> returns?

Wow, I shall be satisfied with that. It's even better than Mathematica
(which returns a Hypergeometric function).
But a flaw is that the result is real only for x<-1/3. Although a simple
modification can make it valid for both x<-1/3 and x>0.
(Also, the merge of exponent here happen to be valid (in a point of view
of complex arithmetic)...)

>
>> BTW: Is sourceforge.net/p/fricas/bugs/ the proper place to report bug?
> Yes. That's what http://fricas.sourceforge.net/ says.
>
> Ralf
>

Seems the mailing list is much more active than there :-)

xyy

[XYY]

Ah, so next time I might report bugs there (if any) instead of bother the whole mailing list.

Actually I also tried Axiom May 2012 version, seems that it triggers an infinity loop. But you are different projects...

xyy

--
You received this message because you are subscribed to a topic in the Google Groups "FriCAS - computer algebra system" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/fricas-devel/TzTI6wp-CG0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to fricas-devel...@googlegroups.com.
To post to this group, send email to fricas...@googlegroups.com.
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.

[Ralf Hemmecke]

>>> BTW: Is sourceforge.net/p/fricas/bugs/ the proper place to report bug?
>> Yes. That's what http://fricas.sourceforge.net/ says.

> Seems the mailing list is much more active than there :-)

Well, the bug tracker is not much in use. Usually people first report on
the mailing list. Either it turns out not to be a bug or it gets fixed
quickly. Only the harder bugs tend to end up in the tracker (if people
care at all to report).

Ralf

[Ralf Hemmecke]

> Actually I also tried Axiom May 2012 version, seems that it triggers an
> infinity loop. But you are different projects...

http://fricas.sourceforge.net/history.html

Ralf

[Waldek Hebisch]

xyy wrote:
>
> Actually I also tried Axiom May 2012 version, seems that it triggers an
> infinity loop. But you are different projects...
>
> xyy
>

Axiom for this integral probably uses old code (coming from
NAG version). This part is extremaly slow, and if you are
patient enough (it may take a month or more) should either
run out of memory or finally signal different error. AFAICS
original code is exteremaly unlikely to produce result.
Namely it uses constructs which are not handled at later
stages. Unless there is some magic cancelation
eventually the code will signal error. There is no reson
to expect cancelation and in fact under assumptions that
this code is making (but which are violated in your
example) there should be no cancellation. So basically
old code for this case has no chance of working, but
the problem is masked by sloweness: the code is so slow
(and need _huge_ amount of memory) that I can not imagine
that anybody tried long enough to see error. The
old code is removed from FriCAS, instead FriCAS tries
to handle this case in different way. Unfortunately
I made a mistake in my reasoning and some case are
not handled by new code. FriCAS recognises the problematic
case, but istead of claiming that it is impossible we
need to handle it.

--
Waldek Hebisch
heb...@math.uni.wroc.pl

[xyy]

Thanks for detailed explanation! Indeed, Axiom is still running after 60
hours (used 0.5 GB memory).