Geodesic
On the Computational Complexity of Compressed Power Series
Matematičeskie zametki, Tome 114 (2023) no. 1, pp. 113-120

Voir la notice de l'article provenant de la source Math-Net.Ru

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$.
Keywords: algorithm, power series, computational complexity, fast algorithm, FEE method, Faulhaber's formula, Bernoulli numbers. 
E. A. Karatsuba. On the Computational Complexity of Compressed Power Series. Matematičeskie zametki, Tome 114 (2023) no. 1, pp. 113-120. http://geodesic.mathdoc.fr/item/MZM_2023_114_1_a8/
@article{MZM_2023_114_1_a8,
     author = {E. A. Karatsuba},
     title = {On the {Computational} {Complexity} of {Compressed} {Power} {Series}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {113--120},
     year = {2023},
     volume = {114},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2023_114_1_a8/}
}
TY  - JOUR
AU  - E. A. Karatsuba
TI  - On the Computational Complexity of Compressed Power Series
JO  - Matematičeskie zametki
PY  - 2023
SP  - 113
EP  - 120
VL  - 114
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MZM_2023_114_1_a8/
LA  - ru
ID  - MZM_2023_114_1_a8
ER  - 
%0 Journal Article
%A E. A. Karatsuba
%T On the Computational Complexity of Compressed Power Series
%J Matematičeskie zametki
%D 2023
%P 113-120
%V 114
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_2023_114_1_a8/
%G ru
%F MZM_2023_114_1_a8

[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