Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Accurate and efficient evaluation of Schur and Jack functions

Authors: James Demmel and Plamen Koev
Journal: Math. Comp. 75 (2006), 223-239
MSC (2000): Primary 65G50; Secondary 05E05
Published electronically: August 31, 2005
MathSciNet review: 2176397
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. P.-A. Absil, A. Edelman, and P. Koev, On the largest principal angle between random subspaces,, Submitted to Linear Algebra Appl..
  • 2. ANSI/IEEE, New York, IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 ed., 1985.
  • 3. Ȧke Björck and Victor Pereyra, Solution of Vandermonde systems of equations, Math. Comp. 24 (1970), 893–903. MR 0290541, 10.1090/S0025-5718-1970-0290541-1
  • 4. 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, 10.1214/aos/1031689021
  • 5. 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
  • 6. James Demmel, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 562–580. MR 1742810, 10.1137/S0895479897328716
  • 7. 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, 10.1090/conm/281/04652
  • 8. -, The accurate and efficient solution of a totally positive generalized Vandermonde linear system. SIAM J. Matrix Anal. Appl., 27 (2005), no. 1, 142-152.
  • 9. I. Dumitriu, A. Edelman, and F. Shuman, A Maple Package for Computing Multivariate Orthogonal Polynomials,
  • 10. A. Edelman and B. Sutton, Tails of condition number distributions, submitted to SIAM J. Matrix Anal. Appl.
  • 11. 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
  • 12. 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 (electronic). MR 1799027
  • 13. G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work., Chelsea Publishing Company, New York, 1959. MR 0106147
  • 14. 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, 10.1137/0611002
  • 15. Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606
  • 16. 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, Mass., 1981. With a foreword by P. M. Cohn; With an introduction by Gilbert de B. Robinson. MR 644144
  • 17. Friedrich Knop and Siddhartha Sahi, A recursion and a combinatorial formula for Jack polynomials, Invent. Math. 128 (1997), no. 1, 9–22. MR 1437493, 10.1007/s002220050134
  • 18. P. Koev,
  • 19. P. Koev, Accurate eigenvalues and SVDs of totally nonnegative matrices, SIAM J. Matrix Anal. Appl., 27 (2005), no. 1, 1-23.
  • 20. P. Koev and A. Edelman, The efficient evaluation of the hypergeometric function of matrix argument, Math. Comp., to appear.
  • 21. 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, 10.1108/EUM0000000002757
  • 22. 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
  • 23. The MathWorks, Inc., Natick, MA, MATLAB reference guide, 1992.
  • 24. M. Monagan, K. Geddes, K. Heal, G. Labahn, and S. Vorkoetter, Maple V Programming guide for release 5, Springer-Verlag, 1997.
  • 25. Robb J. Muirhead, Aspects of multivariate statistical theory, John Wiley & Sons, Inc., New York, 1982. Wiley Series in Probability and Mathematical Statistics. MR 652932
  • 26. 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.
  • 27. A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 0292344
  • 28. Richard P. Stanley, Some combinatorial properties of Jack symmetric functions, Adv. Math. 77 (1989), no. 1, 76–115. MR 1014073, 10.1016/0001-8708(89)90015-7
  • 29. 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
  • 30. H. Van de Vel, Numerical treatment of a generalized Vandermonde system of equations, Linear Algebra and Appl. 17 (1977), no. 2, 149–179. MR 0474757

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65G50, 05E05

Retrieve articles in all journals with MSC (2000): 65G50, 05E05

Additional Information

James Demmel
Affiliation: Department of Mathematics and Computer Science Division, University of California, Berkeley, California 94720

Plamen Koev
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Keywords: Schur function, Jack function, zonal polynomial, high relative accuracy
Received by editor(s): March 9, 2004
Received by editor(s) in revised form: October 14, 2004
Published electronically: August 31, 2005
Additional Notes: This material is based in part upon work supported by the LLNL Memorandum Agreement No. B504962 under DOE Contract No. W-7405-ENG-48, DOE Grants No. DE-FG03-94ER25219, DE-FC03-98ER25351 and DE-FC02-01ER25478, NSF Grant No. ASC-9813362, and Cooperative Agreement No. ACI-9619020.
This work was partially supported by National Science Foundation Grant No. DMS-0314286.
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.