On the additive complexity of GCD and LCM matrices
Let GCD (respectively LCM) be the \(n\times n\) greatest common divisor (least common multiple) matrix, and let \(L_B(A)\) denote the complexity of a matrix~\(A\) over a basis~\(B\). Denoting by~\(A^{[r]}\) the \(r\)'th Hadamard (i.e., entrywise) power of~\(A\), and by~\(\sim\) the asymptotic equality as \(n\to\infty\), the authors prove (Theorem~1) that \(L_B(\text{GCD}^{[r]})\sim rn\log_2n\) over \(B=\{x+y\}\) and (Theorem~2) \(L_B(\text{LCM}^{[r]})\sim 2rn\log_2n\) over \(B=\{x+y\}\cup\{ax\mid |a|\leq 1\}\). Thereafter, they note: Although the result of Theorem~2 is asymptotically sharp, it is obtained in a powerful basis admitting non-integer-valued operations. A derivation of a similar result in a basis with minimal family of computational tools would be of interest. So they prove (Theorem~3) that the above formula holds also over \(B=\{x+y,-x\}\).
- Approximate formulas for some functions of prime numbers
- Arithmetic complexity of certain linear transformations
- Arithmetic complexity of the Stirling transforms
- Complexity of Linear Boolean Operators
- Handbook of Number Theory I
- scientific article; zbMATH DE number 2133276 (Why is no real title available?)
- scientific article; zbMATH DE number 913229 (Why is no real title available?)
- scientific article; zbMATH DE number 3303655 (Why is no real title available?)
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- On GCD and LCM matrices
- On Smith's determinant
- On the complexity of Boolean matrices, graphs, and the Boolean functions corresponding to them
- On the complexity of calculation of differentials and gradients
- Problems and theorems in analysis. I. Series, integral calculus, theory of functions. Transl. from the German by Dorothee Aeppli
This page was built for publication: On the additive complexity of GCD and LCM matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q509060)
