RUS  ENG
Полная версия
ЖУРНАЛЫ // Фундаментальная и прикладная математика // Архив

Фундамент. и прикл. матем., 2012, том 17, выпуск 2, страницы 107–166 (Mi fpm1404)

Эта публикация цитируется в 1 статье

Экспонента сложности матричного умножения

Д. В. Жданович

Московский государственный университет им. М. В. Ломоносова

Аннотация: В 1990 году Д. Копперсмит и С. Виноград опубликовали оценку количества арифметических операций, необходимых для вычисления произведения квадратных матриц размера $n\times n$, равную $O(n^{2,3755})$. В настоящей работе проведена систематизация теоретического инструментария, использование которого привело к этой оценке. Одним из результатов проведённой систематизации является улучшение оценки Д. Копперсмита и С. Винограда до $O(n^{2,373})$.

Ключевые слова: трилинейные тензоры, тернарные отношения, ранг тензора, ёмкость отношения, сложность вычисления произведения матриц.

УДК: 512.55


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2012, 186:4, 599–643

Реферативные базы данных:


© МИАН, 2024