On 4 Aug, 15:05, Robert Miller <[email protected]> wrote:
> http://en.wikipedia.org/wiki/Dodgson_condensation
>
> Chris Godsil pointed out to me yesterday that determinants over
> generic rings uses expansion by minors, which is exponential. Much
> better would be to use Charles Dodgson's method, which is cubic,
> described in the link above. This might be a fun project for someone
> new to Sage development, as it is not the most complicated thing in
> the world to implement, and is rather self-contained.
>
> {{{
>
> "But I don't want to go among mad people," Alice remarked.
>
> Oh, you can't help that," said the Cat: "we're all mad here. I'm mad.
> You're mad."
>
> How do you know I'm mad?" said Alice.
>
> You must be," said the Cat, "or you wouldn't have come here."
>
> }}}
>
> --
> Robert L. Millerhttp://www.rlmiller.org/
Hi Robert,
Actually, I don't think it does. If you have a look at
def determinant(self, algorithm=None):
on line 951 in matrix2.pyx, you can see that in the generic case the
characteristic polynomial is computed using a division free algorithm
in time O(n^4). From what I remember from memory (when I implemented
this), I think the ideas behind this are quite similar to Dodgson's
method.
Following that method, there's the method
cdef _det_by_minors(self, Py_ssize_t level):
but I don't think that's called anywhere apart from the recursive
calls.
Sebastian
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
