Is there a way to optimize this equation-solving code to run in a reasonable timeframe?

asked 2023-05-14 17:03:42 +0200

ZL gravatar image

I have the following lines in Sage:

var('A, B, C, E, α, β, γ, d')

f = lambda n : (
   (12*A + 6*B + 4*C + 2*E + 4*α + 2*β + γ)^n
 - (11*A + 6*B + 4*C + 2*E + 4*α + 2*β + γ)^n
 - (11*A + 5*B + 4*C + 2*E + 4*α + 2*β + γ)^n
 + (10*A + 5*B + 4*C + 2*E + 4*α + 2*β + γ)^n
 - (10*A + 5*B + 3*C + 2*E + 4*α + 2*β + γ)^n
 + ( 9*A + 5*B + 3*C + 2*E + 4*α + 2*β + γ)^n
 + ( 9*A + 4*B + 3*C + 2*E + 4*α + 2*β + γ)^n
 - ( 8*A + 4*B + 3*C + 2*E + 4*α + 2*β + γ)^n
 - ( 8*A + 4*B + 3*C +   E + 4*α + 2*β + γ)^n
 + ( 7*A + 4*B + 3*C +   E + 4*α + 2*β + γ)^n
 + ( 7*A + 3*B + 3*C +   E + 4*α + 2*β + γ)^n
 - ( 6*A + 3*B + 3*C +   E + 4*α + 2*β + γ)^n
 + ( 6*A + 3*B + 2*C +   E + 4*α + 2*β + γ)^n
 - ( 6*A + 3*B + 2*C +   E + 3*α + 2*β + γ)^n
 - ( 6*A + 3*B + 2*C +   E + 3*α +   β + γ)^n
 + ( 6*A + 3*B + 2*C +   E + 2*α +   β + γ)^n
 - ( 6*A + 3*B + 2*C +   E + 2*α +   β)^n
 + ( 6*A + 3*B + 2*C +   E +   α +   β)^n
 + ( 6*A + 3*B + 2*C +   E +   α)^n
 - ( 6*A + 3*B + 2*C +   E)^n
 + ( 6*A + 3*B +   C +   E)^n
 - ( 5*A + 3*B +   C +   E)^n
 - ( 5*A + 2*B +   C +   E)^n
 + ( 4*A + 2*B +   C +   E)^n
 + ( 4*A + 2*B +   C)^n
 - ( 3*A + 2*B +   C)^n
 - ( 3*A +   B +   C)^n
 + ( 2*A +   B +   C)^n
 - ( 2*A +   B)^n
 + (   A +   B)^n
 + A^n
)/factorial(n)

solve([f(3) == 0, f(4) == 0, f(5) == d], α, β, γ)

I want Sage to solve this system of equations for the three Greek-letter variables in terms of the five English-letter variables. However, when I ask Sage to solve this, it just sits and spins at maximum CPU usage and steadily-increasing RAM usage until I kill the process. I've waited over fifteen minutes without it completing.

Are there any ways to make this more performant?

edit retag flag offensive close merge delete

Comments

Since your equations are polynomial, you'll will have better control over their solution if you empoy polynomial ideals machinery. And even then a solution that you look for may be infeasible to compute explicitly.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-05-16 05:20:28 +0200 )edit

@Max Alekseyev I read the reference doc you linked, but I don't understand how to apply it. I looked for more-accessible tutorials on using polynomial rings online, but couldn't find anything. Do you know of any resources on the topic that would make sense to someone using Sage for the first time? Or can you explain how to apply it to this specific situation?

I tried for example adding R.<α, β, γ> = QQ['α, β, γ'] to the variable declaration section, but running the solve line after that generated the error message TypeError: α is not a valid variable.

ZL gravatar imageZL ( 2023-05-16 15:40:37 +0200 )edit

You can start with reading Wikipedia: https://en.wikipedia.org/wiki/System_...

You don't use solve() function in polynomial rings, but rather define ideals, compute their bases and/or elimination ideals, and possibly call .variety() method for 0-dimensional ideals.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-05-16 19:20:25 +0200 )edit
add a comment