Geodesic
Arithmetic complexity of the Stirling transforms
Diskretnaya Matematika, Tome 26 (2014) no. 4, pp. 23-35.

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

For the linear Stirling transforms of both kinds, which are well-known in combinatorics, we obtain close to optimal estimates of the complexity of computation by vector addition chains and non-branching programs composed of arithmetic operations over real numbers. A relation between these problems and the Lagrange and Newton interpolation is discussed.
Keywords: Stirling transforms of the 1st and 2nd kinds, addition vector chains, circuits in arithmetic bases, the Lagrange and Newton interpolation, Vandermonde matrices, the Gauss $q$-binomial coefficient. 
@article{DM_2014_26_4_a2,
     author = {S. B. Gashkov},
     title = {Arithmetic complexity of the {Stirling} transforms},
     journal = {Diskretnaya Matematika},
     pages = {23--35},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2014_26_4_a2/}
}
TY  - JOUR
AU  - S. B. Gashkov
TI  - Arithmetic complexity of the Stirling transforms
JO  - Diskretnaya Matematika
PY  - 2014
SP  - 23
EP  - 35
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2014_26_4_a2/
LA  - ru
ID  - DM_2014_26_4_a2
ER  - 
%0 Journal Article
%A S. B. Gashkov
%T Arithmetic complexity of the Stirling transforms
%J Diskretnaya Matematika
%D 2014
%P 23-35
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2014_26_4_a2/
%G ru
%F DM_2014_26_4_a2
S. B. Gashkov. Arithmetic complexity of the Stirling transforms. Diskretnaya Matematika, Tome 26 (2014) no. 4, pp. 23-35. http://geodesic.mathdoc.fr/item/DM_2014_26_4_a2/

[1] Riordan Dzh., Vvedenie v kombinatornyi analiz, IL, Moskva, 1963

[2] Gulden Ya. Dzhekson D., Perechislitelnaya kombinatorika., Nauka, Moskva, 1990 | MR

[3] Aigner M., Kombinatornaya teoriya., Mir, Moskva, 1982 | MR

[4] Riordan Dzh., Kombinatornye tozhdestva, Nauka, Moskva, 1982 | MR | Zbl

[5] Stefensen I.P., Teoriya interpolyatsii, ONTI, M., 1935

[6] Knut D., Iskusstvo programmirovaniya, v. 2, Vilyams, Kiev, Moskva, S.Peterburg, 2000

[7] Gashkov S., Kochergin V., “On addition chains of vectors, gate circuits, and the complexity of computation of power”, Syberian Adv. in Math., 4:4 (1994), 1–16 | MR

[8] Gashkov S.B., “Ob arifmeticheskoi slozhnosti vychisleniya nekotorykh lineinykh preobrazovanii”, Vestn. Mosk. un-ta. Seriya 1. Matematika. Mekhanika, 2014

[9] Gashkov S.B., Gashkov I.B., “O slozhnosti vychisleniya differentsialov i gradientov”, Diskretnaya matematika, 17:2 (2005), 45–67 | DOI | MR | Zbl

[10] Morgenstern J., “Note on lower bound of the linear complexity of the fast Fourier transform”, J.ACM, 20:2 (1973), 305-306 | DOI | MR | Zbl

[11] Akho A., Khopkroft Dzh., Ulman Dzh., Proektirovanie i analiz vychislitelnykh algoritmov, Mir, Moskva, 1979

[12] von zur Gathen J., Gerhard J., Modern Computer Algebra, Cambridge Univ. Press, Cambridge, 1999 | MR | Zbl

[13] Gashkov S.B., Chubarikov V.N., Arifmetika. Algoritmy. Slozhnost vychislenii., Vysshaya shkola, M., 2000

[14] Cooley J., Tukey J., “An algorithm for the machine calculation of complex Fourier series”, Math. Comp., 19 (1965), 297–301 | DOI | MR | Zbl

[15] Cantor D., Kaltofen E., “On fast multiplication of polynomials over arbitrary algebras”, Acta Informatica, 28 (1991), 693-701 | DOI | MR | Zbl

[16] Schönhage A., “Schnelle multiplikation von polynomen über körpern der charakteristik 2”, Acta Informatica, 7 (1977), 395–398 | DOI | MR | Zbl

[17] Gashkov S.B., “O slozhnosti integrirovaniya ratsionalnykh drobei”, Trudy Matem. instituta im. V.A. Steklova, 218 (1997), 122–133 | MR | Zbl

[18] Gashkov S.B., Sergeev I.S., “O slozhnosti i glubine bulevykh skhem dlya umnozheniya i invertirovaniya v konechnykh polyakh kharakteristiki dva”, Diskretnaya matematika, 25(1) (2013), 3–32 | DOI | MR | Zbl

[19] Bostan A., Schost E., “Polynomial evaluation and interpolation on special sets of points”, J. Complexity, 21(4) (2005), 420-446 | DOI | MR | Zbl

[20] Harvey D., van der Hoeven J., Lecerf G., “Faster polynomial multiplication over finite fields”, 12 Jul 2014, arXiv: 1407.3361