Thanks for your comments so far. Please note that I want to compute determinants of matrices whose entries are polynomials over QQ (so performance over ZZ is irrelevant). For the examples I offered, the determinants were characteristic polynomials but this would not be true for the cases I want to study. Also I would be computing tens of thousands of these determinants, ideally with matrices of orders of up to 30 x 30. Eventually I may want to look at cases where the entries are polynomials in two or three variables.
So this leads to the following questions. What algorithm(s) does sage use to compute determinants over QQ[t] or QQ[t,u]? Does they work over the ring of definition, or over the field of fractions? Are they polynomial time? My limited experiments seem to suggest that the default algorithm sage uses for matrices over QQ[t] is not polynomial time. As the Reference Manual suggests, I entered M.determinant? to see what algorithm was being used, but did not get any useful information. Thanks Chris On Mar 19, 4:17 am, Chris Godsil <cgod...@uwaterloo.ca> wrote: > I want to compute determinants of matrix polynomials, for matrices up > to 20 x 20, say. > The attached transcript seems to indicate 9 or 10 might be my limit. > (Or it's late > and I am being stupd?) > > ---------------------------------------------------------------------- > | Sage Version 3.4, Release Date: > 2009-03-11 | > | Type notebook() for the GUI, and license() for information. | > ---------------------------------------------------------------------- > # intel mac pro, binary distribution > > sage: P = graphs.PetersenGraph() > sage: P.delete_edge([0,1]) > sage: P.degree() > [2, 2, 3, 3, 3, 3, 3, 3, 3, 3] > sage: P > Petersen graph: Graph on 10 vertices ## but P is not the Petersen > graph now > sage: A = P.am() > sage: Id = identity_matrix(10) > sage: R.<t> = QQ[] > sage: (t+1)^5 > t^5 + 5*t^4 + 10*t^3 + 10*t^2 + 5*t + 1 > sage: M = t*Id - A; M > > [ t 0 0 0 -1 -1 0 0 0 0] > [ 0 t -1 0 0 0 -1 0 0 0] > [ 0 -1 t -1 0 0 0 -1 0 0] > [ 0 0 -1 t -1 0 0 0 -1 0] > [-1 0 0 -1 t 0 0 0 0 -1] > [-1 0 0 0 0 t 0 -1 -1 0] > [ 0 -1 0 0 0 0 t 0 -1 -1] > [ 0 0 -1 0 0 -1 0 t 0 -1] > [ 0 0 0 -1 0 -1 -1 0 t 0] > [ 0 0 0 0 -1 0 -1 -1 0 t] > sage: M.det() ## and sage hangs > > ## but the following worked > sage: K =graphs.CompleteGraph(3) > sage: B =K.am() > sage: Id = identity_matrix(3) > sage: (t*Id-B).det() > t^3 - 3*t - 2 > > sage: C = graphs.CubeGraph(3) > sage: C > 3-Cube: Graph on 8 vertices > sage: Id = identity_matrix(8) > sage: (t*Id-C.am()).det() > t^8 - 12*t^6 + 30*t^4 - 28*t^2 + 9 > > # and the cycle on 9 vertices hangs --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
