On Monday 28 Apr 2014 14:57:59 François Colas wrote: > Hi Martin, > > Here is two examples using multivariate quotients and extension fields > which should be faster than computing CyclotomicField(m) or > NumberField(cyclotomic(m), 'r') : > > m = 3*5*7 > pi = prime_factors(m) > Qi = PolynomialRing(QQ, len(pi), 'q') > Idl = [cyclotomic_polynomial(p, 'q'+str(i)) for (i, p) in enumerate(pi)] > K = Qi.quo(Idl, 'k') > %time K.fraction_field() > CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s > Wall time: 0.10 s
Okay, this one does pretty much nothing as far as I can tell except for
checking that Idl is prime. This check could/should be specialised for this
type of input.
Am I right in assuming that I = <f_1, ..., f_m> with all f_i irreducible and
<f_i> \intersect <f_j> = \empty then I is a prime ideal?
> and with NumberField:
>
> m = 3*5*7
> pi = prime_factors(m)
> Idl = [cyclotomic_polynomial(p) for p in pi]
> %time NumberField(Idl, 'k', check=False)
> CPU times: user 2.30 s, sys: 0.01 s, total: 2.31 s
> Wall time: 2.30 s
Running
sage: %prun NumberField(Idl, 'k', check=False)
4 1.761 0.440 1.761 0.440
number_field_rel.py:1034(_rnfeltreltoabs)
this is because we're building a tower of number fields:
def NumberFieldTower(v, names, check=True, embeddings=None):
if len(v) == 0:
return QQ
if len(v) == 1:
return NumberField(v[0], names=names, embedding=embeddings[0])
f = v[0]
w = NumberFieldTower(v[1:], names=names[1:], embeddings=embeddings[1:])
if isinstance(f, polynomial_element.Polynomial):
var = f.variable_name()
else:
var = 'x'
name = names[0]
R = w[var] # polynomial ring
f = R(f)
i = 0
sep = chr(ord(name[0]) + 1)
return w.extension(f, name, check=check, embedding=embeddings[0])
The last line of this code in number_field.py consumes all the time. I don't
know what could be done here.
> Now try to play with prime factors in m (e.g. m = 5*7*11 or m = 7*11*13),
> it becomes uncomputable quickly with both...
Cheers,
Martin
signature.asc
Description: This is a digitally signed message part.
