Определение показателя умножения матриц

15

В разговорной речи определение показателя умножения матриц является наименьшим значением, для которого существует известный алгоритм умножения матриц . Это неприемлемо как формальное математическое определение, поэтому я предполагаю, что техническое определение является чем-то вроде инфимума по всем , так что в существует алгоритм умножения матриц .ωnωtnt

В этом случае нельзя сказать, что существует алгоритм умножения матриц в или даже в , просто для всех существует алгоритм в . Однако, часто статьи и результаты, которые используют умножение матриц, сообщают о своей стоимости просто как .nωnω+o(1)ϵ>0nω+ϵO(nω)

Есть ли какое-то альтернативное определение которое разрешает такое использование? Существуют ли какие-либо результаты, гарантирующие, что алгоритм времени или должен существовать? Или использование просто небрежно?п ω п ω + O ( 1 ) О ( п ω )ωnωnω+o(1)O(nω)

Дэвид Харрис
источник
2
Если вы просто хотите использовать умножение матриц в качестве черного ящика, проще всего сказать: «Пусть ω таково, что мы можем умножить n×n -матрицы с O(nω) арифметическими операциями». Конечно, тогда ω не является показателем умножения матриц, но может быть сколь угодно близко. Если вы хотите указать показатель вашего окончательного бега в десятичном представлении, в настоящее время вы все равно должны округлить, поскольку все нетривиальные оценки для ω о которых я знаю, являются либо иррациональными числами, либо бесконечными последовательностями.
Маркус Блезер
2
ω обычно определяется как инфимум по всем вещественным значениямk дляn идущего к , так что существуеталгоритм времениO(nk) , который умножает двематрицыn×n (где время - это число сложений, умножений и делений в основное поле). Это также означает, что технически мы всегда должны писатьnω+o(1) но это становится беспорядочным, поэтому, когда вы видитеO(nω) вы должны думать, что где M ( n ) - время выполнения алгоритма матричного умножения. O(M(n))M(n)
virgi

Ответы:

20

Показатель умножения матриц, являющийся , не гарантирует, что существует алгоритм, который выполняется за время O ( n ω ) , но только то, что для каждого ϵ > 0 , существует алгоритм, который выполняется за O ( n ω + ϵ ) . Действительно , если вы можете найти алгоритм , который работает в время O ( п 2 р о л у л о г ( п ) ) , то это показывает , что ω = 2 .ωO(nω)ϵ>0O(nω+ϵ)O(n2polylog(n))ω=2

Вы можете найти формальное определение в книге «Теория алгебраической сложности» Питера Бюргиссера, Михаэля Клаузена, Амина Шокроллахи.

MCH
источник
7

Небольшой комментарий, который слишком длинный, чтобы быть комментарием:

Иногда, когда у вас есть проблема, для которой существует алгоритм со временем выполнения для каждого ϵ > 0 , существует алгоритм со временем выполнения n k + o ( 1 ) .O(nk+ϵ)ϵ>0nk+o(1)

Например, иногда вы получаете алгоритмы, которые идут как для некоторой быстро растущей функции f (например, 2 2 1 / ϵ ). Если вы установите f ( 1 / ϵ ) в (скажем) log n , то ϵ будет o (1). В примере с f ( 1 / ϵ ), равным 2 2 1 / ϵ , вы можете выбрать 1 / ϵf(1/ϵ)nk+ϵf221/ϵf(1/ϵ)lognϵf(1/ϵ)221/ϵ1/ϵбыть , что дает ϵ = 1 / ( log log log n ) , что равно o (1). Таким образом, окончательное время работы этого алгоритма будет n k + o ( 1 ) , поскольку log n также равно n o ( 1 ) .logloglognϵ=1/(logloglogn)nk+o(1)lognno(1)

Робин Котари
источник
Я полагаю, что алгоритм Coppersmith-Winograd попадает в эту категорию?
Дэвид Харрис
2
@DavidHarris: не знаю об этом. Может быть, кто-то, кто понимает алгоритм, сможет пролить свет на это. Я просто хотел сказать, что часто не так плохо, как кажется. O(nk+ϵ)
Робин Котари
5

Хорошо известен результат Копперсмита и Винограда о том, что -время не может быть реализовано ни одним единственным алгоритмом. Но я читал, что они ограничены алгоритмами, основанными на билинейных тождествах, подобных Штрассену, так что я не знаю точно, так как статья находится за платным доступом.O(nω)

Диего де Эстрада
источник
3

Я не согласен с вашим утверждением в вопросе о том, что недостаточно четко определено «наименьшим значением, для которого существует известный алгоритм умножения матриц n ω ». Когда люди используют эту константу, это потому, что их алгоритм основан на умножении матриц, а под сложностью n ω они подразумевают «оптимальная сложность нашего алгоритма определяется оптимальным алгоритмом умножения матриц».ωnωnω

Я не говорю, что иначе невозможно определить (например, говоря, что ω - это наилучшая достижимая сложность).ωω

Кстати, самая известная верхняя граница для умножения матриц только что была улучшена до если я не ошибаюсь. 2.3737

Bruno
источник
3
Я не понимаю, как человеческие знания могут быть частью математического определения
Дэвид Харрис
2
Недавний опыт показывает, что количественно определить все алгоритмы намного проще, чем все алгоритмы, известные человечеству в настоящее время ;-)
Маркус Блезер