KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №15, Moscow, 2006
Authors: Kochergin V.V.
On the complexity of computation of three monomials in three variables
Assume given the system of 3 monomials over 3 indeterminates f1 = xa11 ya12 za13, f2 = xa21 ya22 za23, f3 = xa31 ya32 za33 , which is described by a nonnegative integer matrix A = (aij) of size 3 × 3 without zero rows. By l(f1, f2, f3) (another notation l(A)) we denote the minimal number of multiplications for computation of the system of monomials {f1, f2, f3} 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 (xa11 ya12 za13, xa21 ya22 za23, xa31 ya32 za33 ) = (1 + o(1)) log2 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
Publication language: russian,  pages: 76 (p. 79-154)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Kochergin Vadim Vasil'evich,  ,  Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ