13
$\begingroup$

There are many, many different versions of the Littlewood-Richardson rule: the original characterization via Yamanouchi words, Remmel's version, a description via the Poirier-Reutenauer bialgebra, the Knutson-Tao hive model rule and many more. Any of these rules provides an effective algorithm for computing products of Schur functions. It is known that computing Littlewood-Richardson coefficients is, in general, #P complete.

I am interested in the most computationially efficient Littlewood-Richardson rule. Since any rule will be in #P, for which I am not aware of easy characterizations of run time (please correct me if I'm wrong on this), I suspect any answer to this question would have to be based on experimental evidence. No doubt the various computer algebra systems have coded the various rules, computed a bunch of examples and checked which one was fastest. In one of my graduate courses, we were told the Remmel rule was the easiest, though this was for by hand computations of small examples. At the end of Exercise 2.7.10 of book Symmetric Functions, Schubert Polynomials and Degeneracy Loci, Manivel asserts that the Lascoux-Schutzenberger transition equations (see here) for Schubert polynomials (and hence Stanley symmetric functions) provides the most computationally efficient means of computing the product of Schur functions.

1) What is the (experimentally) most efficient method of computing a single Littlewood-Richardson coefficient?

2) Can anyone confirm or refute Manivel's assertion that the Lascoux-Schutzenberger transition equations are the most efficient rule for computing the product of Schur functions?

$\endgroup$
2
  • 3
    $\begingroup$ To compute say all LR-coeffcients with parameters less than size $k$, there is a nice recursion that hold for the LR-rule for the factorial Schur polynomials, and can therefore be used here as well, see A. Molev and B. Sagan. A Littlewood-Richardson rule for factorial Schur functions. Trans. Amer. Math. Soc., 351(11):4429–4443, 1999. This can be imitated to give a recursion for the Jack polynomial LR-coefficients, for which a combinatorial interpretation is so far unknown. $\endgroup$ Commented Aug 14, 2015 at 20:52
  • 4
    $\begingroup$ For computing all the terms in the expansion of $s_\lambda s_\mu$, one method is to work with a sufficiently large but finite number of variables, express the product as a linear combination of Schur functions with unknown coefficients, write the Schur functions as bialternants (quotients of determinants), and specialize the variables to real numbers sufficiently generically to be able solve the resulting system of linear equations for the unknown coefficients. I believe that John Stembridge uses this technique for some of his SF computations. $\endgroup$ Commented Aug 14, 2015 at 22:27

1 Answer 1

6
$\begingroup$

I can refute Manivel's assertion that the transition equation is the most efficient way to multiply Schur (or Schubert) polynomials. I've implemented this, but later found a faster implementation using my research together with Sottile's Pieri rule for elementary symmetric polynomials.

It's well known that a Schubert polynomial can be expressed in terms of ``elementary symmetric monomials.'' If we require all of the numbers of variables of the elementary symmetric polynomials to be different in the monomial, there's a unique such expression. But this is almost never the most efficient way to express a Schubert polynomial in terms of elementary symmetric polynomials. The most efficient way is as follows. Let $v$ be a permutation, and consider its code: $$c_i(v)=\#\{j>i|v(i)>v(j)\}$$ Recursively we construct a permutation $\mu(v)$ from $v$ such that the code of $\mu$ is weakly decreasing (a partition, padded with $0$'s). Such a permutation is called dominant. If $v$ is already dominant, let $\mu(v)=v$. Otherwise, let $i$ be the maximal integer such that $c_i(v^{-1})<c_{i+1}(v^{-1})$, and define $\mu(v)=\mu(s_iv)$. When this recursion terminates we have a dominant permutation that's $\geq$ $v$ in left weak Bruhat order.

Consider the double Schubert polynomial $$S_{\mu(v)}(x;y)$$ This is a product of factorial elementary symmetric polynomials. We can apply divided differences on the $y$ variables to obtain the double Schubert polynomial $S_v(x;y)$, which is where my research comes in, to find an expression for that. The expression that we result in is a sum of products of factorial elementary symmetric polynomials with messed up $y$ variables. But here we don't care about the $y$ variables, so we set them to $0$ and end up with an expression for $S_v(x)$ in terms of elementary symmetric polynomials. If $v$ is Grassmannian, these elementary symmetric polynomials will all have the same number of variables as $S_v(x)$.

Given this expression, use this to multiply an arbitrary Schubert polynomial $S_u(x)$ by $S_v(x)$ by applying Sottile's Pieri formula in "Pieri's rule for flag manifolds and Schubert polynomials." How does this compare to my transition formula implementation? For comparison, my transition formula implementation in python is always slower than schubmult from lrcalc. That could just be because it's python, and schubmult is written in C, right? There's a case where I applied my research-Pieri formula python implementation and it got the result in 59 seconds. schubmult took 96 minutes to do the same calculation.

Since the problem is $\#P$-complete (actually we don't even know if it's in $\#P$ for the complete flag variety, but at least it's $\#P$-hard) it's unlikely any sort of efficient algorithm exists in the general sense. If a polynomial time algorithm existed, then $P=NP$. I'm not claiming my method is the best either; someone could easily come up with something better, but in a computational complexity sense it will almost certainly never be "fast."

I've gone public with my implementation, including scripts for multiplying double Schubert polynomials in either the same or different sets of variables. https://pypi.org/project/schubmult/. There's a link to the github project on the site.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.