Efficient algorithm to express symmetric polynomial in terms of elementary ones

[Michael Jung]

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

[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

[Michael Jung]

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

[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

[Michael Jung]

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

[Vincent Delecroix]

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

[Michael Jung]

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

[Vincent Delecroix]

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

[Michael Jung]

This is awesome! Thank you very much, that was really helpful.

Soon, I will open another thread about polarization.

Best
Michael

--
Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft.
https://www.avast.com/antivirus

[Markus Wageringel]

The bottleneck in `from_polynomial` is the check to test whether the input is actually a symmetric polynomial. If you disable the check, the computation is moderately fast, although not quite as fast as Vincent's code.

Sym.e().from_polynomial(P(seq_taylor), check=False)

[Nils Bruin]

On Tuesday, April 21, 2020 at 10:08:27 AM UTC-7, Markus Wageringel wrote:

The bottleneck in `from_polynomial` is the check to test whether the input is actually a symmetric polynomial. If you disable the check, the computation is moderately fast, although not quite as fast as Vincent's code.

Sym.e().from_polynomial(P(seq_taylor), check=False)

That's quite a horrible check then! All you'd need to check is that f(x2,x1,x3,...,xn) and f(x2,x3,...,xn,x1) are both equal to f. Perhaps it's worth changing the check. The super-complicated procedure implemented now (expand the representation as polynomial in the symmetric functions back into a polynomial in the original variables) can then be relegated to a doctest.

[Travis Scrimshaw]

The bottleneck in `from_polynomial` is the check to test whether the input is actually a symmetric polynomial. If you disable the check, the computation is moderately fast, although not quite as fast as Vincent's code.

Sym.e().from_polynomial(P(seq_taylor), check=False)

That's quite a horrible check then! All you'd need to check is that f(x2,x1,x3,...,xn) and f(x2,x3,...,xn,x1) are both equal to f. Perhaps it's worth changing the check. The super-complicated procedure implemented now (expand the representation as polynomial in the symmetric functions back into a polynomial in the original variables) can then be relegated to a doctest.

+1

[Vincent Delecroix]

I think that it would be good to implement this directly of the level of
multivariate polynomials. I opened

https://trac.sagemath.org/ticket/29553

Vincent

[Vincent Delecroix]

Le 23/04/2020 à 12:04, Vincent Delecroix a écrit :> I think that it

would be good to implement this directly of the level of
> multivariate polynomials. I opened
>
>  https://trac.sagemath.org/ticket/29553

Ready for review.

[Nils Bruin]

On Thursday, April 23, 2020 at 3:04:46 AM UTC-7, vdelecroix wrote:

I think that it would be good to implement this directly of the level of
multivariate polynomials. I opened

What would the uptake of such a method be? If I needed to test if a polynomial is symmetric, I would probably end up rolling my own because:

 - I wouldn't know or expect such a method to exist on symmetric polynomials

 - I wouldn't know what the particular conditions and assumptions on the input would be (and whether the author silently had different definitions in mind than I had).

Because it's so easy to program myself, I would probably decide that's faster than figuring out if the library version is appropriate (if I knew if it existed in the first place).

In terms of use: I think it's very rare in a computational setting to want to know if a polynomial is symmetric and not want it expressed in (elementary) symmetric polynomials. That's a routine I'd look for -- although surprisingly, this is something that routinely gets done poorly in computer algebra systems (including magma!), so I'd probably end up implementing elimination anyway.

(in this case, it's clear the code is needed in at least one place of the library, so it's not really a loss to put it somewhere, but for code maintainability, I'd keep it closer to where it's used and then perhaps refactor if it shows the demand is there to have it in a more accessible spot)

[Vincent Delecroix]

I agree that if you have a symmetric polynomial at hand you most
probably don't want it expanded (or you are probably doing something
wrong).

But first of all, to make it fast there is no other option than
making it at the level of polynomials themselves (and even then
the generic version it is quite slow because I believe conversion
back and forth between Singular and Sage). Secondly, as a developer,
if I am looking whether such feature is implemented I would never
look into sage/combinat/sf/monomial.py. To my mind, there is more
risk of duplication by implementing it close to its usage rather
than close to the data structure it concerns. And finally, I
implemented the latter in ticket #29553.

[Travis Scrimshaw]

Also, I feel there should be an easy-to-find redirect function in the symmetric function code (IIRC in sfa.py would be the most natural spot), which would tell you to look in the corresponding polynomial code. My natural place to put such checks would be in the polynomial code given that it could take advantage of the specialized implements as Vincent said.

Best,
Travis

[Dima Pasechnik]

On Fri, Apr 24, 2020 at 12:53 AM Nils Bruin <nbr...@sfu.ca> wrote:
>
> On Thursday, April 23, 2020 at 3:04:46 AM UTC-7, vdelecroix wrote:
>>
>>
>> I think that it would be good to implement this directly of the level of
>> multivariate polynomials. I opened
>
>
> What would the uptake of such a method be? If I needed to test if a polynomial is symmetric, I would probably end up rolling my own because:
> - I wouldn't know or expect such a method to exist on symmetric polynomials
> - I wouldn't know what the particular conditions and assumptions on the input would be (and whether the author silently had different definitions in mind than I had).
> Because it's so easy to program myself, I would probably decide that's faster than figuring out if the library version is appropriate (if I knew if it existed in the first place).

A natural function to have in the library is to compute the image of a
polynomial under a linear transformation.
And based on it, a function to compute the orbit of a polynomial under
a group G generated by a finite number of the latter.

E.g. GAP has the one for permutations (if you like, permutation matrices) only

41.2-13 OnIndeterminates

‣ OnIndeterminates( poly, perm )
──────────────────────────────────────────────────────────────────────────────────────────────────────
function

A permutation perm acts on the multivariate polynomial poly by
permuting the indeterminates as it permutes points.

And it can be used as an "action" in their general machinery for
computing orbits.

>
> In terms of use: I think it's very rare in a computational setting to want to know if a polynomial is symmetric and not want it expressed in (elementary) symmetric polynomials. That's a routine I'd look for -- although surprisingly, this is something that routinely gets done poorly in computer algebra systems (including magma!), so I'd probably end up implementing elimination anyway.

I think in a domain like computational group theory and computational
invariant theory (and practice :-)) is is not rare at all.
I did such computations many times, mostly for various extremal
combinatorics problems.


Dima

>
> (in this case, it's clear the code is needed in at least one place of the library, so it's not really a loss to put it somewhere, but for code maintainability, I'd keep it closer to where it's used and then perhaps refactor if it shows the demand is there to have it in a more accessible spot)
>

> --
> 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 view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/f8462d8f-7dc9-4797-84e4-4f5f131ad367%40googlegroups.com.