Faster norm calculations

[MvanBeek]

Using a relative norm calculation is far slower than using an absolute norm calculation. The first should therefore be avoided if possible. What is needed is a patch that avoids using relative norm calculations when they are not necessary. The problem is well summarized in the following example:

sage: K1.<a1> = CyclotomicField(11)
sage: K2.<a2> = K1.extension(x!^2 - 3)
sage: K3.<a3> = K2.extension(x!^2 + 1)
sage: t=a1+6*a2+a3*a1
sage: %time t.norm()
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.11 s
46593592840125350650995659797233874763776
sage: %time t.norm(QQ)
CPU times: user 2.11 s, sys: 0.01 s, total: 2.12 s
Wall time: 2.23 s
46593592840125350650995659797233874763776

[MvanBeek]

I am working on this patch and it should be online tomorrow

[MvanBeek]

first version of the patch

[johanbosman]

Does this ticket need review, or are you still working on it?

[MvanBeek]

it's ready for review

[davidloeffler]

Please make sure that your patch has a sensible commit message (beginning with the ticket number) and that your Mercurial username includes an email address.

[mstreng]

Aren't ticket numbers added automatically these days? As for hg usernames, David refers to this part of the ~/.hgrc file: (even Gauss has an email address)

[ui]
username = Carl Friedrich Gauss <cfgauss@uni-goettingen.de>

[mstreng]

The patch speeds up the case where the subfield is QQ, but ignores the case where K is a number field isomorphic to QQ, which is more likely to happen in practice, as the subfields method always returns such number fields.

Without patch:

sage: x = var('x')
sage: K1.<a1> = CyclotomicField(11)
sage: K2.<a2> = K1.extension(x^2 - 3)
sage: K3.<a3> = K2.extension(x^2 + 1)
sage: t=a1+6*a2+a3*a1
sage: %time t.norm()
Wall time: 0.08 s
46593592840125350650995659797233874763776
sage: CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
sage: %time t.norm(QQ)
CPU times: user 3.82 s, sys: 0.04 s, total: 3.86 s
Wall time: 3.85 s
46593592840125350650995659797233874763776
sage: K = NumberField(x-1,'a')
sage: %time t.norm(K)
CPU times: user 11.28 s, sys: 0.14 s, total: 11.42 s
Wall time: 11.43 s
46593592840125350650995659797233874763776
sage: K.degree()
1
sage: K is QQ
False

Patch speeds up the second one to match the first, but leaves the third one as it is.