Accurate and efficient evaluation of Schur and Jack functions

Demmel, James; Koev, Plamen

doi:10.1090/S0025-5718-05-01780-1

Accurate and efficient evaluation of Schur and Jack functions
HTML articles powered by AMS MathViewer

by James Demmel and Plamen Koev;

Math. Comp. 75 (2006), 223-239

DOI: https://doi.org/10.1090/S0025-5718-05-01780-1

Published electronically: August 31, 2005

PDF | Request permission

Abstract:

We present new algorithms for computing the values of the Schur $s_\lambda (x_1,x_2,\ldots ,x_n)$ and Jack $J_\lambda ^\alpha (x_1,x_2,\ldots ,x_n)$ functions in floating point arithmetic. These algorithms deliver guaranteed high relative accuracy for positive data ($x_i, \alpha >0$) and run in time that is only linear in $n$.

References

P.-A. Absil, A. Edelman, and P. Koev, On the largest principal angle between random subspaces, http://www.csit.fsu.edu/~absil/Publi/RandomSubspaces.htm, Submitted to Linear Algebra Appl..
ANSI/IEEE, New York, IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 ed., 1985.
Åke Björck and Victor Pereyra, Solution of Vandermonde systems of equations, Math. Comp. 24 (1970), 893–903. MR 290541, DOI 10.1090/S0025-5718-1970-0290541-1
Ronald W. Butler and Andrew T. A. Wood, Laplace approximations for hypergeometric functions with matrix argument, Ann. Statist. 30 (2002), no. 4, 1155–1177. MR 1926172, DOI 10.1214/aos/1031689021
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 2nd ed., MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001. MR 1848805
James Demmel, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 562–580. MR 1742810, DOI 10.1137/S0895479897328716
James Demmel and Plamen Koev, Necessary and sufficient conditions for accurate and efficient rational function evaluation and factorizations of rational matrices, Structured matrices in mathematics, computer science, and engineering, II (Boulder, CO, 1999) Contemp. Math., vol. 281, Amer. Math. Soc., Providence, RI, 2001, pp. 117–143. MR 1855508, DOI 10.1090/conm/281/04652
—, The accurate and efficient solution of a totally positive generalized Vandermonde linear system. SIAM J. Matrix Anal. Appl., 27 (2005), no. 1, 142–152.
I. Dumitriu, A. Edelman, and F. Shuman, A Maple Package for Computing Multivariate Orthogonal Polynomials, http://www.math.berkeley.edu/~dumitriu.
A. Edelman and B. Sutton, Tails of condition number distributions, submitted to SIAM J. Matrix Anal. Appl.
Walter Gautschi, How (un)stable are Vandermonde systems?, Asymptotic and computational analysis (Winnipeg, MB, 1989) Lecture Notes in Pure and Appl. Math., vol. 124, Dekker, New York, 1990, pp. 193–210. MR 1052434
R. Gutiérrez, J. Rodriguez, and A. J. Sáez, Approximation of hypergeometric functions with matricial argument through their development in series of zonal polynomials, Electron. Trans. Numer. Anal. 11 (2000), 121–130. MR 1799027
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Chelsea Publishing Co., New York, 1959. MR 106147
Nicholas J. Higham, Stability analysis of algorithms for solving confluent Vandermonde-like systems, SIAM J. Matrix Anal. Appl. 11 (1990), no. 1, 23–41. MR 1032215, DOI 10.1137/0611002
Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
Gordon James and Adalbert Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, MA, 1981. With a foreword by P. M. Cohn; With an introduction by Gilbert de B. Robinson. MR 644144
Friedrich Knop and Siddhartha Sahi, A recursion and a combinatorial formula for Jack polynomials, Invent. Math. 128 (1997), no. 1, 9–22. MR 1437493, DOI 10.1007/s002220050134
P. Koev, http://www-math.mit.edu/~plamen.
P. Koev, Accurate eigenvalues and SVDs of totally nonnegative matrices, SIAM J. Matrix Anal. Appl., 27 (2005), no. 1, 1–23.
P. Koev and A. Edelman, The efficient evaluation of the hypergeometric function of matrix argument, Math. Comp., to appear.
I. G. Macdonald, Schur functions: theme and variations, Séminaire Lotharingien de Combinatoire (Saint-Nabor, 1992) Publ. Inst. Rech. Math. Av., vol. 498, Univ. Louis Pasteur, Strasbourg, 1992, pp. 5–39. MR 1308728, DOI 10.1108/EUM0000000002757
I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
The MathWorks, Inc., Natick, MA, MATLAB reference guide, 1992.
M. Monagan, K. Geddes, K. Heal, G. Labahn, and S. Vorkoetter, Maple V Programming guide for release 5, Springer-Verlag, 1997.
Robb J. Muirhead, Aspects of multivariate statistical theory, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1982. MR 652932, DOI 10.1002/9780470316559
D. Priest, Algorithms for arbitrary precision floating point arithmetic, Proceedings of the 10th Symposium on Computer Arithmetic (Grenoble, France) (P. Kornerup and D. Matula, eds.), IEEE Computer Society Press, June 26-28 1991, pp. 132–145.
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
Richard P. Stanley, Some combinatorial properties of Jack symmetric functions, Adv. Math. 77 (1989), no. 1, 76–115. MR 1014073, DOI 10.1016/0001-8708(89)90015-7
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
H. Van de Vel, Numerical treatment of a generalized Vandermonde system of equations, Linear Algebra Appl. 17 (1977), no. 2, 149–179. MR 474757, DOI 10.1016/0024-3795(77)90035-0