angelolucia's profile - activity

I do (in terms of tensor product of smaller matrices), but I don't think it would have helped to the discussion.

Thank you very much! This is indeed a pretty good idea. I have noticed that doing computations with the polynomial ring Sage uses Singular (while I guess it is using Maxima for the symbolic ring). Even computing the characteristic polynomial over the symbolic ring is too much for my machine, but the answer should be the same in both cases, right?

Regarding the applicability of this approach in general: I suppose a polynomial matrix could have a lot (all?) eigenvalues that are non-rational functions, so this approach would fail in that cases: but wouldn't it reduce to the original symbolic calculations in that case? In other words, can this actually be harmful?

Thanks! I have tried to include the example, I hope it is at least copy-pastable (it's a 16x16 matrix after all)

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).

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)

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. This is what I did

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 (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)]
)