simplify differences between 1.2 and 1.3

[ribrdb]

For some rational polynomial expressions, I'm seeing worse simplification results with version 1.3.1 than with 1.2. Additionally, the results take much longer to compute:

function run(e){console.time(e);try { return Algebrite.run(e)} finally{console.timeEnd(e)}}

with 1.2.0

simplify((x^2+8x-3)/(x^2-1)-(x^2+8x-3)/((x-1)*(x+1))): 334.2421875 ms
0

simplify((x^2+12x-5)/(x^2-2) - (5-12x-x^2)/(2-x^2)): 120.877197265625 ms
0

with 1.3.1

simplify((x^2+8x-3)/(x^2-1)-(x^2+8x-3)/((x-1)*(x+1))): 1446.41796875 ms
3*(1/(x^2-1)+1/(-x^2+1))

simplify((x^2+12x-5)/(x^2-2) - (5-12x-x^2)/(2-x^2)): 3286.921875 ms
x*(12/(x^2-2)+12/(-x^2+2)+x/(x^2-2)+x/(-x^2+2))

I'm also seeing many expressions that used to run quickly evaluating much slower. It seems possible this is from the rational simplification. Maybe that should be a separate function? Or have a way to turn it off for quicker results.

[davidedc]

Do you happen to have more information about this @ribrdb ? Maybe the exact commit that made things worse? Or minimal example that shows the problem? Or something like a test set with a range of small examples that I could use?

I'd be happy to address this, but there are other bugs that take priority. If you have the time to collect more information then I'd be happy to take a look earlier though.

[davidedc]

note to self: might be related to #109 (comment) ?

[ribrdb]

It appears to be caused by the gcd part of 358e699

[ribrdb]

Here's some reduced versions of those two cases:
1/a - (-1/-a):
simplify(1/(x-1) - (-1/(1-x)))

1/a - 1/factor(a):
simplify(1/(x^2-1)-1/((x-1)*(x+1)))

[davidedc]

Thanks for finding the commit, that helps a lot.

I think the gcd changes were good. For example pre-358e699 we have Algebrite.run("gcd((x-1),(1-x))"); -> 1, while post-358e699 Algebrite.run("gcd((x-1),(1-x))"); -> x-1. I think it's the improvements to gcd that don't work well with the rationalise code that invoke gcd.

In fact I think that the problem boils down to "rationalize" not doing its job properly: pre-358e699 we have Algebrite.run("rationalize(1/(x-1) - (-1/(1-x)))"); -> 0 (despite gcd being flawed), while post-358e699 Algebrite.run("rationalize(1/(x-1) - (-1/(1-x)))"); -> (1+1/(x-1)-x/(x-1))/(-x+1)

It looks to me that rationalize was "tuned" to the old gcd not working, and it now needs rework.

Will look into this more.

P.S. gcd itself is better than before, but it factors polynomials to get the job done, which is extreme overkill, and limits the degree (because we factor via symbolic roots which works up to a point and is expensive). Should be using Euclid's algorithm instead.

[davidedc]

log showing how the "correct" gcd confuses "rationalise":

Leaving the "correct" gcd:

> Algebrite.run("rationalize(1/(x-1) - (-1/(1-x)))");
[Log] rationalize: this is the input expr: 1/(-1+x)+1/(1-x)
[Log] rationalize: this is the denominator: 1-x
[Log] term: 1/(-1+x)
[Log] term: 1/(1-x)
[Log] rationalize: original terms times common denominator: 1+(1-x)/(-1+x)
[Log] rationalize: after factoring: 1+1/(-1+x)-x/(-1+x)
[Log] rationalize: after dividing by common denom. (and we're done): (1+1/(-1+x)-x/(-1+x))/(1-x)
< "(1+1/(x-1)-x/(x-1))/(-x+1)"

i.e. in [Log] rationalize: original terms times common denominator: 1+(1-x)/(-1+x), the system is not noticing the num/denom simplification of the monomial due to the different sign.

Sabotaging gcd to just return 1:

> Algebrite.run("rationalize(1/(x-1) - (-1/(1-x)))");
[Log] rationalize: this is the input expr: 1/(-1+x)+1/(1-x)
[Log] rationalize: this is the denominator: (-1+x)*(1-x)
[Log] term: 1/(-1+x)
[Log] term: 1/(1-x)
[Log] rationalize: original terms times common denominator: 0
[Log] rationalize: after factoring: 0
[Log] rationalize: after dividing by common denom. (and we're done): 0
< "0"

...in this case the system finds an inefficient denominator which contains both monomials (due to bad gcd), one with each sign, so each term's denominator finds a matching one, and hence triggers the num/denom simplification.

...So it would seem that just by improving themultiply routine to check for different sign should work.

[28raining]

Hi @davidedc, I'm hitting similar issues with simplification. Will you get a chance to look at it?

Nerdamer also has simplification issues, it seems if we want simplification there is no library out there.

Screenshots attached of before and after simplification

[Yaffle]

@28raining ,
you can try my lib , but it has its own issues.
Are your use cases all "rational polynomial expressions" as well?

[28raining]

Hey Yaffle, awesome, your lib works!
These equations are coming from a matrix inverse operation*

Would be super helpful if you can support variable name like R1 - I just created an issue on your git.

var matrix = ExpressionParser.parse('-1/(ab(-1/(ab)-1/(ac)-1/(bc)))-1/(ac(-1/(ab)-1/(ac)-1/(bc)))');

*inverse matrix is part of MNA, which I'm building a web tool around https://lpsa.swarthmore.edu/Systems/Electrical/mna/MNA2.html