The crucial difference is that I don't use .from_polynomial (which
is kind of broken). Given a univariate polynomial f it is easy to
compute directly the symmetric function
f(x1) f(x2) ... f(xn)
in the monomial basis (this is what my function prod_in_monomial does).
Then the conversion "monomial basis" -> "elementary basis" is fast.
See the attached script that is even shorter and more efficient.
I have no idea what is the polarization, but you can open a new thread
where you explain your problem.
Best
Vincent
Le 21/04/2020 à 12:16, Michael Jung a écrit :
Wow, thanks Vincent. This is awesome! Could you shortly explain what the
crucial difference is here?
On this occasion, may I ask you a slightly off-topic question? Is there an
effective way to compute the polarization of homogeneous polynomials in
Sage?
Best
Michael
Am Dienstag, 21. April 2020 12:08:56 UTC+2 schrieb vdelecroix:
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/5b22ffcb-098f-ec04-4a67-6cbf4552ddda%40gmail.com.
r"""
Fast computation of Todd polynomials.
See
https://groups.google.com/forum/#!topic/sage-devel/Z9YS7Hh146I
"""
def prod_in_monomial(f, n):
Sym_m = SymmetricFunctions(QQ).m()
return Sym_m.sum(prod(f[i] for i in p) * Sym_m[p] for k in range(n) for p in Partitions(k))
def todd(n):
r"""
EXAMPLES::
sage: todd(10)
e[] + 1/2*e[1] + 1/12*e[1, 1] - 1/720*e[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/240*e[2, 2] + 1/480*e[2, 2, 1] + 1/720*e[3, 1] + 1/1440*e[3, 1, 1] - 1/720*e[4] - 1/1440*e[4, 1]
"""
x = polygen(QQ, 'x')
f = ((1 - (-x)._exp_series(n//2 + 1)) // x).inverse_series_trunc(n//2)
return Sym.e()(prod_in_monomial(f, n//2 + 1))
