[BUG] another case of falsely claim an integral is not integrable

[Qian Yun]

This bug is more subtle than the other "falsely claim unintegrable" bug.

Because the integral is not reproducible in a fresh session, but after
some other computation.

A minimal reproducible example I found is:

====
integrate(0 - sin(1/sin(x))*cos(x)*cos(cos(1/sin(x)))/sin(x)^2, x)
integrate((x^2*sin(x)*cos(cos(x))/sin(cos(x))^2 +
2*x/sin(cos(x)))*sin(x^2/sin(cos(x))) + 0, x)

g0 := tan(sin((x*tan(x) + x)/2));
f := D(g0, x);
g := integrate(f,x)
====


If you integrate 'f' in a fresh session, you can get correct result.
But after the previous 2 integrals, it returns as unintegrable.

Tracing shows the computation diverge at "extendedEuclidean" in
"normalHermiteIntegrate" of TranscendentalHermiteIntegration in
intrf.spad.

[Qian Yun]

> Tracing shows the computation diverge at "extendedEuclidean" in
> "normalHermiteIntegrate" of TranscendentalHermiteIntegration in
> intrf.spad.

The reason that "extendedEuclidean" gives wrong result is that
something wrong happened earlier: there are expressions with
the same appearance but have different kernel underneath.

The creation of different kernels happens at "trigs2explogs"
in "integrate" in integrat.spad.

The definition of "trigs2explogs" seems alright, still it's
unknown why the same input may produce different kernels.

If we replace
gg := eval(gg0, tgg0, tgg1)
in integrat.spad with
gg := trigs2explogs(gg0, [])
then this bug disappears. But I'm still not clear about the
root cause of this bug.

[oldk1331]

Almost sure it is bug when adding new kernel in cache, in function "enterInCache".

[Waldek Hebisch]

On Sat, Dec 05, 2020 at 09:06:22PM +0800, oldk1331 wrote:
> Almost sure it is bug when adding new kernel in cache, in function
> "enterInCache".

ATM our handling of kernel cache is unsound. Basicaly, kernel
cache assumes order and in fact there are no consistent order
on kernels. Many problems would go away if we would switch
to linear search for kernels (awoiding use of order). But
that would slow down unormously routines making heavy
use of kernels (mainly series expansion and limits). And
some problem would remains.

Currently, IMO correct direction is to limit creation of
new kernel and better detect cases when we already created
needed kernel. This in necessary to avoid other bugs
and with limiting creation of kernels using linear
search will be less problematic.

One recuring problem is that expression routines try to
be smart and perform various simplifications. In integrator
we need full control of kernels and _any_ kernel trasformation
without explicit request from integrator is a bug. In
cases where integrator depended on some behind the scene
kernel manipulations in other routines we need to make
sure that integrator still have sufficient control. This
may require creating new versions of auxiliary routines.
Let me add that large part of 'integrat.spad' is a quick
hack to mitigate some bad effects of transformations in
other routines. This should be replaced by new routine...

Have you tried 'subst' instead of 'eval'? 'subst' is dumber
and hence ususaly safer than 'eval'.

--
Waldek Hebisch

[Qian Yun]

On 12/5/20 11:26 PM, Waldek Hebisch wrote:
> On Sat, Dec 05, 2020 at 09:06:22PM +0800, oldk1331 wrote:
>> Almost sure it is bug when adding new kernel in cache, in function
>> "enterInCache".
>
> ATM our handling of kernel cache is unsound. Basicaly, kernel
> cache assumes order and in fact there are no consistent order
> on kernels.

Can you share more details about this?

Still, it shocks me a little that we trade correctness for speed...

> Currently, IMO correct direction is to limit creation of
> new kernel and better detect cases when we already created
> needed kernel. This in necessary to avoid other bugs
> and with limiting creation of kernels using linear
> search will be less problematic.

I agree. "trigs2explogs" would be a good place to start
limiting creation of kernels.

Also, does that mean we will move to linear search in
the future?

>> On Fri, Dec 4, 2020, 6:11 PM Qian Yun <oldk...@gmail.com> wrote:
>>
>>>
>>> If we replace
>>> gg := eval(gg0, tgg0, tgg1)
>>> in integrat.spad with
>>> gg := trigs2explogs(gg0, [])
>>> then this bug disappears. But I'm still not clear about the
>>> root cause of this bug.
>
> Have you tried 'subst' instead of 'eval'? 'subst' is dumber
> and hence ususaly safer than 'eval'.
>

I tried using "subst" instead of "eval", doesn't solve this bug.

[Ralf Hemmecke]

> On 12/5/20 11:26 PM, Waldek Hebisch wrote:
>> On Sat, Dec 05, 2020 at 09:06:22PM +0800, oldk1331 wrote:
>>> Almost sure it is bug when adding new kernel in cache, in function
>>> "enterInCache".
>>
>> ATM our handling of kernel cache is unsound.  Basicaly, kernel
>> cache assumes order and in fact there are no consistent order
>> on kernels.

Why does Kernel need an order at all?

Wouldn't it be an option to do kernel caching via XHashTable?

No, I have no deep insight. It's just a thought.

Ralf

[Bill Page]

On Sun, Dec 6, 2020 at 4:59 AM Ralf Hemmecke <ra...@hemmecke.org> wrote:
> >> ...

> >> ATM our handling of kernel cache is unsound. Basicaly, kernel
> >> cache assumes order and in fact there are no consistent order
> >> on kernels.
>
> Why does Kernel need an order at all?
>

Ordering for kernels is important from the point of view of the use of
simplification and canonical form to determine equality. Most other
computational definitions of equality require much greater effort. In
general this is undecidable but it is desirable that any method
"almost work" in as large and important a subclass of expressions as
possible.

> Wouldn't it be an option to do kernel caching via XHashTable?
>

I tried using XHashTable to replace binary search while also
maintaining an ordering a few years ago. I did not see any performance
benefit.

> No, I have no deep insight. It's just a thought.
>

This problem has a long history and how it is treated in different
computer algebra systems is one of those fundamental things that
distinguishes them. I think that what Waldek is suggesting amounts to
trying to push the problem of defining canonical forms back to where
sub-expressions are generated. This sounds like a good strategy to me
but obviously not a complete solution.

Bill.

[Qian Yun]

On 12/5/20 11:26 PM, Waldek Hebisch wrote:

> On Sat, Dec 05, 2020 at 09:06:22PM +0800, oldk1331 wrote:
>> Almost sure it is bug when adding new kernel in cache, in function
>> "enterInCache".
>
> ATM our handling of kernel cache is unsound. Basicaly, kernel
> cache assumes order and in fact there are no consistent order
> on kernels. Many problems would go away if we would switch
> to linear search for kernels (awoiding use of order). But
> that would slow down unormously routines making heavy
> use of kernels (mainly series expansion and limits). And
> some problem would remains.

In 2015 March 20, email titled "Re: Troubles with kernels",
you said:

> There is potential problem with binary search that we use.
> Linear search trough all of the cache should work fine.
> Surprisingly after fixing a few other bugs I was not able to
> produce example of failure due to wrong sort, so I keep it
> as is.

Do you have other failure examples since then?

> I expect that sooner or later problem will show up,
> then we will have to think about solution. One possibility is
> to use linear search, which is slow. Another possibility is
> to force removal of irrationalities from denominators.
> That would make representation canonical and allow
> sorting/hashing at representation level.

To record the problem we encountered this time, it boils down to

y :=
(complex(0,1)*x*exp((complex(0,2)*x)/complex(1,0))+complex(-1,0)*x)/(complex(1,1)*exp((complex(0,2)*x)/complex(1,0))+complex(1,1))

a :=
(complex(0,-1)*exp((complex(0,1)*x)/complex(1,0))^2+complex(0,-1))/(complex(2,0)*exp((complex(0,1)*x)/complex(1,0)))

b :=
(complex(-2,0)*exp((complex(0,1)*x)/complex(1,0)))/(complex(1,0)*exp((complex(0,1)*x)/complex(1,0))^2+complex(-1,0))

And smaller?(y,a) smaller?(a,b) smaller?(b,y) are all true,
causing it impossible to order kernel exp(y),exp(a),exp(b).


About possible solution: we can do better than linear search,
we should be able to classify kernels into groups, and groups
are strictly ordered. Then search and insert of kernel into
cache would be quicker.

[Waldek Hebisch]

On Sun, Dec 06, 2020 at 10:59:33AM +0100, Ralf Hemmecke wrote:
> > On 12/5/20 11:26 PM, Waldek Hebisch wrote:
> >> On Sat, Dec 05, 2020 at 09:06:22PM +0800, oldk1331 wrote:
> >>> Almost sure it is bug when adding new kernel in cache, in function
> >>> "enterInCache".
> >>

> >> ATM our handling of kernel cache is unsound.=C2=A0 Basicaly, kernel

> >> cache assumes order and in fact there are no consistent order
> >> on kernels.
>
> Why does Kernel need an order at all?
>
> Wouldn't it be an option to do kernel caching via XHashTable?

The core problem is that kernel reprezentation is noncanonical.
For kernels (and several other noncanonical domains) it is hard
to create hash function which is efficient (has many values in
image) and sound (equal values for equal objects).

--
Waldek Hebisch

[Waldek Hebisch]

On Mon, Dec 07, 2020 at 06:57:08PM +0800, Qian Yun wrote:
>
>
> On 12/5/20 11:26 PM, Waldek Hebisch wrote:
> > On Sat, Dec 05, 2020 at 09:06:22PM +0800, oldk1331 wrote:
> > > Almost sure it is bug when adding new kernel in cache, in function
> > > "enterInCache".
> >
> > ATM our handling of kernel cache is unsound. Basicaly, kernel
> > cache assumes order and in fact there are no consistent order
> > on kernels. Many problems would go away if we would switch
> > to linear search for kernels (awoiding use of order). But
> > that would slow down unormously routines making heavy
> > use of kernels (mainly series expansion and limits). And
> > some problem would remains.
>
> In 2015 March 20, email titled "Re: Troubles with kernels",
> you said:
>
> > There is potential problem with binary search that we use.
> > Linear search trough all of the cache should work fine.
> > Surprisingly after fixing a few other bugs I was not able to
> > produce example of failure due to wrong sort, so I keep it
> > as is.
>
> Do you have other failure examples since then?

IIRC Kurt Pagani gave most striking example.

> > I expect that sooner or later problem will show up,
> > then we will have to think about solution. One possibility is
> > to use linear search, which is slow. Another possibility is
> > to force removal of irrationalities from denominators.
> > That would make representation canonical and allow
> > sorting/hashing at representation level.
>
> To record the problem we encountered this time, it boils down to
>
> y := (complex(0,1)*x*exp((complex(0,2)*x)/complex(1,0))+complex(-1,0)*x)/(complex(1,1)*exp((complex(0,2)*x)/complex(1,0))+complex(1,1))
>
> a := (complex(0,-1)*exp((complex(0,1)*x)/complex(1,0))^2+complex(0,-1))/(complex(2,0)*exp((complex(0,1)*x)/complex(1,0)))
>
> b := (complex(-2,0)*exp((complex(0,1)*x)/complex(1,0)))/(complex(1,0)*exp((complex(0,1)*x)/complex(1,0))^2+complex(-1,0))
>
> And smaller?(y,a) smaller?(a,b) smaller?(b,y) are all true,
> causing it impossible to order kernel exp(y),exp(a),exp(b).

The expressions are transcendental and 'smaller?' should work
for them. OTOH inside integrator 'exp(2*%i*x)' and 'exp(%i*x)'
should not appear together, 'normalize' removes first one
and no other routine should introduce new unnormalizes
kernels. Unfortunaltely, some routines do this and
we need to replace them by correct ones.

> About possible solution: we can do better than linear search,
> we should be able to classify kernels into groups, and groups
> are strictly ordered. Then search and insert of kernel into
> cache would be quicker.

Well, I have looked at various possible schemes. ATM it
is not clear for me which one is better. Basicaly, my
current view is that integrator should internaly use
representation which is significantly different than
current Expression. In particular it should keep its
own represention of kernels _for given problem_.
Currently when integration problem after normalization
involves more than 20-30 kernels, then it is way too hard.
So probably integrator could do linear search (searches
in integrator should be relatively rare compared to
other operations). OTOH, having control over kernels
integrator could speed up searches. Important point
is that after integration problem is done integrator
would discard all info about kernels, so there would
be no problem with maintaining consistency between
successive calls.

Assuming the above is sucessful, we could than use similar
approach in other heavy users of kernels. And turn
Expression into a wrapper for user convenience. But
ATM I am at very first stage...

--
Waldek Hebisch

[Waldek Hebisch]

On Mon, Dec 07, 2020 at 02:06:22PM +0100, Waldek Hebisch wrote:
> On Mon, Dec 07, 2020 at 06:57:08PM +0800, Qian Yun wrote:
> >
> > To record the problem we encountered this time, it boils down to
> >
> > y := (complex(0,1)*x*exp((complex(0,2)*x)/complex(1,0))+complex(-1,0)*x)/(complex(1,1)*exp((complex(0,2)*x)/complex(1,0))+complex(1,1))
> >
> > a := (complex(0,-1)*exp((complex(0,1)*x)/complex(1,0))^2+complex(0,-1))/(complex(2,0)*exp((complex(0,1)*x)/complex(1,0)))
> >
> > b := (complex(-2,0)*exp((complex(0,1)*x)/complex(1,0)))/(complex(1,0)*exp((complex(0,1)*x)/complex(1,0))^2+complex(-1,0))
> >
> > And smaller?(y,a) smaller?(a,b) smaller?(b,y) are all true,
> > causing it impossible to order kernel exp(y),exp(a),exp(b).
>
> The expressions are transcendental and 'smaller?' should work
> for them. OTOH inside integrator 'exp(2*%i*x)' and 'exp(%i*x)'
> should not appear together, 'normalize' removes first one
> and no other routine should introduce new unnormalizes
> kernels. Unfortunaltely, some routines do this and
> we need to replace them by correct ones.

Oops, '%i' is algebraic. I was thinking that special
handling in Complex avoids the trouble and that one
can treat it as transcendentals, but unfortunately not.

Actually, already definiton of 'smaller?' in Fraction
is unsound...

We need some order for display purposes so probably need
to define 'smaller?' for kernels, but it must be done
in more ad-hoc way...

--
Waldek Hebisch