On the Computational Complexity of Compressed Power Series

E. A. Karatsuba

Matematičeskie zametki, Tome 114 (2023) no. 1, pp. 113-120.

Résumé

We present computational algorithms and complexity estimates for power series in which all exponents are positive integers raised to one and the same integer power $\ge2$.

Détail

Keywords: algorithm, power series, computational complexity, fast algorithm, FEE method, Faulhaber's formula, Bernoulli numbers.

Bibliographie

[1] Dzh. N. Vatson, E. T. Uitteker, Kurs sovremennogo analiza, Mir, M., 1963 | MR

[2] S. M. Voronin, A. A. Karatsuba, Dzeta-funktsiya Rimana, Nauka, M., 1994 | MR

[3] V. V. Dodonov, ““Nonclassical” states in quantum optics: a “squeezed” review of the first 75 years”, J. Opt. B Quantum Semiclass. Opt., 4:1 (2002), R1–R33 | DOI | MR

[4] R. Tanaś, “Nonclassical states of light propagating in Kerr media, Chapter 6”, Theory of Nonclassical States of Light, eds. V. V. Dodonov, V. I. Man'ko, CRC Press, 2019, 267–312

[5] A. Karatsuba, Yu. Ofman, “Umnozhenie mnogoznachnykh chisel na avtomatakh”, Dokl. AN SSSR, 145:2 (1962), 293–294

[6] E. B. Dynkin, A. N. Kolmogorov, A. I. Kostrikin, I. I. Pjateckii-Sapiro, I. R. Safarevic, Six Lectures Delivered at the International Congress of Mathematicians in Stockholm, Amer. Math. Soc. Transl. 2, 31, Amer. Math. Soc., 1962

[7] A. A. Karatsuba, “Slozhnost vychislenii”, Optimalnoe upravlenie i differentsialnye uravneniya, Sbornik statei. K semidesyatiletiyu so dnya rozhdeniya akademika Evgeniya Frolovicha Mischenko, Tr. MIAN, 211, Nauka, Fizmatlit, M., 1995, 186–202 | MR | Zbl

[8] A. A. Karatsuba, “Kommentarii k moim rabotam, napisannye mnoi samim”, Matematika i informatika, 2, K 75-letiyu so dnya rozhdeniya Anatoliya Alekseevicha Karatsuby, Sovr. probl. matem., 17, MIAN, M., 2013, 7–29 | DOI

[9] A. L. Toom, “O slozhnosti skhemy iz funktsionalnykh elementov, realizuyuschei umnozhenie tselykh chisel”, Dokl. AN SSSR, 150:3 (1963), 496–498 | MR | Zbl

[10] A. Schönhage, V. Strassen, “Schnelle Multiplikation grosser Zahlen”, Computing (Arch. Elektron. Rechnen), 7 (1971), 281–292 | DOI | MR

[11] M. Fürer, “Faster integer multiplication”, SIAM J. Comput., 39:3 (2009), 979–1005 | DOI | MR

[12] E. A. Karatsuba, “Bystrye vychisleniya transtsendentnykh funktsii”, Probl. peredachi inform., 27:4 (1991), 76–99 | MR | Zbl

[13] E. A. Karatsuba, “Bystroe vychislenie dzeta-funktsii Rimana $\zeta(s)$ pri tselykh znacheniyakh argumenta $s$”, Probl. peredachi inform., 31:4 (1995), 69–80 | MR | Zbl

[14] E. A. Karatsuba, “Bystroe vychislenie znachenii dzeta-funktsii Gurvitsa i $L$-ryadov Dirikhle”, Probl. peredachi inform., 34:4 (1998), 62–75 | MR | Zbl

[15] E. A. Karatsuba, “Fast evaluation of hypergeometric functions by FEE”, Computational Methods and Function Theory (Nicosia, 1997), Ser. Approx. Decompos., 11, World Sci., River Edge, NJ, 1999, 303–314 | MR

[16] E. A. Karatsuba, “Fast computation of $\zeta(3)$ and of some special integrals using the Ramanujan formula and polylogarithms”, BIT, 41:4 (2001), 722–730 | DOI | MR

[17] E. A. Karatsuba, “Fast computation of some special integrals of mathematical physics”, Scientific Computing, Validated Numerics, Interval Methods, eds. W. Kramer, J. W. von Gudenberg, 2001, 29–41

[18] E. A. Karatsuba, “O vychislenii funktsii Besselya putem summirovaniya ryadov”, Sib. zhurn. vychisl. matem., 22:4 (2019), 453–472 | DOI

[19] C. L. Siegel, Transcendental Numbers, Princeton Univ. Press, Princeton, 1949 | MR

[20] A. P. Prudnikov, Yu. A. Brychkov, O. I. Marichev, Integraly i ryady, v. 1, Elementarnye funktsii, Nauka, M., 1981 | MR

[21] J. Faulhaber, Academia Algebrae – Darinnen die miraculosische Inventiones zu den höchsten Cossen weiters continuirt und profitiert werden, 1631

[22] J. Bernoulli, “Ars conjectandi, opus posthumum”, Accedit Tractatus de seriebus infinitis, et epistola gallicé scripta de ludo pilae reticularis, Thurneysen Brothers, Basel, 1713