Ask Your Question
2

Large symbolic determinant

asked 2011-03-24 17:06:25 -0500

David Ferrone gravatar image

updated 2015-01-27 13:57:56 -0500

FrédéricC gravatar image

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 flag offensive close merge delete

Comments

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?

benjaminfjones gravatar imagebenjaminfjones ( 2011-03-24 17:58:10 -0500 )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.)

David Ferrone gravatar imageDavid Ferrone ( 2011-03-31 13:13:54 -0500 )edit

3 answers

Sort by » oldest newest most voted
5

answered 2011-03-24 18:57:57 -0500

updated 2011-03-24 18:59:10 -0500

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.

edit flag offensive delete link more
0

answered 2011-03-25 03:31:59 -0500

kcrisman gravatar image

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.

edit flag offensive delete link more
0

answered 2015-01-27 11:54:09 -0500

updated 2015-01-27 12:41:37 -0500

kcrisman gravatar image

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?

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2011-03-24 17:06:25 -0500

Seen: 933 times

Last updated: Jan 27 '15