Assume given the system of 3 monomials over 3 indeterminates f₁ = x^a11 y^a12 z^a13, f₂ = x^a21 y^a22 z^a23, f₃ = x^a31 y^a32 z^a33 , which is described by a nonnegative integer matrix A = (a_ij) of size 3 × 3 without zero rows. By l(f₁, f₂, f₃) (another notation l(A)) we denote the minimal number of multiplications for computation of the system of monomials {f₁, f₂, f₃} given the indeterminates x, y, z (repeated use of the results of intermediate computation is permitted). The main result of the paper is the asymptotic formula l (x^a11 y^a12 z^a13, x^a21 y^a22 z^a23, x^a31 y^a32 z^a33 ) = (1 + o(1)) log₂ D(A), D(A) → ∞, where D(A) is the maximum of the absolute values of the minors of A, where the maximum is taken over all minors.

vector additive chain, evaluations of monomials, circuit complexity, complexity of matrix

Mathematical problems and theory of numerical methods