[PATCH] optimize =$EXPR

[Qian Yun]

Testing for equality (or inequality) of EPXR is
a core part of Kernel and other places.

I find that current situation can be improved.

To test equality, we do not need to compute (x-y)
in full, we can skip the denominator part, skip gcd,
skip potential "algreduc" (rationalizing the denominator),
save a few unnecessary "reduc" calls (only reduce on
necessary algebraic kernels).

I believe the following change doesn't break anything.

As a benchmark, for mapleok.input, the memory usage
drop from 13.5GB to 8.5GB, time usage from 14.5s to
12.2s.

- Qian

diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad
index 6b9a11b5..86f94145 100644
--- a/src/algebra/expr.spad
+++ b/src/algebra/expr.spad
@@ -139,7 +139,8 @@
simplifyPower(denominator x, n::Integer)

smaller?(x : %, y : %) == smaller?(x, y)$Rep
- x : % = y : % == (x - y) =$Rep 0$Rep
+ x : % = y : % ==
+ numerator(x)*denominator(y) =$Rep
denominator(x)*numerator(y)
numer x == numer(x)$Rep
denom x == denom(x)$Rep

[Waldek Hebisch]

On Thu, Jun 11, 2026 at 06:33:03PM +0800, Qian Yun wrote:
> Testing for equality (or inequality) of EPXR is
> a core part of Kernel and other places.
>
> I find that current situation can be improved.
>
> To test equality, we do not need to compute (x-y)
> in full, we can skip the denominator part, skip gcd,

yes

> skip potential "algreduc" (rationalizing the denominator),
> save a few unnecessary "reduc" calls (only reduce on
> necessary algebraic kernels).

we definitely need 'reduc'. 'algreduc' is actually about
improving efficiency, because _correct_ alternatives are
more expensive.

> I believe the following change doesn't break anything.

AFAICS this is essentially the same as NAG version:

x:% = y:% == x =$Rep y

(where Rep is doing calculation which you expanded inline)
which was changed to current one because the simpler thing
is sometimes incorrect.

> As a benchmark, for mapleok.input, the memory usage
> drop from 13.5GB to 8.5GB, time usage from 14.5s to
> 12.2s.
>
> - Qian
>
> diff --git a/src/algebra/expr.spad b/src/algebra/expr.spad
> index 6b9a11b5..86f94145 100644
> --- a/src/algebra/expr.spad
> +++ b/src/algebra/expr.spad
> @@ -139,7 +139,8 @@
> simplifyPower(denominator x, n::Integer)
>
> smaller?(x : %, y : %) == smaller?(x, y)$Rep
> - x : % = y : % == (x - y) =$Rep 0$Rep
> + x : % = y : % ==
> + numerator(x)*denominator(y) =$Rep
> denominator(x)*numerator(y)
> numer x == numer(x)$Rep
> denom x == denom(x)$Rep
>

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/54bf5511-7487-41e1-8f1f-169128536449%40gmail.com.

--
Waldek Hebisch

[Waldek Hebisch]

On Thu, Jun 11, 2026 at 06:33:03PM +0800, Qian Yun wrote:

> Testing for equality (or inequality) of EPXR is
> a core part of Kernel and other places.
>
> I find that current situation can be improved.
>
> To test equality, we do not need to compute (x-y)
> in full, we can skip the denominator part, skip gcd,
> skip potential "algreduc" (rationalizing the denominator),
> save a few unnecessary "reduc" calls (only reduce on
> necessary algebraic kernels).
>
> I believe the following change doesn't break anything.

Look at commit 3255808d742077bc16f5ab47d658be3e80dcdf16

--
Waldek Hebisch

[Qian Yun]

On 6/11/26 7:44 PM, Waldek Hebisch wrote:
> On Thu, Jun 11, 2026 at 06:33:03PM +0800, Qian Yun wrote:
>> Testing for equality (or inequality) of EPXR is
>> a core part of Kernel and other places.
>>
>> I find that current situation can be improved.
>>
>> To test equality, we do not need to compute (x-y)
>> in full, we can skip the denominator part, skip gcd,
>
> yes
>
>> skip potential "algreduc" (rationalizing the denominator),
>> save a few unnecessary "reduc" calls (only reduce on
>> necessary algebraic kernels).
>
> we definitely need 'reduc'. 'algreduc' is actually about
> improving efficiency, because _correct_ alternatives are
> more expensive.
>

Not all 'reduc' are skipped, it used to happen for
commonk(x, y), now it is commonk(numer x, denom y)
and commonk(denom x, numer y) separately.
(The 'reduc' is only needed for multiplication, right?)

'algreduc' is not totally skipped, it is skipped
for denom(x)*denom(y).

- Qian

[Qian Yun]

On 6/11/26 7:44 PM, Waldek Hebisch wrote:
>

> AFAICS this is essentially the same as NAG version:
>
> x:% = y:% == x =$Rep y
>
> (where Rep is doing calculation which you expanded inline)
> which was changed to current one because the simpler thing
> is sometimes incorrect.
>

> Look at commit 3255808d742077bc16f5ab47d658be3e80dcdf16

It is not the same as old one, because I'm doing
multiplication in EXPR, not Rep. So 'reduc' is applied.

In theory, I didn't missing anything, right?

- Qian

[Waldek Hebisch]

I see, mutiplication in EXPR is probably good enough to pass
our existing tests, but this does not look right. Note that
we may have nested roots and mutiplying two roots may introduce
new denominators.

In general, representation of Expression is only normal: when
result of an operation is 0 it will give 0 at representation
level, but equal expressions may have different representations.

AFAICS the following should be OK:

algreduc((numer(x)*$Rep denom(y) -$Rep numer(y)*$Rep denom(x))::%,
commonk(x, y)) =$Rep 0

--
Waldek Hebisch

[Qian Yun]

On 6/11/26 11:48 PM, Waldek Hebisch wrote:
>
> I see, mutiplication in EXPR is probably good enough to pass
> our existing tests, but this does not look right. Note that
> we may have nested roots and mutiplying two roots may introduce
> new denominators.
>
> In general, representation of Expression is only normal: when
> result of an operation is 0 it will give 0 at representation
> level, but equal expressions may have different representations.
>
> AFAICS the following should be OK:
>
> algreduc((numer(x)*$Rep denom(y) -$Rep numer(y)*$Rep denom(x))::%,
> commonk(x, y)) =$Rep 0
>

Thanks, this works (need to tweak signature a bit), but the memory
usage grows from 8.5GB to 9.7GB compare to previous (flawed) version.

Profile shows lots of time and memory is spent in =$EXPR, reduc$EXPR.

As I see it, the purpose of 'reduc' is to simplify algebraic expression,
and the purpose of 'algreduc' is to rationalize the denominator
depending on getSimplifyDenomsFlag.

I can leave 'algreduc' alone. But for 'reduc', I think its
implementation is very inefficient. I think, in theory,
we can walk the variables of Rep to check for algebraic kernels
and do transformation if necessary.

I'll report back with numbers.

- Qian

[Waldek Hebisch]

On Fri, Jun 12, 2026 at 07:42:14AM +0800, Qian Yun wrote:
> On 6/11/26 11:48 PM, Waldek Hebisch wrote:
> >
> > I see, mutiplication in EXPR is probably good enough to pass
> > our existing tests, but this does not look right. Note that
> > we may have nested roots and mutiplying two roots may introduce
> > new denominators.
> >
> > In general, representation of Expression is only normal: when
> > result of an operation is 0 it will give 0 at representation
> > level, but equal expressions may have different representations.
> >
> > AFAICS the following should be OK:
> >
> > algreduc((numer(x)*$Rep denom(y) -$Rep numer(y)*$Rep denom(x))::%,
> > commonk(x, y)) =$Rep 0
> >
>
> Thanks, this works (need to tweak signature a bit), but the memory
> usage grows from 8.5GB to 9.7GB compare to previous (flawed) version.
>
> Profile shows lots of time and memory is spent in =$EXPR, reduc$EXPR.
>
> As I see it, the purpose of 'reduc' is to simplify algebraic expression,
> and the purpose of 'algreduc' is to rationalize the denominator
> depending on getSimplifyDenomsFlag.

Yes. Actually, above in test for equality we should be able to
replace 'algreduc' by 'reduc'.

> I can leave 'algreduc' alone. But for 'reduc', I think its
> implementation is very inefficient. I think, in theory,
> we can walk the variables of Rep to check for algebraic kernels
> and do transformation if necessary.

Hmm, that is what 'reduc' is essentially doing. But there is a
catch: reducing with respect to one kernel may expose other ones.
So we order kernels and start reduction from the most complex
one and then repeat this with simpler kernels. Also, we allow
arbitrary algebraic kernels and do not require minimal polynomials
to be monic, so reduction is more complex than in case of roots.

--
Waldek Hebisch

[Qian Yun]

On 6/12/26 8:42 AM, Waldek Hebisch wrote:
>
>> I can leave 'algreduc' alone. But for 'reduc', I think its
>> implementation is very inefficient. I think, in theory,
>> we can walk the variables of Rep to check for algebraic kernels
>> and do transformation if necessary.
>
> Hmm, that is what 'reduc' is essentially doing. But there is a
> catch: reducing with respect to one kernel may expose other ones.
> So we order kernels and start reduction from the most complex
> one and then repeat this with simpler kernels. Also, we allow
> arbitrary algebraic kernels and do not require minimal polynomials
> to be monic, so reduction is more complex than in case of roots.
>

Because 'reduc' is called by every + - * / =, any tiny
optimization could be helpful in the end.

My current plan is to do search and replace in parallel,
say for alg_ker1^n1*alg_ker2^n2, do transformation for them
in one loop. Then loop on the result until no transformation
are needed. This should save many memory allocations.

Also this opens doors for optimization like
sum([e1,e2,e3,...]), mul([e1,e2,e3,...]).

- Qian