Opened 12 years ago

Closed 11 years ago

# [fixed by #5842] constructing the ring of integers of a relative number field is SLOW

Reported by: Owned by: AlexGhitza davidloeffler major sage-duplicate/invalid/wontfix number fields N/A

### Description

David Loeffler reported this on sage-devel:

```sage: K.<a> = QuadraticField(-23)
sage: L.<b> = K.extension(x^3 - x - 1)
sage: OL = L.ring_of_integers()   # infinite loop?
```

Note also that CTRL-C seems to have no effect. I see the same problem on my 32-bit Archlinux machine.

### comment:1 Changed 12 years ago by AlexGhitza

Actually, CTRL-C does eventually stop this, with the following result:

```KeyboardInterrupt                         Traceback (most recent call last)

/home/ghitza/.sage/temp/artin/14950/_home_ghitza__sage_init_sage_0.py in <module>()

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/rings/number_field/number_field_base.so in sage.rings.number_field.number_field_base.NumberField.ring_of_integers (sage/rings/number_field/number_field_base.c:1090)()

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/rings/number_field/number_field_rel.pyc in maximal_order(self)
438         O = K.maximal_order()
439         B = [from_K(z) for z in O.basis()]
--> 440         OK = self.order(B, check_is_integral=False, check_rank=False)
441         self.__maximal_order = OK
442         return OK

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/rings/number_field/number_field_rel.pyc in order(self, *gens, **kwds)
1363             gens = gens[0]
1364         gens = [self(x) for x in gens]
-> 1365         return order.relative_order_from_ring_generators(gens, **kwds)
1366
1367

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/rings/number_field/order.pyc in relative_order_from_ring_generators(gens, check_is_integral, check_rank, is_maximal, allow_subfield)
1647     abs_order =  absolute_order_from_module_generators(absolute_order_module_gens,
1648                                                        check_integral=False, check_is_ring=False,
-> 1649                                                        check_rank=check_rank)
1650
1651     return RelativeOrder(K, abs_order, check=False, is_maximal=is_maximal)

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/rings/number_field/order.pyc in absolute_order_from_module_generators(gens, check_integral, check_rank, check_is_ring, is_maximal, allow_subfield)
1565     mod_gens = [to_V(x) for x in gens]
1566     ambient = ZZ**V.dimension()
-> 1567     W = ambient.span(mod_gens)
1568
1569     if allow_subfield:

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/modules/free_module.pyc in span(self, gens, base_ring, check, already_echelonized)
2146         if base_ring is None or base_ring == self.base_ring():
2147             return FreeModule_submodule_pid(
2149         else:
2150             try:

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/modules/free_module.pyc in __init__(self, ambient, gens, check, already_echelonized)
4738         """
4739         FreeModule_submodule_with_basis_pid.__init__(self, ambient, basis=gens,
4741
4742     def _repr_(self):

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/modules/free_module.pyc in __init__(self, ambient, basis, check, echelonize, echelonized_basis, already_echelonized)
3929
3930         if echelonize and not already_echelonized:
-> 3931             basis = self._echelonized_basis(ambient, basis)
3932
3933         FreeModule_generic.__init__(self, R, rank=len(basis), degree=ambient.degree(), sparse=ambient.is_sparse())

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/modules/free_module.pyc in _echelonized_basis(self, ambient, basis)
4043         if d != 1:
4044             basis = [x*d for x in basis]
-> 4045         A = MAT(basis)
4046         E = A.echelon_form()
4047         if d != 1:

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/matrix/matrix_space.pyc in __call__(self, entries, coerce, copy, rows)
341                 entries = e
342             else:
--> 343                 entries = sum([v.list() for v in entries],[])
344
345         if rows is None:

/opt/sage-3.3.alpha0/local/lib/python2.5/site-packages/sage/interfaces/get_sigs.pyc in my_sigint(x, n)
7
8 def my_sigint(x, n):
----> 9     raise KeyboardInterrupt
10
11 def my_sigfpe(x, n):

KeyboardInterrupt:
```

### comment:2 Changed 12 years ago by AlexGhitza

• Priority changed from blocker to major
• Summary changed from sage-3.3.alpha3 gets stuck computing the ring of integers of a relative number field to constructing the ring of integers of a relative number field is SLOW

It is, in fact, not an infinite loop. It's just really, really slow. It also seems to pre-date 3.3.alpha3:

```----------------------------------------------------------------------
| Sage Version 3.2.3, Release Date: 2009-01-05                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: L.<b> = K.extension(x^3 - x - 1)
sage: time OL = L.ring_of_integers()
CPU times: user 263.94 s, sys: 12.98 s, total: 276.92 s
Wall time: 280.13 s
```

### comment:3 Changed 12 years ago by ncalexan

I do not think this is a problem with the relative number field patch; it was an existing problem. I have code that I can submit if you want to compute the relative ring of integers; it uses pari's rnfbasis.

This issue has to with the fact that `L.ring_of_integers().base_ring()` is ZZ and not `K.ring_of_integers()`. There's already a ticket for that.

### comment:4 follow-up: ↓ 6 Changed 12 years ago by davidloeffler

This works for me now (in sage 4.0.2):

```----------------------------------------------------------------------
| Sage Version 4.0.2, Release Date: 2009-06-18                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: L.<b> = K.extension(x^3 - x - 1)
sage: time OL = L.ring_of_integers()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
```

I don't know what's changed -- presumably this is something to do with Francis Clarke's campaign to fix all the relative number field bugs over the last couple of months -- but presumably we can close this ticket now?

### comment:5 Changed 12 years ago by davidloeffler

• Component changed from number theory to number fields
• Owner changed from was to davidloeffler

### comment:6 in reply to: ↑ 4 Changed 12 years ago by fwclarke

This works for me now (in sage 4.0.2): ... I don't know what's changed -- presumably this is something to do with Francis Clarke's campaign to fix all the relative number field bugs over the last couple of months -- but presumably we can close this ticket now?

Yes, this issue had already been raised in #4738, and I commented there that "The problem of the slowness of computing relative maximal orders is solved by the patch in #5842. A doctest is included at line 532 of the patched `number_field_rel.py`" (It's become line 570 by 4.1)

What changed was a rewrite of `maximal_order` for relative number fields. The previous version was repetitive and grossly wasteful of memory.

### comment:7 Changed 11 years ago by davidloeffler

• Report Upstream set to N/A
• Status changed from new to needs_review
• Summary changed from constructing the ring of integers of a relative number field is SLOW to [fixed by #5842] constructing the ring of integers of a relative number field is SLOW

We should close this ticket -- two people agree that it's fixed and there are doctests to prove it.

### comment:8 Changed 11 years ago by davidloeffler

• Status changed from needs_review to positive_review

I'm setting this to "positive review" so the release manager can close it when convenient.

### comment:9 Changed 11 years ago by mpatel

• Milestone changed from sage-4.5.2 to sage-duplicate/invalid/wontfix
• Resolution set to duplicate
• Status changed from positive_review to closed

I'm closing this ticket as a "duplicate."

Note: See TracTickets for help on using tickets.