9 views

Skip to first unread message

Aug 24, 2021, 8:49:02 AM8/24/21

to fricas...@googlegroups.com

It was already discussed that there is no consisent and reasonably

computable order on kernels. Example by Kurt Pagani from February

2 2017 shows that this may lead to user-visible troubles. Recently

Qian reported that this leads to bugs during integration.

Core of the problem is that due to failure of order our kernel

machinery may consider two kernels as unequal, even though

they should be equal. Attached patch modifies KERNEL so

that it does not depend on order for kernel equality.

It still uses order to find positions in kernel cache.

With the patch all test pass but testsuite takes almost

two times longer than current version. More visible

slowdown is on formal derivatives:

f := operator 'f

D(f(x), x, 655)

currently takes 8.22 sec on my machine. After kernel patch

it was much longer (I did not wait long enough to know how

much longer).

The patch fixes problem reported by Kurt and hopefully

should fix some integration problems (of course there

are several problem with integration and most are

not coused by wrong handling of kernels).

ATM I am testing this patch, I particular I am looking

for possible troubles. This patch passed testsuite, but

earlier version failed, at least one of failures in

earlier version looks like unwarrented assumption in

algebra, so it is possible that this version also

causes trouble in some obscure cases. Of course,

I would like to avoid slowdown, but ATM is is not

clear how much can be done in kernel code.

Probably most of work on avoiding slowdown should

be outside kernel...

--

Waldek Hebisch

computable order on kernels. Example by Kurt Pagani from February

2 2017 shows that this may lead to user-visible troubles. Recently

Qian reported that this leads to bugs during integration.

Core of the problem is that due to failure of order our kernel

machinery may consider two kernels as unequal, even though

they should be equal. Attached patch modifies KERNEL so

that it does not depend on order for kernel equality.

It still uses order to find positions in kernel cache.

With the patch all test pass but testsuite takes almost

two times longer than current version. More visible

slowdown is on formal derivatives:

f := operator 'f

D(f(x), x, 655)

currently takes 8.22 sec on my machine. After kernel patch

it was much longer (I did not wait long enough to know how

much longer).

The patch fixes problem reported by Kurt and hopefully

should fix some integration problems (of course there

are several problem with integration and most are

not coused by wrong handling of kernels).

ATM I am testing this patch, I particular I am looking

for possible troubles. This patch passed testsuite, but

earlier version failed, at least one of failures in

earlier version looks like unwarrented assumption in

algebra, so it is possible that this version also

causes trouble in some obscure cases. Of course,

I would like to avoid slowdown, but ATM is is not

clear how much can be done in kernel code.

Probably most of work on avoiding slowdown should

be outside kernel...

--

Waldek Hebisch

Aug 26, 2021, 5:22:07 AM8/26/21

to fricas...@googlegroups.com

I did not give the patch a full test, but the logic in the patch

looks very reasonable to me.

About performance (50% slower?), do you think it is acceptable?

Most time spent on Kernel should be in "linearSearch".

And since Kernel doesn't have order, I wonder if it is possible to

using some kind of hashtable to store all cached kernels.

- Qian

looks very reasonable to me.

About performance (50% slower?), do you think it is acceptable?

Most time spent on Kernel should be in "linearSearch".

And since Kernel doesn't have order, I wonder if it is possible to

using some kind of hashtable to store all cached kernels.

- Qian

Aug 26, 2021, 9:08:12 AM8/26/21

to fricas...@googlegroups.com

Waldek wrote:

> It still uses order to find positions in kernel cache.

Although order is at least to some extent arbitrary, it is still
> It still uses order to find positions in kernel cache.

necessary for the ordering to be consistent during a session to

satisfy category 'Comparable'.

On Thu, Aug 26, 2021 at 5:22 AM Qian Yun <oldk...@gmail.com> wrote:

>

> Most time spent on Kernel should be in "linearSearch".

> And since Kernel doesn't have order, I wonder if it is possible to

> using some kind of hashtable to store all cached kernels.

to maintain a duplicate cache.

Aug 26, 2021, 9:43:46 AM8/26/21

to fricas...@googlegroups.com

On Thu, Aug 26, 2021 at 05:21:56PM +0800, Qian Yun wrote:

> I did not give the patch a full test, but the logic in the patch

> looks very reasonable to me.

>

> About performance (50% slower?), do you think it is acceptable?

We need to do something. As I wrote, I noticed unsoundness of
> I did not give the patch a full test, but the logic in the patch

> looks very reasonable to me.

>

> About performance (50% slower?), do you think it is acceptable?

kernel order several years ago. However, it looked like

theoretical problem, rare enough that it would get

unnoticed in practice. And we had visible problems to

fix. So other things got done and this one waited.

But other things improved. And examples by Kurt and

expecially your recent example shows that problem is

more serious than what I thought before.

Main speed loss shows in 'mapleok.input'. Profiling shows

significant slowdown in 'normalize' and in limit code.

In both cases it is desirable to rewrite code limiting use

of kernels.

There are also possiblities to somewhat limit linear

search. OTOH it is not clear if limiting search will

give visible gain: in profile main cost is aritmetic

which happens only after other things like operator

and number of arguments match.

> Most time spent on Kernel should be in "linearSearch".

> And since Kernel doesn't have order, I wonder if it is possible to

> using some kind of hashtable to store all cached kernels.

Consider "sin(1 + sqrt(2))" and "sin(-1/(1 - sqrt(2)))".

They should give the same kernel. Building hash function

from part we need hash function which produces the same

value for "1 + sqrt(2)" and "-1/(1 - sqrt(2))". Simple

way to get such function is to use homomorphizm. But

there are no homomorphizms from field into smaller field.

The best scheme that I found out is to build tower of

finite fields, and compute algebraic expressions inside

appropriate extention of "PF(p)" for some choice of "p".

But this is rather complicated scheme and there is still

trouble that during evaluation we can get 0/0 errors.

Another trouble is that we can attach arbitrary data to

operators. Currently we require equality function,

but would also need hash functions. Or (as we do now)

go back to linear search for any problematic cases.

--

Waldek Hebisch

Aug 26, 2021, 9:59:36 AM8/26/21

to fricas...@googlegroups.com

On Thu, Aug 26, 2021 at 09:07:58AM -0400, Bill Page wrote:

> Waldek wrote:

>

> > It still uses order to find positions in kernel cache.

>

> Although order is at least to some extent arbitrary, it is still

> necessary for the ordering to be consistent during a session to

> satisfy category 'Comparable'.

On kernels, once kernel is in cache order is determined by
> Waldek wrote:

>

> > It still uses order to find positions in kernel cache.

>

> Although order is at least to some extent arbitrary, it is still

> necessary for the ordering to be consistent during a session to

> satisfy category 'Comparable'.

position, so it is consistent. Beyond kernels it quickly

gets unsound. I am affraid that we either need to declare

that "Comparable" is unsound (that is useful for ordering

printouts, but not much more) or drop "Comparable" from

"Expression" and similar domains.

BTW: When kernel is not in the cache, our code uses order

to find position. But if ordering predicate gives wrong

results we still insert kernel somewhere, possibly in

"wrong" position.

--

Waldek Hebisch

Aug 27, 2021, 4:55:58 AM8/27/21

to fricas...@googlegroups.com

Hi Waldek,

I can not reproduce the slowdown in the following example

after applying your patch. Did I miss something here?

On 8/24/21 8:48 PM, Waldek Hebisch wrote:

function "height" can give a noticeable boost.

- Qian

I can not reproduce the slowdown in the following example

after applying your patch. Did I miss something here?

On 8/24/21 8:48 PM, Waldek Hebisch wrote:

> two times longer than current version. More visible

> slowdown is on formal derivatives:

>

> f := operator 'f

> D(f(x), x, 655)

>

> currently takes 8.22 sec on my machine. After kernel patch

> it was much longer (I did not wait long enough to know how

> much longer).

About the performance in KERNEL, it seems that simply inline
> slowdown is on formal derivatives:

>

> f := operator 'f

> D(f(x), x, 655)

>

> currently takes 8.22 sec on my machine. After kernel patch

> it was much longer (I did not wait long enough to know how

> much longer).

function "height" can give a noticeable boost.

- Qian

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu