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
DOI: https://doi.org/10.1090/S0025-5718-05-01780-1
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, http://www.csit.fsu.edu/~absil/Publi/RandomSubspaces.htm, Submitted to Linear Algebra Appl..
  • 2. ANSI/IEEE, New York, IEEE Standard for Binary Floating Point Arithmetic, Std 754-1985 ed., 1985.
  • 3. A. Björck and V. Pereyra, Solution of Vandermonde systems of equations, Math. Comp. 24 (1970), 893-903. MR 0290541 (44:7721)
  • 4. R. W. Butler and A. T. A. Wood, Laplace approximations for hypergeometric functions with matrix argument, Ann. Statist. 30 (2002), no. 4, 1155-1177. MR 1926172 (2003h:62076)
  • 5. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, second ed., MIT Press, Cambridge, MA, 2001. MR 1848805 (2002e:68001)
  • 6. J. Demmel, Accurate SVDs of structured matrices, SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 562-580. MR 1742810 (2001h:65036)
  • 7. J. Demmel and P. 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), Amer. Math. Soc., Providence, RI, 2001, pp. 117-143. MR 1855508 (2002h:65055)
  • 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, http://www.math.berkeley.edu/~dumitriu.
  • 10. A. Edelman and B. Sutton, Tails of condition number distributions, submitted to SIAM J. Matrix Anal. Appl.
  • 11. W. 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 (91f:65080)
  • 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. MR 1799027 (2002b:33004)
  • 13. G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work., AMS Chelsea Publishing Company, New York, 1999.MR 0106147 (21:4881)
  • 14. N. J. Higham, Stability analysis of algorithms for solving confluent Vandermonde-like systems, SIAM J. Mat. Anal. Appl. 11 (1990), no. 1, 23-41. MR 1032215 (91d:65062)
  • 15. -, Accuracy and stability of numerical algorithms, second ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606 (2003g:65064)
  • 16. G. James and A. 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 0644144 (83k:20003)
  • 17. F. Knop and S. Sahi, A recursion and a combinatorial formula for Jack polynomials, Invent. Math. 128 (1997), no. 1, 9-22. MR 1437493 (98k:33040)
  • 18. P. Koev, http://www-math.mit.edu/~plamen.
  • 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 (95m:05245)
  • 22. -, Symmetric functions and Hall polynomials, 2nd ed., Oxford University Press, 1995. MR 1354144 (96h:05207)
  • 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. R. J. Muirhead, Aspects of multivariate statistical theory, John Wiley & Sons Inc., New York, 1982, Wiley Series in Probability and Mathematical Statistics. MR 0652932 (84c:62073)
  • 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. MR 0292344 (45:1431)
  • 28. R. Stanley, Some combinatorial properties of Jack symmetric functions, Adv. Math. 77 (1989), no. 1, 76-115. MR 1014073 (90g:05020)
  • 29. -, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999.MR 1676282 (2000k:05026)
  • 30. H. Van de Vel, Numerical treatment of a generalized Vandermonde system of equations, Linear Algebra Appl. 17 (1977), 149-179.MR 0474757 (57:14390)

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
Email: demmel@eecs.berkeley.edu

Plamen Koev
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: plamen@math.mit.edu

DOI: https://doi.org/10.1090/S0025-5718-05-01780-1
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.

American Mathematical Society