#5570: determinants of matrices over Z/nZ with n composite are dog slow
----------------------------+-----------------------------------------------
Reporter: was | Owner: was
Type: defect | Status: new
Priority: major | Milestone: sage-3.4.1
Component: linear algebra | Keywords:
----------------------------+-----------------------------------------------
In Sage it is not feasable to directly compute the determinant of a 20x20
matrix over Integers(26)!
{{{
David Kohel:
> A related problem I had recently was in finding a random
> element of GL_n(ZZ/26ZZ) where n was 20-30. It was
> failing to terminate in the determinant computation. My
> guess is that a determinant over ZZ was being computed
> and reduced but that the resulting determinant was too big.
> I didn't verify this, but invite someone to check.
It is trivial to compute the determinant of an nxn matrix over ZZ when n
<= 30 and the entries of the matrix have 2 digits. That would be the case
in your example. Sage wasn't computing your det over ZZ; if it had, then
doing that computation would have worked fine. For example:
----------------------------------------------------------------------
| Sage Version 3.4, Release Date: 2009-03-11 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: a = random_matrix(Integers(26), 7)
sage: time a.det()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.05 s
6
sage: a = random_matrix(Integers(26), 8)
sage: time a.det()
CPU times: user 0.15 s, sys: 0.00 s, total: 0.15 s
Wall time: 0.16 s
9
sage: a = random_matrix(Integers(26), 9)
sage: time a.det()
CPU times: user 1.37 s, sys: 0.01 s, total: 1.37 s
Wall time: 1.38 s
23
sage: time Integers(26)(a.lift().det())
CPU times: user 0.02 s, sys: 0.01 s, total: 0.03 s
Wall time: 0.39 s
23
sage: time Integers(26)(a.lift().det())
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
23
sage: a = random_matrix(Integers(26), 9)
sage: time Integers(26)(a.lift().det())
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
10
sage: a = random_matrix(Integers(26), 30)
sage: time Integers(26)(a.lift().det())
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
20
sage: a = random_matrix(Integers(26), 200)
sage: time Integers(26)(a.lift().det())
CPU times: user 0.30 s, sys: 0.04 s, total: 0.33 s
Wall time: 0.34 s
15
It would thus be far better for now if Sage were to lift to ZZ, do the
det, then reduce again.
For square-free modulus, a multimodular algorithm would of course be even
better.
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5570>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
