Geodesic
On the Additive Complexity of GCD and LCM Matrices
Matematičeskie zametki, Tome 100 (2016) no. 2, pp. 196-211.

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

In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the $n\times n$ matrix formed by the numbers $\text{GCD}^r(i,k)$ over the basis $\{x+y\}$ is asymptotically equal to $rn \log_2 n$ as $n\to\infty$, and the complexity of the $n\times n$ matrix formed by the numbers $\text{LCM}^r(i,k)$ over the basis $\{x+y,-x\}$ is asymptotically equal to $2rn \log_2 n$ as $n\to \infty$.
Keywords: greatest common divisor, least common multiple, additive complexity of matrices, Smith determinant, circuit complexity. 
@article{MZM_2016_100_2_a1,
     author = {S. B. Gashkov and I. S. Sergeev},
     title = {On the {Additive} {Complexity} of {GCD} and {LCM} {Matrices}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {196--211},
     publisher = {mathdoc},
     volume = {100},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2016_100_2_a1/}
}
TY  - JOUR
AU  - S. B. Gashkov
AU  - I. S. Sergeev
TI  - On the Additive Complexity of GCD and LCM Matrices
JO  - Matematičeskie zametki
PY  - 2016
SP  - 196
EP  - 211
VL  - 100
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2016_100_2_a1/
LA  - ru
ID  - MZM_2016_100_2_a1
ER  - 
%0 Journal Article
%A S. B. Gashkov
%A I. S. Sergeev
%T On the Additive Complexity of GCD and LCM Matrices
%J Matematičeskie zametki
%D 2016
%P 196-211
%V 100
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2016_100_2_a1/
%G ru
%F MZM_2016_100_2_a1
S. B. Gashkov; I. S. Sergeev. On the Additive Complexity of GCD and LCM Matrices. Matematičeskie zametki, Tome 100 (2016) no. 2, pp. 196-211. http://geodesic.mathdoc.fr/item/MZM_2016_100_2_a1/

[1] H. J. S. Smith, “On the value of a certain arithmetical determinant”, Proc. London Math. Soc., 7:1 (1875), 208–212 | DOI | MR | Zbl

[2] P. Haukkanen, J. Wang, J. Sillanpää, “On Smith's determinant”, Linear Algebra Appl., 258 (1997), 251–269 | DOI | MR | Zbl

[3] J. Sándor, B. Crstici, Handbook of Number Theory. II, Kluwer Acad. Publ., Dordrecht, 2004 | MR | Zbl

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

[5] S. Jukna, I. Sergeev, “Complexity of linear boolean operators”, Found. Trends Theor. Comput. Sci., 9:1 (2013), 1–123 | DOI | MR | Zbl

[6] S. B. Gashkov, “Arifmeticheskaya slozhnost nekotorykh lineinykh preobrazovanii”, Matem. zametki, 97:4 (2015), 529–555 | DOI | MR | Zbl

[7] S. B. Gashkov, “Arifmeticheskaya slozhnost preobrazovanii Stirlinga”, Diskret. matem., 26:4 (2014), 23–35 | DOI

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

[9] C. M. Fiduccia, On the Algebraic Complexity of Matrix Multiplication, Ph.D. thesis, Brown Univ., Providence, RI, 1973

[10] G. Polia, G. Sege, Zadachi i teoremy iz analiza, Ch. 2, Nauka, M., 1978 | MR

[11] S. Z. Chun, “GCD and LCM power matrices”, Fibonacci Quart., 34:4 (1996), 290–297 | MR

[12] A. Brauer, “On addition chains”, Bull. Amer. Math. Soc., 45 (1939), 736–739 | DOI | MR | Zbl

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

[14] J. B. Rosser, L. Schoenfeld, “Approximate formulas for some functions of prime numbers”, Illinois J. Math., 6 (1962), 64–94 | MR | Zbl

[15] J. Sándor, D. S. Mitrinović, B. Crstici, Handbook of Number Theory, I, Springer, Dordrecht, 2006 | MR | Zbl

[16] K. Bourque, S. Ligh, “On GCD and LCM matrices”, Linear Algebra Appl., 174 (1992), 65–74 | DOI | 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