Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
On 8 May 2014 08:18, Nils Bruin wrote: > On Wednesday, April 30, 2014 1:07:55 AM UTC-7, John Cremona wrote: > >> NO! If f1 and f2 define the same extension field then will >> not be prime, e.g. f1=x^2-2 and f2=x^2-8 over QQ. >> > > you probably mean f1=x^2-2 and f2=y^2-8 in QQ[x,y] . =<1> is > also not prime but that doesn't have much to do which fields the > polynomials define. > You are right, of course! John > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
On Wednesday, April 30, 2014 1:07:55 AM UTC-7, John Cremona wrote: > NO! If f1 and f2 define the same extension field then will > not be prime, e.g. f1=x^2-2 and f2=x^2-8 over QQ. > you probably mean f1=x^2-2 and f2=y^2-8 in QQ[x,y] . =<1> is also not prime but that doesn't have much to do which fields the polynomials define. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
On 30 April 2014 10:09, François Colas wrote: > What I am trying to do is to use the prime factorisation of m to compute in > another field than Q(zeta_m) (i.e. Q(zeta_m1, zeta_m2, ..., zeta_ml)) or > Q[x]/ (i.e. Q[x1, ..., xl] / ) because I need m > between 1000 and 1 and actually sage is not able to do this. The idea is > to have a faster arithmetic. > > In fact I should have written: > > Idl = [cyclotomic_polynomial(p^e, 'q'+str(i)) for (i, (p, e)) in > enumerate(factor(m))] > > In this case 2 cyclotomic polynomials never define the same extension field > right? > Yes, that is certainly true. In fact if m and n are distinct positive integers then Phi_m and Phi_n generate the unit ideal in Z[X] so they are coprime in this stronger sense: their reultant is 1, not just a nonzero constant). Sometimes it is possible to do computations in Z[X] / (X^m-1) which should be cheaper. Of course this is not the rings you actually want, as it is the direct sum of the d'th cyclotomic rings for all d|m, but any equality in this ring is also an inequality in the m'th cyclotomic ring as that is a quotient of this. John > > PS: Phi_m = cyclotomic_polynomial(m) > > Le mercredi 30 avril 2014 10:07:55 UTC+2, John Cremona a écrit : >> >> On 29 April 2014 19:23, Martin Albrecht wrote: >> > 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 = with all f_i irreducible >> > and >> > \intersect = \empty then I is a prime ideal? >> >> NO! If f1 and f2 define the same extension field then will >> not be prime, e.g. f1=x^2-2 and f2=x^2-8 over QQ. >> >> John >> >> > >> >> 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) >> > >> > 41.7610.4401.7610.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 > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
What I am trying to do is to use the prime factorisation of m to compute in another field than Q(zeta_m) (i.e. Q(zeta_m1, zeta_m2, ..., zeta_ml)) or Q[x]/ (i.e. Q[x1, ..., xl] / ) because I need m between 1000 and 1 and actually sage is not able to do this. The idea is to have a faster arithmetic. In fact I should have written: Idl = [cyclotomic_polynomial(p^e, 'q'+str(i)) for (i, (p, e)) in enumerate( factor(m))] In this case 2 cyclotomic polynomials never define the same extension field right? PS: Phi_m = cyclotomic_polynomial(m) Le mercredi 30 avril 2014 10:07:55 UTC+2, John Cremona a écrit : > > On 29 April 2014 19:23, Martin Albrecht > > > wrote: > > 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 = with all f_i irreducible > and > > \intersect = \empty then I is a prime ideal? > > NO! If f1 and f2 define the same extension field then will > not be prime, e.g. f1=x^2-2 and f2=x^2-8 over QQ. > > John > > > > >> 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) > > > > 41.7610.4401.7610.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 > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
On 29 April 2014 19:23, Martin Albrecht wrote: > 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 = with all f_i irreducible and > \intersect = \empty then I is a prime ideal? NO! If f1 and f2 define the same extension field then will not be prime, e.g. f1=x^2-2 and f2=x^2-8 over QQ. John > >> 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) > > 41.7610.4401.7610.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 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
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 = with all f_i irreducible and \intersect = \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) 41.7610.4401.7610.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.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
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 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 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... Le lundi 28 avril 2014 21:54:33 UTC+2, Martin Albrecht a écrit : > > I just tried to run: > > sage: m = random_prime(10^5) > sage: K. = CyclotomicField(m) > > and I ran out of RAM! Doing a smaller example: > > sage: m = random_prime(10^4) > sage: %prun K. = CyclotomicField(m) > > puts > > sage.rings.number_field.number_field_morphisms.create_embedding_from_approx > > > as the most expensive function call. Continuing to: > > sage: m = random_prime(2*10^3) > sage: K. = CyclotomicField(m) > sage: %prun K.ring_of_integers() > > puts > > sage.matrix.matrix_integer_dense.Matrix_integer_dense._solve_right_nonsingular_square > > > > as the most expensive function call, which would imply John's assumption > is > right. > > Cheers, > Martin > > On Tuesday 15 Apr 2014 13:04:27 François Colas wrote: > > Hi Vincent, > > > > In fact that's exactly what I want to do! > > > > But I am using morphisms: > > > > m = ZZ(int(random()*10^5+1)) > > > > R. = NumberField(cyclotomic_polynomial(m)) > > > > Idl = [] > > > > for (p, e) in factor(m): > > Idl.append(cyclotomic_polynomial(p)) > > > > K = NumberField(Idl, 'k') > > > > F = Hom(R, K) > > > > f = F([...]) > > > > Unfortunately I also need K with big m for cryptographic purpose... :'( > > > > Note that even if you have 3 cyclotomic polynomials in Idl (e.g. 11, 13, > > 17) it's always slow. > > > > Le mardi 15 avril 2014 18:48:11 UTC+2, vdelecroix a écrit : > > > Hi François, > > > > > > Might be related to the ticket #16116 on trac > > > (http://trac.sagemath.org/ticket/16116). Note that for performance, > it > > > is possible to use multivariate polynomials as described in the > > > ticket. > > > > > > Best > > > Vincent > > > > > > 2014-04-15 18:30 UTC+02:00, François Colas >: > > > > Hello group, > > > > > > > > I am playing with quotient ring of Z over cyclotomic polynomial but > it > > > > > > is > > > > > > > strangely slow: > > > > > > > > sage: m = random_prime(10^4); m > > > > 2437 > > > > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > > > CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s > > > > Wall time: 2.50 s > > > > > > > > cyclotomic_polynomial(m) is created instantly whatever the size of m > but > > > > the quotient becomes very long: > > > > > > > > sage: m = random_prime(10^5); m > > > > 16231 > > > > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > > > CPU times: user 217.82 s, sys: 0.00 s, total: 217.82 s > > > > Wall time: 217.65 s > > > > > > > > > > > > I am using Sage Version 6.1.1, does anyone could confirm this > problem? > > > > > > Groups > > > > > > > "sage-devel" group. > > > > To unsubscribe from this group and stop receiving emails from it, > send > > > > > > an > > > > > > > email to sage-devel+...@googlegroups.com . > > > > To post to this group, send email to > > > > sage-...@googlegroups.com. > > > > > > > > Visit this group at http://groups.google.com/group/sage-devel. > > > > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
I just tried to run: sage: m = random_prime(10^5) sage: K. = CyclotomicField(m) and I ran out of RAM! Doing a smaller example: sage: m = random_prime(10^4) sage: %prun K. = CyclotomicField(m) puts sage.rings.number_field.number_field_morphisms.create_embedding_from_approx as the most expensive function call. Continuing to: sage: m = random_prime(2*10^3) sage: K. = CyclotomicField(m) sage: %prun K.ring_of_integers() puts sage.matrix.matrix_integer_dense.Matrix_integer_dense._solve_right_nonsingular_square as the most expensive function call, which would imply John's assumption is right. Cheers, Martin On Tuesday 15 Apr 2014 13:04:27 François Colas wrote: > Hi Vincent, > > In fact that's exactly what I want to do! > > But I am using morphisms: > > m = ZZ(int(random()*10^5+1)) > > R. = NumberField(cyclotomic_polynomial(m)) > > Idl = [] > > for (p, e) in factor(m): > Idl.append(cyclotomic_polynomial(p)) > > K = NumberField(Idl, 'k') > > F = Hom(R, K) > > f = F([...]) > > Unfortunately I also need K with big m for cryptographic purpose... :'( > > Note that even if you have 3 cyclotomic polynomials in Idl (e.g. 11, 13, > 17) it's always slow. > > Le mardi 15 avril 2014 18:48:11 UTC+2, vdelecroix a écrit : > > Hi François, > > > > Might be related to the ticket #16116 on trac > > (http://trac.sagemath.org/ticket/16116). Note that for performance, it > > is possible to use multivariate polynomials as described in the > > ticket. > > > > Best > > Vincent > > > > 2014-04-15 18:30 UTC+02:00, François Colas >: > > > Hello group, > > > > > > I am playing with quotient ring of Z over cyclotomic polynomial but it > > > > is > > > > > strangely slow: > > > > > > sage: m = random_prime(10^4); m > > > 2437 > > > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > > CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s > > > Wall time: 2.50 s > > > > > > cyclotomic_polynomial(m) is created instantly whatever the size of m but > > > the quotient becomes very long: > > > > > > sage: m = random_prime(10^5); m > > > 16231 > > > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > > CPU times: user 217.82 s, sys: 0.00 s, total: 217.82 s > > > Wall time: 217.65 s > > > > > > > > > I am using Sage Version 6.1.1, does anyone could confirm this problem? > > > > Groups > > > > > "sage-devel" group. > > > To unsubscribe from this group and stop receiving emails from it, send > > > > an > > > > > email to sage-devel+...@googlegroups.com . > > > To post to this group, send email to > > > sage-...@googlegroups.com. > > > > > > Visit this group at http://groups.google.com/group/sage-devel. > > > For more options, visit https://groups.google.com/d/optout. signature.asc Description: This is a digitally signed message part.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
Hi Vincent, In fact that's exactly what I want to do! But I am using morphisms: m = ZZ(int(random()*10^5+1)) R. = NumberField(cyclotomic_polynomial(m)) Idl = [] for (p, e) in factor(m): Idl.append(cyclotomic_polynomial(p)) K = NumberField(Idl, 'k') F = Hom(R, K) f = F([...]) Unfortunately I also need K with big m for cryptographic purpose... :'( Note that even if you have 3 cyclotomic polynomials in Idl (e.g. 11, 13, 17) it's always slow. Le mardi 15 avril 2014 18:48:11 UTC+2, vdelecroix a écrit : > > Hi François, > > Might be related to the ticket #16116 on trac > (http://trac.sagemath.org/ticket/16116). Note that for performance, it > is possible to use multivariate polynomials as described in the > ticket. > > Best > Vincent > > 2014-04-15 18:30 UTC+02:00, François Colas >: > > > Hello group, > > > > I am playing with quotient ring of Z over cyclotomic polynomial but it > is > > strangely slow: > > > > sage: m = random_prime(10^4); m > > 2437 > > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s > > Wall time: 2.50 s > > > > cyclotomic_polynomial(m) is created instantly whatever the size of m but > > the quotient becomes very long: > > > > sage: m = random_prime(10^5); m > > 16231 > > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > CPU times: user 217.82 s, sys: 0.00 s, total: 217.82 s > > Wall time: 217.65 s > > > > > > I am using Sage Version 6.1.1, does anyone could confirm this problem? > > > > -- > > You received this message because you are subscribed to the Google > Groups > > "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an > > email to sage-devel+...@googlegroups.com . > > To post to this group, send email to > > sage-...@googlegroups.com. > > > Visit this group at http://groups.google.com/group/sage-devel. > > For more options, visit https://groups.google.com/d/optout. > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
I wa going to write: "Is there any reason not to do sage: m=random_prime(10^5) sage: K. = CyclotomicField(m) sage: R = K.ring_of_integers() " but I tried it and the last line is (much too) slow, which probably means that a generic algorithm is being used even though one knows that R = Z[r]. John On 15 April 2014 17:48, Vincent Delecroix <20100.delecr...@gmail.com> wrote: > Hi François, > > Might be related to the ticket #16116 on trac > (http://trac.sagemath.org/ticket/16116). Note that for performance, it > is possible to use multivariate polynomials as described in the > ticket. > > Best > Vincent > > 2014-04-15 18:30 UTC+02:00, François Colas : >> Hello group, >> >> I am playing with quotient ring of Z over cyclotomic polynomial but it is >> strangely slow: >> >> sage: m = random_prime(10^4); m >> 2437 >> sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) >> CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s >> Wall time: 2.50 s >> >> cyclotomic_polynomial(m) is created instantly whatever the size of m but >> the quotient becomes very long: >> >> sage: m = random_prime(10^5); m >> 16231 >> sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) >> CPU times: user 217.82 s, sys: 0.00 s, total: 217.82 s >> Wall time: 217.65 s >> >> >> I am using Sage Version 6.1.1, does anyone could confirm this problem? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sage-devel" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to sage-devel+unsubscr...@googlegroups.com. >> To post to this group, send email to sage-devel@googlegroups.com. >> Visit this group at http://groups.google.com/group/sage-devel. >> For more options, visit https://groups.google.com/d/optout. >> > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Quotient ring over cyclotomic polynomial very slow
Hi François, Might be related to the ticket #16116 on trac (http://trac.sagemath.org/ticket/16116). Note that for performance, it is possible to use multivariate polynomials as described in the ticket. Best Vincent 2014-04-15 18:30 UTC+02:00, François Colas : > Hello group, > > I am playing with quotient ring of Z over cyclotomic polynomial but it is > strangely slow: > > sage: m = random_prime(10^4); m > 2437 > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s > Wall time: 2.50 s > > cyclotomic_polynomial(m) is created instantly whatever the size of m but > the quotient becomes very long: > > sage: m = random_prime(10^5); m > 16231 > sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) > CPU times: user 217.82 s, sys: 0.00 s, total: 217.82 s > Wall time: 217.65 s > > > I am using Sage Version 6.1.1, does anyone could confirm this problem? > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Quotient ring over cyclotomic polynomial very slow
Hello group, I am playing with quotient ring of Z over cyclotomic polynomial but it is strangely slow: sage: m = random_prime(10^4); m 2437 sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s Wall time: 2.50 s cyclotomic_polynomial(m) is created instantly whatever the size of m but the quotient becomes very long: sage: m = random_prime(10^5); m 16231 sage: %time R. = ZZ['z'].quotient(cyclotomic_polynomial(m)) CPU times: user 217.82 s, sys: 0.00 s, total: 217.82 s Wall time: 217.65 s I am using Sage Version 6.1.1, does anyone could confirm this problem? -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
