4852 words - 20 pages

A LINEAR-TIME ALGORITHM FOR EVALUATING

SERIES OF SCHUR FUNCTIONS

CY CHAN, VESSELIN DRENSKY, ALAN EDELMAN, AND PLAMEN KOEV

Abstract. We present a new algorithm for computing all Schur functions sλ(x1, x2, . . . , xn)

for all partitions λ of integers not exceeding N in time O(n2K ), where K ≡ #{λ| |λ| ≤ N}

N N

is the number of those partitions.

In particular, this algorithm has optimal complexity for evaluating truncated series of

Schur functions such as the hypergeometric function ...view middle of the document...

The challenge in evaluating (1) involves the evaluation of the Schur function sκ and has

proven extremely challenging primarily since, as a multivariate symmetric polynomial, it has

|κ|

exponential number of terms—O n [4, 8, 11].

Currently, the best algorithm for evaluating (1) is mhg from [11] whose complexity is

2

O(nKN),

2000 Mathematics Subject Classiﬁcation. Primary 05E05. Secondary 65F50; 65T50.

Key words and phrases. Schur functions, Fast Fourier Transforms.

The research of the second author was partially supported by Grant MI-1503/2005 of the Bulgarian

National Science Fund.

The research of the third and fourth authors was supported by NSF Grant DMS–0608306.

1

where KN ≡ #{κ| |κ| ≤ N} is the number of terms in (1).

√

π 2N/3

An estimate of KN is Ramanujan’s asymptotic formula [9, p. 116] KN ∼ O e ,

which is subexponential in N.

In this paper, we present a new algorithm for computing (1) whose complexity is only

2

O(n KN),

2

i.e., it takes only O(n ) per term instead of the O(nKN) cost per term of mhg.

To achieve that complexity, we follow the idea in [11]: The recursive formula [12]

X

|λ|−|µ|

(3) sλ(x , x , . . . , x1 2 n) = sµ(x , x , . . . , x1 2 n−1)xn

µ

allows each Schur function in (1) to be computed at a cost not exceeding O(nKM). The

summation in (3) is over all partitions µ = (µ , . . . , µ1 n−1) such that λ/µ is a horizontal strip,

i.e.,

(4) λ1 ≥ µ1 ≥ λ2 ≥ µ2 ≥ · · · ≥ λn−1 ≥ µn−1 ≥ λn.

In this paper we improve on the result of [11] by observing that (3) represents a vector-

matrix multiplication

(n) (n−1)

(5) s = s · Zn(xn)

(i)

where s is an (appropriately indexed) row-vector of all Schur functions sκ(x , x , . . . , x1 2 i),

|λ|−|µ|

|κ| ≤ N and Zn(xn) ≡ εµ,λxn is a matrix with entries indexed with the pairs of

partitions (µ, λ), with εµ,λ = 1 if λ/µ is a horizontal strip and 0 otherwise.

...

Beat writer's block and start your paper with the best examples