Чебышевский сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2015, том 16, выпуск 4, страницы 11–27 (Mi cheb433)  

О билинейной сложности умножения матриц размеров $m\times 2$ и $2\times 2$

В. Б. Алексеев

Московский государственный университет им. М. В. Ломоносова, факультет вычислительной математики и кибернетики

Аннотация: В данной работе исследуется сложность умножения матриц. Ф. Штрассен в 1969 году [1] построил алгоритм для умножения двух матриц порядка $n$ с числом арифметических операций $O( n^{\log_27})$, что асимптотически лучше, чем сложность порядка $n^3$ стандартного алгоритма умножения матриц «строка на столбец». В последующие годы проводились активные исследования минимальной сложности различных алгебраических операций. Результаты исследований в этой области хорошо отражены в книге [2].
Ситуация в задаче об умножении матриц оказалась достаточно тяжелой. К концу 1980-х годов усилиями многих математиков сложность умножения матриц удалось понизить до $O( n^{2.38})$ [3], но с тех пор существенных продвижений в этой задаче нет.
Для того, чтобы лучше понять проблемы, возникающие при поиске быстрых алгоритмов умножения матриц, эта задача исследуется в разных направлениях. Одним из таких направлений является исследование минимальной сложности умножения матриц малых размеров. Эти исследования имеют самостоятельный интерес, а также связаны с тем, что быстрые алгоритмы для умножения матриц малых размеров могут рекурсивно использоваться для умножения матриц больших размеров. В частности, алгоритм Штрассена основан на рекурсивном использовании найденного им алгоритма умножения двух матриц порядка 2 с 7 умножениями, а не с 8, как в стандартном алгоритме.
Можно обратить внимание на 2 особенности алгоритма Штрассена.
Во-первых, на асимптотическую оценку сложности алгоритма умножения больших матриц, построенного рекурсивно, влияет только число умножений в алгоритме умножения маленьких матриц, используемых для рекурсии.
Во-вторых, при рекурсии элементы маленьких матриц сами являются матрицами и поэтому могут не коммутировать между собой. Эти 2 особенности породили исследования билинейной сложности умножения матриц и умножения в других алгебрах. В билинейных алгоритмах сначала должны вычисляться несколько произведений линейных комбинаций элементов первого сомножителя на линейные комбинации элементов второго сомножителя. А затем из этих произведений линейными комбинациями должны получаться все требуемые выражения. При этом число произведений называют билинейной сложностью билинейного алгоритма, а минимум билинейной сложности по всем билинейным алгоритмам, решающим данную задачу, называют билинейной сложностью задачи.
Установить точное значение билинейной сложности редко удается даже в задачах перемножения двух матриц малого размера. Например, для задачи перемножения двух матриц размера $3\times 3$ к настоящему моменту известно только, что билинейная сложность заключена между 19 и 23 [4, 5]. Несложно установить точное значение билинейной сложности умножения двух матриц, если хотя бы в одной из них всего одна строка или один столбец.
В данной работе исследуется билинейная сложность умножения матрицы размера $m\times 2$ на матрицу размера $2\times 2$ над произвольным полем. Точное значение билинейной сложности для умножения таких матриц над произвольным полем известно только при $m=2,3,4$ [6, 7, 8]. Из результата Штрассена можно несложно получить, что билинейная сложность этой задачи не превосходит $\lceil\frac{7m}{2}\rceil$ для произвольного поля. В работе [9] была получена такая же нижняя оценка, но только для поля из 2 элементов. Для произвольных полей в работе [5] для этой задачи получена нижняя оценка $3m+1$. В данной статье доказано, что билинейная сложность умножения матрицы размера $m\times 2$ на матрицу размера $2\times 2$ над произвольным полем при $m\geq 3$ не может быть меньше чем $3m+2$.
Библиография: 15 названий.

Ключевые слова: матрица, умножение матриц, алгоритм, сложность, билинейная сложность.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 13-01-00183
Работа выполнена по гранту РФФИ 13-01-00183


Полный текст: PDF файл (283 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.712.3, 519.61
Поступила в редакцию: 10.03.2015

Образец цитирования: В. Б. Алексеев, “О билинейной сложности умножения матриц размеров $m\times 2$ и $2\times 2$”, Чебышевский сб., 16:4 (2015), 11–27

Цитирование в формате AMSBIB
\RBibitem{Ale15}
\by В.~Б.~Алексеев
\paper О билинейной сложности умножения матриц размеров $m\times 2$ и $2\times 2$
\jour Чебышевский сб.
\yr 2015
\vol 16
\issue 4
\pages 11--27
\mathnet{http://mi.mathnet.ru/cheb433}
\elib{https://elibrary.ru/item.asp?id=25006091}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb433
  • http://mi.mathnet.ru/rus/cheb/v16/i4/p11

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:360
    Полный текст:115
    Литература:43
    Первая стр.:7
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021