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/