Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №15, Москва, 2006
Авторы: Кочергин В.В.
О сложности совместного вычисления трех одночленов от трех переменных
Аннотация:
Пусть дана система из трех одночленов от трех переменных f1 = xa11 ya12 za13, f2 = xa21 ya22 za23, f3 = xa31 ya32 za33, заданная целочисленной матрицей A = (aij) размера 3 × 3 с неотрицательными элементами без нулевых строк. Под сложностью l(f1, f2, f3) (другое обозначение: l(A)) вычисления этой системы понимается минимальное число операций умножения, достаточное для вычисления системы {f1, f2, f3} по переменным x, y, z (разрешается многократное использование результатов промежуточных вычислений). Основным результатом работы является асимптотическое соотношение l (xa11 ya12 za13, xa21 ya22 za23, xa31 ya32 za33 ) = (1 + o(1)) log2 D(A), D(A) → ∞, где D(A) - это максимум абсолютных величин миноров матрицы A (максимум берется по всем минорам).
Ключевые слова:
аддитивная цепочка векторов, вычисление одночленов, схемная сложность, сложность матрицы
Язык публикации: русский, страниц: 76 (с. 79-154)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Кочергин Вадим Васильевич,  ,  Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ