On Thu, Mar 19, 2009 at 4:00 PM, David Kohel <drko...@gmail.com> wrote: > > Hi, > > One can always work around a problem, but it would be > better to discuss the best approach and put this in place. > > 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. This is now trac #5570: http://trac.sagemath.org/sage_trac/ticket/5570 > > Instead I worked around this by computing the determinants > mod 2 and mod 13 and using CRT (if the determinants were > both units). The time was then almost trivial. Suppose I > replace this problem over ZZ/25ZZ or ZZ/256ZZ. I would > still hope that the problem would NOT be lifted to ZZ for > computation, since this would certainly not terminate in > reasonable time for a dense matrix. Yes it would. Even for a dense 200x200 matrix over ZZ/256ZZ it only take 0.35 seconds total time to lift *and* compute the determinant, then reduce the result. sage: a = random_matrix(Integers(256), 30) sage: time Integers(256)(a.lift().det()) CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s 222 sage: a = random_matrix(Integers(256), 200) sage: time Integers(256)(a.lift().det()) CPU times: user 0.32 s, sys: 0.04 s, total: 0.35 s Just out of curiosity, why didn't you try any of the above before writing this email? :-) > Taking the approach of lifting to ZZ for charpolys of matrices > of non-trivial size will undoubtably lead to exactly the same > coefficient explosion which is the presumed source of the > problem with determinants over ZZ/26ZZ. > > --David Except it isn't anywhere nearly so bad as you think: sage: a = random_matrix(Integers(256), 500) sage: time Integers(256)(a.lift().det()) CPU times: user 3.70 s, sys: 0.49 s, total: 4.19 s Wall time: 4.04 s 188 sage: a = random_matrix(Integers(2^20), 500) sage: time Integers(256)(a.lift().det()) CPU times: user 7.23 s, sys: 0.81 s, total: 8.04 s Wall time: 7.94 s 208 All timings above on my 2GB of RAM Macbook laptop. William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
