Reduced complexity evaluation of hypergeometric functions. (English) Zbl 0613.42007
The author employs fast Fourier transform-like techniques in order to reduce the complexity of the evaluation of standard approximations to hypergeometric functions and the gamma function. This leads to algorithms that provide n digits of these functions for O(\(\sqrt{n}(\log n)^ 2)\) arithmetic operations. The usual methods require O(n) operations for comparable accuracy.
Reviewer: R.Srivastava
MSC:
| 42A38 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |
| 33C05 | Classical hypergeometric functions, \({}_2F_1\) |
Keywords:
fast Fourier transform-like techniques; hypergeometric functions; gamma function; algorithmsReferences:
| [1] | Abramowitz, M.; Stegun, I. A., (Handbook of Mathematical Functions (1970), National Bureau of Standards: National Bureau of Standards Washington, D. C) |
| [2] | Aho, A.; Hopcroft, J.; Ullman, J., The design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0326.68005 |
| [3] | Beeler, M.; Gosper, R. W.; Scroeppel, R., Hakmem (1974), MIT Artificial Intelligence Lab., MIT: MIT Artificial Intelligence Lab., MIT Cambridge, Mass |
| [4] | Borodin, A.; Munroe, I., The Computational Complexity of Algebraic and Numeric Problems (1975), Amer. Elsevier: Amer. Elsevier New York · Zbl 0404.68049 |
| [5] | Borwein, J. M.; Borwein, P. B., The arithmetic-geometric mean and fast computation of elementary functions, SIAM Rev., 26, 351-366 (1984) · Zbl 0557.65009 |
| [7] | Brent, R. P., The complexity of multiple-precision arithmetic, (Proceedings, Seminar on Complexity of Computational Problem Solving (1975), Queensland Univ. Press: Queensland Univ. Press Brisbane) · Zbl 0276.65023 |
| [8] | Brent, R. P., Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach., 23, 242-251 (1976) · Zbl 0324.65018 |
| [9] | Knuth, D., Seminumerical Algorithms, (The Art of Computer Programming, Vol. 2 (1969), Addison-Wesley: Addison-Wesley Reading, Mass) · Zbl 0895.65001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
