Hi Chris,
I'm not sure what other types of matrices you're looking at, but if
the matrices are similar to the ones you posted, then one typical
approach is to evaluate the matrices at a number of points, take the
determinant, and then rebuild the determinant from that data. This
work well if you have a good degree bound on the entries since it
reduces the number of determinants you have to take. Here is a (very)
rough function that does this:
def poly_det(m, degree_bound):
#Get a bunch of points to evaluate the determinant at
points = range(degree_bound+1)
n = len(points)
#Evaluate the matrix at a number of points and compute
#the determinant
evaluations = [m.apply_map(lambda x: x(p)).det() for p in points]
#Rebuild the polynomial determinant
det_matrix = matrix( [[p^i for i in range(n)] for p in points] )
coefficients = det_matrix.solve_right(vector(evaluations))
#Return the polynomial
R = PolynomialRing(QQ, 't')
return R(list(coefficients))
Then, on my machine:
sage: C = graphs.CycleGraph(9)
sage: m = t - C.am()
sage: %time m.det()
t^9 - 9*t^7 + 27*t^5 - 30*t^3 + 9*t - 2
CPU time: 24.74 s, Wall time: 25.81 s
sage: %time poly_det(m, len(C))
t^9 - 9*t^7 + 27*t^5 - 30*t^3 + 9*t - 2
CPU time: 0.06 s, Wall time: 0.06 s
With this approach all of the "hard" linear algebra ends up being done
with fast integer linear algebra: QQ[t] -> QQ -> ZZ.
--Mike
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
