Opened 9 years ago

Closed 9 years ago

#9437 closed defect (fixed)

special linear group over finite rings

Reported by: vdelecroix Owned by: AlexGhitza
Priority: major Milestone: sage-4.6.2
Component: algebra Keywords: group, matrix, special linear
Cc: vdelecroix Merged in: sage-4.6.2.alpha3
Authors: David Loeffler Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Sage is not able to work with special linear group over finite rings (for example iterate over its element). As in the following example, the constructor accept the argument Zmod(4). But the object is not able to do anything due to call to finite field in gap. Curiously, list(G) and G.list() does not raise the same error (but both of them do).

sage: G = SL(2, Zmod(4))
sage: print G
sage: list(G)
TypeError                                 Traceback (most recent call last)
...
TypeError: variable names have not yet been set using self._assign_names(...)
error coercing to finite field
sage: G.list()
NameError                                 Traceback (most recent call last)
NameError: name 'ZmodnZObj' is not defined

Attachments (2)

trac_9437_matrix_group_finite_ring.patch (1.7 KB) - added by davidloeffler 9 years ago.
patch against 4.6.alpha1
trac_9437_matrix_group_finite_ring-rebase.patch (1.5 KB) - added by davidloeffler 9 years ago.
rebased version

Download all attachments as: .zip

Change History (11)

Changed 9 years ago by davidloeffler

patch against 4.6.alpha1

comment:1 Changed 9 years ago by davidloeffler

  • Authors set to David Loeffler
  • Milestone set to sage-4.6
  • Status changed from new to needs_review

For a matrix group G, the two commands list(G) and G.list() are totally different implementations; the former uses Gap to calculate the generators of G, and does the rest in Sage, while the latter just asks Gap for the list. The former works since #8970. The patch above fixes the latter, and adds doctests to prove that they both work.

It is, of course, really dumb that we have two independent implementations, but that's a job for another ticket.

comment:2 Changed 9 years ago by cremona

  • Reviewers set to John Cremona
  • Status changed from needs_review to needs_info

With 4.6.rc0 the patch applies and works fine. But look at these timings:

sage: G = SL(2, Zmod(4))
sage: time a = list(G)  
CPU times: user 0.05 s, sys: 0.01 s, total: 0.06 s
Wall time: 1.69 s
sage: time b = G.list() 
CPU times: user 0.07 s, sys: 0.00 s, total: 0.07 s
Wall time: 20.60 s

I'm not letting that stop me giving the patch a positive review, but it suggest that the list() method should be calling whatever the other one uses!

Testing the directory matrix_gps, the file which this patch changes now takes a very long time:

sage -t  "sage/groups/matrix_gps/matrix_group.py"           
	 [263.9 s]

whereas without the patch:

[240.1s]

Is the extra time just the time of the new doctest (if so, mark it #long time), or are some other doctests now slower?

comment:3 Changed 9 years ago by davidloeffler

  • Status changed from needs_info to needs_review

I just remembered this ticket, which I'd forgotten about completely...

Can I propose that we have another ticket for dealing with the discrepancy between the two "list" methods? It's somewhat independent of the problem with non-finite-field base rings -- even if G = SL(3, 17) then G.list() and list(G) are using completely independent implementations -- so it's a preexisting problem. Hence I'm putting this back to "needs review".

comment:4 Changed 9 years ago by davidloeffler

In fact there is already a ticket for the discrepancy of the "list" methods: #8588.

comment:5 Changed 9 years ago by davidloeffler

I've done a test and the before/after timings for testing matrix_group.py (on selmer.warwick.ac.uk using 4.6.2.alpha1) are 25.9 s and 27.0 s. I think that's acceptable without flagging anything as #long.

comment:6 Changed 9 years ago by cremona

  • Status changed from needs_review to positive_review

OK, and I checked that it still works fine with 4.6.2.alpha1.

comment:7 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This patch conflicts with #10515. So could you please rebase this patch so that it applies on top of #10515?

Changed 9 years ago by davidloeffler

rebased version

comment:8 Changed 9 years ago by davidloeffler

  • Status changed from needs_work to positive_review

Done. There's no change in the actual code of the patch, just variable names and diff context, so I'm reinstating the positive review.

comment:9 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.