Slowness of RSolve for third-order relations and above

[pie3636]

Description

Mathics hangs when using RSolve on a linear fourth-order recurrence relation with simple coefficients, which should be able to be handled in seconds. The CPU usage is high while the command is running, but no output is produced even after 15+ minutes on a decent CPU (Ryzen 5 5600H).

I also tried a third-order recurrence instead, and the correct output was produced after a total of 70 seconds, which still seems excessive. Dropping the +1 to make the relation homogeneous doesn't cut down on the processing time either.

The commands used are as follows:
Fourth-order: RSolve[{a[n] == a[n-1] + a[n-4] + 1, a[0] == 0, a[1] == 1, a[2] == 2, a[3] == 3}, a[n], n]
Third-order: RSolve[{a[n] == a[n-1] + a[n-3] + 1, a[0] == 0, a[1] == 1, a[2] == 2}, a[n], n]

How to Reproduce

$mathics -e 'RSolve[{a[n] == a[n-1] + a[n-4] + 1, a[0] == 0, a[1] == 1, a[2] == 2, a[3] == 3}, a[n], n]'
$mathics -e 'RSolve[{a[n] == a[n-1] + a[n-3] + 1, a[0] == 0, a[1] == 1, a[2] == 2}, a[n], n]'

Output Given

None after 15 minutes for the fourth-order relation.

Expected behavior

The closed form expression of the sequence in a reasonable time.

Your Environment

Mathics 6.0.4
on CPython 3.11.9 (main, Apr 27 2024, 21:16:11) [GCC 13.2.0]
using SymPy 1.12, mpmath 1.3.0, numpy 1.24.4, cython Not installed

OS: Ubuntu 24.04 running on WSL2

Priority

Very low

[rocky]

I looked at this a little bit. The slowness seems completely inside sympy.rsolve.

The input to sympy is:

f = _Mathics_User_Global`a(_Mathics_User_Global`n)
   - _Mathics_User_Global`a(_Mathics_User_Global`n - 3) 
   - _Mathics_User_Global`a(_Mathics_User_Global`n - 1) 
   - 1
y = _Mathics_User_Global`a(_Mathics_User_Global`n)
init = {_Mathics_User_Global`a(0): 0, _Mathics_User_Global`a(1): 1, _Mathics_User_Global`a(2): 2}
sympy.solvers.recur.rsolve(f, y, init)

(You can shorten the variables by removing the prefix _Mathics_User_Global in the variable names, so that you can use a, n, instead of the longer names).

Someone (perhaps you?) needs to investigate why sympy rsolve() is slow on this describe how on would translate this relation into something that sympy can solve quicker.

[pie3636]

Thank you for the reply!

Sorry, I was not very familiar with the inner workings of Mathics, but this seems to be a sympy issue then, right?
In this case, I will report it on their bug tracker instead, and feel free to close this issue!

[rocky]

Not totally sure if it is a SymPy issue or not.

It could be that what you want to do is impossible. If you have access to the Wolfram Language, does it give the expected results there in a reasonable amount of time?

If so, it could be a known limitation of SymPy. So I'd investigate whether that's the case.

There are other kinds of rsolve() functions in Sympy, so it may be that one of those is more suitable and we need a way to either translate this automatically into one of those other functions, or have a way for the Mathics3 user to specify how to translate this.

Let me close with a little about open source. The original idea was that everyone is contributing whatever she/he can to make things better for everyone. When things break, since the code is available, the person discovering a problem has code around to investigate and even fix.

[pie3636]

If you have access to the Wolfram Language, does it give the expected results there in a reasonable amount of time?

Wolfram Alpha produces an answer for the third-order equation in fractions of a second. It doesn't for the fourth-order one, but I don't have access to Mathematica or Wolfram Alpha pro so I cannot confirm whether this is just a limitation of the free version or if it's just an inherently hard problem. That said, it's still very possible (although tedious) to calculate the result by hand up to the fourth-order, so I suspect that it shouldn't be too hard for a CAS either.

Let me close with a little about open source.

I appreciate the reminder, though I'm well-aware of how open source works :)
I sadly have very little time to dedicate to the project right now, but I might look into the different rsolve functions at some point.

[rocky]

I appreciate the reminder, though I'm well-aware of how open source works :) I sadly have very little time to dedicate to the project right now, but I might look into the different rsolve functions at some point.

Ok - if you have a chance to look into in at some point in the future, that would be great! From my standpoint, I am perfectly happy for this particular issue to hang out here as a low-priority item.

(To set expectations, in another project I oversee, there was a bug lasting 6 years that seemed to impact a number of people. The fix by a who happened to see come across it went in about 3 months ago; I just finished putting out a new release, although there are still a few things I should do on that.)

I think the reason I mentioned or reminded about how open-source works, is that there seemed to be an (inadvertent?) willingness to involve more open-source volunteers without having first done what you can to understand the situation beforehand.