True Bit Сложность умножения матриц

9

Умножение матриц с использованием обычной техники (ряд - столбец) занимает O(n3) умножение и O(n3)дополнения. Однако при условии, что записи равного размера (количество битов в каждой записи обеих матриц умножается) размераm биты, операция сложения на самом деле происходит на O(n3nm)=O(n4m) биты.

Таким образом, кажется, что истинная сложность умножения матриц, если измеряться с помощью битовой сложности, должна быть O(n4),

(1)Это правильно?

Предположим, если кто-то создает алгоритм, который уменьшает сложность бита до O(n3+ϵ) вместо общего умножения и сложения, это может быть более надежный подход, чем, скажем, сокращение общего умножения и сложения O(n2+ϵ) как попытались исследователи, такие как Копперсмит и Кон.

(2) Это действительный аргумент?

Т ....
источник

Ответы:

31

Нет, битовая сложность умножения матриц на M-битные записи nω(logn)O(1)M(logM)O(1), где ω<2.4является самым известным показателем умножения матриц. Умножение и сложениеM-битные числа могут быть сделаны в M(logM)2время. Умножение двухM-битные числа дают число, которое имеет не более 2Mбиты. Добавлениеn числа M каждый бит, дает число, которое имеет не более M+logn+O(1)биты. (Подумайте об этом: сумма не болееn2MТаким образом, битовое представление занимает не более log(n2M)+O(1) бит.)

Ссылки на быстрые алгоритмы умножения целых чисел можно найти с помощью веб-поиска или википедии.

Райан Уильямс
источник
Я думаю, что мой аргумент был ошибочным. Спасибо. Я ценю это.
T ....