Arithmetic Complexity of Certain Linear Transformations

S. B. Gashkov

Matematičeskie zametki, Tome 97 (2015) no. 4, pp. 529-555.

Résumé

We obtain order-sharp quadratic and slightly higher estimates of the computational complexity of certain linear transformations (binomial, Stirling, Lah, Gauss, Serpiński, Sylvester) in the basis $\{x+y \}\cup \{ax: \vert a \vert \leq C \}$ consisting of the operations of addition and inner multiplication by a bounded constant as well as upper bounds $O(n\log n)$ for the computational complexity in the basis $\{ax+by: a,b \in {\mathbb R}\}$ consisting of all linear functions. Lower bounds of the form $\Omega(n\log n)$ are obtained for the basis consisting of all monotone linear functions $\{ax+by: a, b > 0\}$. For the finite arithmetic basis $B_{+,*,/} = \{x\pm y,xy,1/x,1\}$ and for the bases $\{x\pm y\} \cup \{nx: n \in {\mathbb N}\}\cup \{x/n: n \in {\mathbb N}\}$ and $B_{+,*}=\{x+y,xy,-1\}$, estimates $O(n \log n \log \log n)$ are obtained in certain cases. In the case of a field of characteristic $p$, computations in the basis $\{x+y \operatorname{mod} p\}$ are also considered.

Détail

Mots-clés : linear transformation (binomial, Gauss
Keywords: Stirling, Lah, Serpiński, Sylvester), arithmetic computational complexity of linear transformations, finite arithmetic basis, field of characteristic $p$,.

Bibliographie

[1] Dzh. Riordan, Vvedenie v kombinatornyi analiz, IL, M., 1963 | MR | Zbl

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

[3] D. Knut, Iskusstvo programmirovaniya. T. 2. Poluchislennye algoritmy, Mir, M., 2000 | MR | Zbl

[4] S. B. Gashkov, V. V. Kochergin, “Additivnye tsepochki vektorov, ventilnye skhemy i slozhnost vychisleniya stepenei”, Metody diskret. analiza, 52 (1992), 22–40 | MR | Zbl

[5] J. Morgenstern, “Note on lower bound of the linear complexity of the fast Fourier transform”, J. Assoc. Comput. Mach., 20:2 (1973), 305–306 | DOI | MR | Zbl

[6] D. K. Faddeev, I. S. Sominskii, Zadachi po vysshei algebre, Lan, SPb., 1999

[7] E. Yu. Smirnov, Diagrammy Yunga, ploskie razbieniya i znakochereduyuschiesya matritsy, MTsNMO, M., 2014

[8] D. G. Cantor, E. Kaltofen, “On fast multiplication of polynomials over arbitrary algebras”, Acta Inform., 28:7 (1991), 693–701 | DOI | MR | Zbl

[9] A. Schönhage, “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2”, Acta Inform., 7:4 (1977), 395–398 | DOI | MR | Zbl

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

[11] A. Akho, Dzh. Khopkroft, Dzh. Ulman, Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR | Zbl

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

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

[14] J. Boyar, M. C. Find, Cancellation-Free Circuits: An Approach for Proving Superlinear Lower Bounds for Linear Boolean Operators, arXiv: 1207.5321

[15] D. Yu. Grigorev, “Nizhnie otsenki v algebraicheskoi slozhnosti vychislenii”, Teoriya slozhnosti vychislenii. I, Zap. nauchn. sem. LOMI, 118, Izd-vo «Nauka», Leningrad. otd., L., 1982, 25–82 | MR | Zbl

[16] D. Yu. Grigor'ev, “Additive complexity in directed computations”, Theoret. Comput. Sci., 19:1 (1982), 39–67 | MR | Zbl

[17] A. V. Chashkin, “O slozhnosti bulevykh matrits, grafov i sootvetstvuyuschikh im bulevykh funktsii”, Diskret. matem., 6:2 (1994), 43–73 | MR | Zbl

[18] N. Alon, M. Karchmer, A. Wigderson, “Linear circuits over $\operatorname{GF}(2)$”, SIAM J. Comput., 19:6 (1990), 1064–1067 | DOI | MR | Zbl

[19] S. B. Gashkov, I. B. Gashkov, “O slozhnosti vychisleniya differentsialov i gradientov”, Diskret. matem., 17:3 (2005), 45–67 | DOI | MR | Zbl

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

[21] Dzh. Riordan, Kombinatornye tozhdestva, Nauka, M., 1982 | MR | Zbl