Пусть дана система из трех одночленов от трех переменных f₁ = x^a11 y^a12 z^a13, f₂ = x^a21 y^a22 z^a23, f₃ = x^a31 y^a32 z^a33, заданная целочисленной матрицей A = (a_ij) размера 3 × 3 с неотрицательными элементами без нулевых строк. Под сложностью l(f₁, f₂, f₃) (другое обозначение: l(A)) вычисления этой системы понимается минимальное число операций умножения, достаточное для вычисления системы {f₁, f₂, f₃} по переменным x, y, z (разрешается многократное использование результатов промежуточных вычислений). Основным результатом работы является асимптотическое соотношение 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) → ∞, где D(A) - это максимум абсолютных величин миноров матрицы A (максимум берется по всем минорам).

аддитивная цепочка векторов, вычисление одночленов, схемная сложность, сложность матрицы

Математические вопросы и теория численных методов