Revision history [back]

Eigenvalues over symbolic ring

I am trying to compute the eigenvalues of a 16x16 matrix whose eigenvalues are multivariate polynomials in 4 variables of degree at most 3 and integer coefficients. When I try to do so using the Symbolic Ring SR my machine quickly runs out of memory (~15GB available I believe).

I tried to change the ring to the fraction field of a Multivariate Polynomial Ring over Rational Field, and this allows to quickly compute the characteristic polynomial and its roots, without killing my machine. Unfortunately though some of the eigenvalues are not rational functions, so they do not show up.

Mathematica on the same machine is able to compute the eigenvalues symbolically, and I can solve a similar problem in Sage if I only use 2 variables. Am I missing something, or is simply the algorithm used by Sage not efficient enough for 16x16 matrices in 4 variables?

Eigenvalues over symbolic ring

TypeError: ECL says: Memory limit reached. Please jump to an outer pointer, quit program and enlarge the memory limits before executing the program again.

I am using sage 8.1 (and I could try to upgrade if that is the issue here). The example I am struggling with is included at the end of this question (I did not write this by hand, but I don't think that it is relevant how the matrix was generated. One should be able to copy-and-paste this into Sage)

R = QQ['a,b,c,d']
N = matrix(R, 16, 16, M)
N.change_ring(R.fraction_field()).characteristic_polynomial().roots()

Mathematica on the same machine is able to compute the eigenvalues ~~symbolically,~~ symbolically (quite quickly actually), and I can solve a similar problem in Sage if I only use 2 variables. Am I missing something, or is simply the algorithm used by Sage not efficient enough for 16x16 matrices in 4 variables?

a,b,c,d = var('a','b','c','d', domain='positive')
M = matrix(16,16,[
(3*c^2*d + 6*c + 1, 0, 0, (a - b)*c*d + a - b, 0, (a - b)*c*d + a - b, (a - b)*c*d + a - b, 0, 0, (a - b)*c*d + a - b, (a - b)*c*d + a - b, 0, (a - b)*c*d + a - b, 0, 0, 3*(a - b)^2*d),
(0, -3*c^2*d + 1, (a + b)*c*d + a + b, 0, (a + b)*c*d + a + b, 0, 0, -(a - b)*c*d + a - b, (a + b)*c*d + a + b, 0, 0, -(a - b)*c*d + a - b, 0, -(a - b)*c*d + a - b, 3*(a + b)*(a - b)*d, 0),
(0, (a + b)*c*d + a + b, -3*c^2*d + 1, 0, (a + b)*c*d + a + b, 0, 0, -(a - b)*c*d + a - b, (a + b)*c*d + a + b, 0, 0, -(a - b)*c*d + a - b, 0, 3*(a + b)*(a - b)*d, -(a - b)*c*d + a - b, 0),
((a - b)*c*d + a - b, 0, 0, 3*c^2*d - 2*c + 1, 0, -(a + b)*c*d + a + b, -(a + b)*c*d + a + b, 0, 0, -(a + b)*c*d + a + b, -(a + b)*c*d + a + b, 0, (2*(a + b)^2 + (a - b)^2)*d, 0, 0, (a - b)*c*d + a - b),
(0, (a + b)*c*d + a + b, (a + b)*c*d + a + b, 0, -3*c^2*d + 1, 0, 0, -(a - b)*c*d + a - b, (a + b)*c*d + a + b, 0, 0, 3*(a + b)*(a - b)*d, 0, -(a - b)*c*d + a - b, -(a - b)*c*d + a - b, 0),
((a - b)*c*d + a - b, 0, 0, -(a + b)*c*d + a + b, 0, 3*c^2*d - 2*c + 1, -(a + b)*c*d + a + b, 0, 0, -(a + b)*c*d + a + b, (2*(a + b)^2 + (a - b)^2)*d, 0, -(a + b)*c*d + a + b, 0, 0, (a - b)*c*d + a - b),
((a - b)*c*d + a - b, 0, 0, -(a + b)*c*d + a + b, 0, -(a + b)*c*d + a + b, 3*c^2*d - 2*c + 1, 0, 0, (2*(a + b)^2 + (a - b)^2)*d, -(a + b)*c*d + a + b, 0, -(a + b)*c*d + a + b, 0, 0, (a - b)*c*d + a - b),
(0, -(a - b)*c*d + a - b, -(a - b)*c*d + a - b, 0, -(a - b)*c*d + a - b, 0, 0, -3*c^2*d + 1, 3*(a + b)*(a - b)*d, 0, 0, (a + b)*c*d + a + b, 0, (a + b)*c*d + a + b, (a + b)*c*d + a + b, 0),
(0, (a + b)*c*d + a + b, (a + b)*c*d + a + b, 0, (a + b)*c*d + a + b, 0, 0, 3*(a + b)*(a - b)*d, -3*c^2*d + 1, 0, 0, -(a - b)*c*d + a - b, 0, -(a - b)*c*d + a - b, -(a - b)*c*d + a - b, 0),
((a - b)*c*d + a - b, 0, 0, -(a + b)*c*d + a + b, 0, -(a + b)*c*d + a + b, (2*(a + b)^2 + (a - b)^2)*d, 0, 0, 3*c^2*d - 2*c + 1, -(a + b)*c*d + a + b, 0, -(a + b)*c*d + a + b, 0, 0, (a - b)*c*d + a - b),
((a - b)*c*d + a - b, 0, 0, -(a + b)*c*d + a + b, 0, (2*(a + b)^2 + (a - b)^2)*d, -(a + b)*c*d + a + b, 0, 0, -(a + b)*c*d + a + b, 3*c^2*d - 2*c + 1, 0, -(a + b)*c*d + a + b, 0, 0, (a - b)*c*d + a - b),
(0, -(a - b)*c*d + a - b, -(a - b)*c*d + a - b, 0, 3*(a + b)*(a - b)*d, 0, 0, (a + b)*c*d + a + b, -(a - b)*c*d + a - b, 0, 0, -3*c^2*d + 1, 0, (a + b)*c*d + a + b, (a + b)*c*d + a + b, 0),
((a - b)*c*d + a - b, 0, 0, (2*(a + b)^2 + (a - b)^2)*d, 0, -(a + b)*c*d + a + b, -(a + b)*c*d + a + b, 0, 0, -(a + b)*c*d + a + b, -(a + b)*c*d + a + b, 0, 3*c^2*d - 2*c + 1, 0, 0, (a - b)*c*d + a - b),
(0, -(a - b)*c*d + a - b, 3*(a + b)*(a - b)*d, 0, -(a - b)*c*d + a - b, 0, 0, (a + b)*c*d + a + b, -(a - b)*c*d + a - b, 0, 0, (a + b)*c*d + a + b, 0, -3*c^2*d + 1, (a + b)*c*d + a + b, 0),
(0, 3*(a + b)*(a - b)*d, -(a - b)*c*d + a - b, 0, -(a - b)*c*d + a - b, 0, 0, (a + b)*c*d + a + b, -(a - b)*c*d + a - b, 0, 0, (a + b)*c*d + a + b, 0, (a + b)*c*d + a + b, -3*c^2*d + 1, 0),
(3*(a - b)^2*d, 0, 0, (a - b)*c*d + a - b, 0, (a - b)*c*d + a - b, (a - b)*c*d + a - b, 0, 0, (a - b)*c*d + a - b, (a - b)*c*d + a - b, 0, (a - b)*c*d + a - b, 0, 0, 3*c^2*d + 6*c + 1)]
)