# Large symbolic determinant

I have a dense matrix with symbolic variable entries. I am interested in the equation that describes when the matrix is singular. So I have been having Sage compute the determinant of this matrix and set it equal to zero, and return this expression (a polynomial in several variables).

However when the dimensions get larger (around 9 variables) Sage is taking an incredibly long amount of time to do it. (My program has to perform a number of other tasks as well, the determinant seems to be taking up all the run-time.)

Is there any way I can speed up this kind of computation?

edit retag close merge delete

How big is the matrix? You say 9 variables, but do you mean a very large matrix over the symbolic ring with 9 generators, or do you mean a 9x9 matrix?

( 2011-03-24 23:58:10 +0200 )edit

Not a 9x9, though actually it's smaller than that, a 4x4, but involves many variables. In a sense I'm actually using 18 variables, sorry. I'm taking an upper (symbolic, so I'm not sure how to make it sparse...) triangular matrix (a 4x8) formed by a set of 8 variables, say a0, ... a7. I'm multiplying this by the transpose of another upper triangular matrix with a different set of variables, say b0, ..., b6. Then I'm taking the determinant of that. (I can write the second variables in terms of the first, but I don't think it would speed up the computation.)

( 2011-03-31 20:13:54 +0200 )edit

Sort by » oldest newest most voted

Maybe using polynomial elements instead of symbolic variables might work. On sage.math.washington.edu, the polynomial computations are much faster:

sage: var(' '.join(['a%s'%str(i) for i in range(9)]))
(a0, a1, a2, a3, a4, a5, a6, a7, a8)
sage: R = PolynomialRing(QQ, ['x%s' % str(i) for i in range(9)])
sage: R.inject_variables()
Defining x0, x1, x2, x3, x4, x5, x6, x7, x8
sage: A = [a0, a1, a2, a3, a4, a5, a6, a7, a8]
sage: X = [x0, x1, x2, x3, x4, x5, x6, x7, x8]

sage: time d = matrix(6, 6, A + [a^2 for a in A] + [a^3 for a in A] + [a^4 for a in A]).det()
CPU times: user 26.97 s, sys: 0.00 s, total: 26.97 s
Wall time: 27.02 s
sage: time d = matrix(6, 6, X + [a^2 for a in X] + [a^3 for a in X] + [a^4 for a in X]).det()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: timeit('matrix(6, 6, X + [a^2 for a in X] + [a^3 for a in X] + [a^4 for a in X]).det()')
625 loops, best of 3: 1.27 ms per loop


The 8x8 case takes about 12 seconds with polynomials, and I hesitate to even try it with symbolic variables.

more

I have the same problem. I am trying to compute the determinant of f, for some given matrix A and with I being the identity. I want the determinant to be a function of x , y, and m, or at least a function of x and y for some fixed m. I should be getting a polynomial in two variables, x and y. The entries of the original matrix A are all of the form a+b*sqrt(m) with a and b being integers. Here is my routine. Assume A has been defined.

m=3
x, y = PolynomialRing(RationalField(), 2, ['x','y']).gens()
f=((x+y*sqrt(m))*I-A).determinant()
d=f.expand().collect(sqrt(m))
d


It works fine if A is a 4x4 matrix, but if I raise it to a 9x9 matrix, SAGE simply locks up right at the second line where I define f. I let it run overnight (about 14 hours) and nothing happened.

My level of experience with SAGE is rather limited, but the fact that it works with small size matrices tells me that I have done -- I hope -- nothing wrong. In fact, SAGE does not return error messages; it simply stops. Does anyone have any suggestion?

more

This won't help you, but if it's a comfort, symbolic matrices of the kind you are mentioning are done in Maxima, and the block is there. If you can do what John suggests for your use case, it may be worth it. However, if you have non-polynomial elements, then you probably are just running into a computational problem of a general sort. Posting your original example could be helpful as well.

more