×

Arithmetic complexity of certain linear transformations. (English. Russian original) Zbl 1331.68106

Math. Notes 97, No. 4, 531-555 (2015); translation from Mat. Zametki 97, No. 4, 529-555 (2015).
Summary: 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:|a|\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\mod p\}\) are also considered.

MSC:

68Q25 Analysis of algorithms and problem complexity
15A04 Linear transformations, semilinear transformations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Riordan, An Introduction to Combinatorial Analysis (J. Wiley, New York, 1958; Inostr. Lit., Moscow, 1963). · Zbl 0078.00805
[2] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration (John Wiley, New York, 1983; Nauka, Moscow, 1990). · Zbl 0519.05001
[3] Donald E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969; Mir, Moscow, 2000). · Zbl 0191.18001
[4] S. B. Gashkov and V. V. Kochergin, “On addition chains of vectors, gate circuits and the complexity of computations of powers,” Metody Diskretn. Anal. 52, 22-40 (1992) [Sib. Adv. Math. 4 (4), 1-16 (1994)]. · Zbl 0849.68055
[5] J. Morgenstern, “Note on lower bound for the linear complexity of the fast Fourier transform,” J. Assoc. Comput. Mach. 20 (2), 305-306 (1973). · Zbl 0258.65120 · doi:10.1145/321752.321761
[6] D. K. Faddeev and I. S. Sominskii, Problems of Higher Algebra (Lan’, St. Petersburg, 1999) [in Russian]. · Zbl 0047.25202
[7] E. Yu. Smirnov, Young Diagrams, Planar Partitions, and Alternating-Sign Matrices (MTsNMO, Moscow, 2014) [in Russian].
[8] D. G. Cantor and E. Kaltofen, “On fast multiplication of polynomials over arbitrary algebras,” Acta Inform. 28 (7), 693-701 (1991). · Zbl 0766.68055 · doi:10.1007/BF01178683
[9] A. Schönhage, “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2,” Acta Inform. 7 (4), 395-398 (1977). · Zbl 0362.65011 · doi:10.1007/BF00289470
[10] J. von zur Gathen and J. Gerhard, Modern Computer Algebra (Cambridge Univ. Press, Cambridge, 1999). · Zbl 0936.11069
[11] A. Aho, J. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, 1975; Mir, Moscow, 1979). · Zbl 0307.68053
[12] J. W. Cooley and J. W. Tukey, “An algorithm for the machine compution of complex Fourier series,” Math. Comp. 19, 297-301 (1965). · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1
[13] S. B. Gashkov and V. N. Chubarikov, Arithmetic. Algorithms. Complexity of Computations (Vyassh. Shkola, Moscow, 2000) [in Russian]. · Zbl 0997.00508
[14] J. Boyar and M. C. Find, Cancellation-Free Circuits: An Approach for Proving Superlinear Lower Bounds for Linear Boolean Operators, arXiv: 1207.5321. · Zbl 1328.94110
[15] D. Yu. Grigor’ev, “Lower bounds in the algebraic computational complexity,” in Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova, Vol. 118: Theory of Computational Complexity. I (Izd. “Nauka (Leningradsk. Otd.), Leningrad, 1982), pp. 25-82 [in Russian]. · Zbl 0504.68024
[16] D. Yu. Grigor’ev, “Additive complexity in directed computations,” Theoret. Comput. Sci. 19 (1), 39-67 (1982). · Zbl 0486.68028 · doi:10.1016/0304-3975(82)90014-7
[17] A. V. Chashkin, “On the complexity of Booleanmatrices, graphs, and the Boolean functions corresponding to them,” Discrete Math. Appl. 4, No. 3, 229-257 (1994); translation from Diskretn. Mat. 6, No. 2, 43-73 (1994). Diskret.Mat. 6 (2), 43-73 (1994) [Discrete Math. Appl. 6 (2), 43-73 (1994)]. · Zbl 0925.68334 · doi:10.1515/dma.1994.4.3.229
[18] N. Alon, M. Karchmer, and A. Wigderson, “Linear circuits over GF(2),” SIAM J. Comput. 19 (6), 1064-1067 (1990). · Zbl 0712.05015 · doi:10.1137/0219074
[19] S. B. Gashkov and I. B. Gashkov, “On the complexity of compution of differentials and gradients,” Diskret. Mat. 17 (3), 45-67 (2005) [Discrete Math. Appl. 15 (4), 327-350 (2005)]. · Zbl 1082.65027 · doi:10.4213/dm115
[20] I. P. Stephensen, Theory of Interpolation (ONTI, Moscow, 1935) [Russian transl.].
[21] J. Riordan, Combinatorial Identities (Krieger Publ., Huntington, NY, 1979; Nauka, Moscow, 1982). · Zbl 0194.00502
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.