Hi Michael,
Indeed, Sym.e().from_polynomial(P(seq_taylor)) is taking ages!
Using the function from the attached you can compute todd(12)
is computed in 18ms :-)
sage: todd(12)
e[] + 1/2*e[1] + 1/12*e[1, 1] - 1/720*e[1, 1, 1, 1] + 1/30240*e[1, 1, 1,
1, 1, 1] + 1/12*e[2] + 1/24*e[2, 1] + 1/180*e[2, 1, 1] - 1/1440*e[2, 1,
1, 1] - 1/5040*e[2, 1, 1, 1, 1] + 1/240*e[2, 2] + 1/480*e[2, 2, 1] +
11/60480*e[2, 2, 1, 1] + 1/6048*e[2, 2, 2] + 1/720*e[3, 1] + 1/1440*e[3,
1, 1] + 1/12096*e[3, 1, 1, 1] + 11/60480*e[3, 2, 1] - 1/60480*e[3, 3] -
1/720*e[4] - 1/1440*e[4, 1] - 1/12096*e[4, 1, 1] - 1/6720*e[4, 2] -
1/30240*e[5, 1] + 1/30240*e[6]
sage: %time t = todd(12)
CPU times: user 18.5 ms, sys: 112 µs, total: 18.6 ms
Wall time: 18.1 ms
Best
Vincent
Le 21/04/2020 à 11:20, Michael Jung a écrit :
Hi Travis,
yes, that is exactly what I want to do. I want to compute multiplicative
sequences from arbitrary formal power series, which has use in geometry.
However, in that paper, they compare two different approaches. And even the
general (slower) approach (elimination) seems to be faster than Sage's
algorithm. Let me show you what I have tried so far.
sage: n = 12
sage: f = x / (1-exp(-x))
sage: Sym = SymmetricFunctions(QQ)
sage: P = PolynomialRing(QQ, 'x', n)
sage: seq = prod(f.subs({f.default_variable(): var}) for var in P.gens())
sage: inp = [(var, 0) for var in P.gens()]
sage: seq_taylor = seq.taylor(*inp, n // 2)
sage: Sym.e().from_polynomial(P(seq_taylor))
This code is to compute Todd numbers up the the 6th degree and takes hours
of computation. Did I do use symmetric functions wrong here?
Regards
Michael
Am Dienstag, 21. April 2020 02:44:19 UTC+2 schrieb Travis Scrimshaw:
Hi Michael,
Perhaps I am misunderstanding what you are trying to do. I was thinking
you were starting with a polynomial in, say, R.<x,y,z> that you know is
symmetric and you want its expression in expressed in terms of elementary
symmetric functions. Whereas in that paper, they seem to be computing very
specific symmetric polynomials by applying the constraints of the geometry.
However, there are some specialized change of bases that could be done,
such as p -> e using the contents of section 2, that could be faster
(although in that case, Sage seems to be pretty fast). Or have I
misunderstood something?
Thanks,
Travis
On Tuesday, April 21, 2020 at 10:00:35 AM UTC+10, Michael Jung wrote:
Thanks for your reply Travis.
Here are different computations compared, which take milliseonds up to
seconds: https://orbilu.uni.lu/bitstream/10993/21949/2/ChernLib.pdf
In contrast, doing a similar computation with the same polynomials using
`SymmetricFunctions` takes hours.
However, I think this is a special case they consider, which makes the
computation probably faster.
Kind regards
Michael
Am Dienstag, 21. April 2020 01:52:43 UTC+2 schrieb Travis Scrimshaw:
Hi Michael,
The process is to take a polynomial, convert it to the monomial sym
func basis, then to the elementary basis (which is outsourced to
symmetrica). Do you have some references for these efficient algorithms to
convert a polynomial directly to the elementary basis?
Best,
Travis
On Tuesday, April 21, 2020 at 3:18:37 AM UTC+10, Michael Jung wrote:
Dear Sage developers,
currently, I am working on an alternative algorithm to compute
characteristic forms. I hope to gain a speed-up here. For this reason, I
need to express symmetric polynomials in terms of elementary symmetric
functions. At the moment, I am playing around with `SymmetricFunctions`.
However, the implemented algorithm seems to be very slow. I know that there
are quite efficient algorithms out there, but are they accessible in Sage?
Thanks for your help and best wishes
Michael
--
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 view this discussion on the web visit
https://groups.google.com/d/msgid/sage-devel/dd4afbf4-fce8-2be0-fc4c-57113de5de04%40gmail.com.
r"""
Fast computation of Todd polynomials.
See
https://groups.google.com/forum/#!topic/sage-devel/Z9YS7Hh146I
"""
def prod_in_monomial(f, n):
r"""
given a univariate f = 1 + ... compute the decomposition
f(x1) f(x2) ... f(xn)
in the monomial basis up to degree n.
"""
Sym = SymmetricFunctions(QQ).m()
f = f.truncate(n)
res = Sym.zero()
for k in range(n):
for p in Partitions(k):
# compute the coefficient of x0^(p[0]-1) x1^(p[1]-1) ... x(n-1)^(p[n-1]-1)
res += prod(f[i] for i in p) * Sym[p]
return res
def todd(n):
R = PowerSeriesRing(QQ, 'x')
x = R.gen()
f = x / (1 - (-x).exp()) + O(x**(n//2 + 1))
return Sym.e()(prod_in_monomial(f, n//2 + 1))
