Что не так с методом Штрассена для вычисления квадрата матрицы?

Question

Используя тот же подход, что и для Штрассена, достаточно только 5 умножений для вычисления квадрата матрицы. Если A[2][2] = [a, b, c, d], умножением являются a * a, d * d, b * (a + d), c * (a + d), b * c.

Если мы обобщим этот алгоритм для получения квадрата матрицы, сложность уменьшится до n^log5 с основанием 2.

Мне задали вопрос, чтобы найти, что не так с этим алгоритмом, и когда он терпит неудачу, если мы обобщим этот алгоритм, чтобы найти квадрат матрицы?

Answer 1

Вы можете обойтись только с 5 умножениями в корне дерева вызовов, но некоторые из этих умножений не являются квадратами, поэтому время выполнения не лучше, чем у Штрассена для умножения.

Другими словами, если бы у нас был алгоритм O(n^c) для возведения в квадрат матрицы n на n, то мы получили бы алгоритм O(n^c) для умножения путем возведения в квадрат блочной матрицы 2n на 2n

     2
[0 A]    [AB 0 ]
[B 0]  = [0  BA].

Answer 2

Этот алгоритм не может работать, поскольку умножение матриц не является коммутативным.

ab + bd! = b (a + d), потому что b(a+d) = ba+bd и для умножения матриц ab!=ba. поэтому мы не можем уменьшить любое умножение. Этот алгоритм работает только для матриц 2X2.

Answer 3

Наличие матрицы A:

ab
cd

Мы можем вычислить AA наивным образом с 8 умножениями:

aa + bc
ab + bd 
ac + cd 
bc + dd

Непосредственное применение умножения Штрассена даст нам 7 умножений.

Но, используя такой же подход, как Штрассен, мы можем заметить, что:

ab + bd = b(a + d) 
ac + cd = c(a + d)

Итак, действительно, мы можем сделать только 5 умножений, чтобы получить результат:
aa, dd, bc, b(a + d), c(a + d),

В этом методе нет ничего плохого, т.е. он подходит для всех входов.

Может быть, ваш интервьюер хотел, чтобы вы представили свое мышление и отстаивали, что на самом деле это не так, вместо того, чтобы соглашаться с тем, что это неправильно.

Если ваш интервьюер все еще говорит, что это неправильно, хорошей идеей будет спросить, каково определение "неправильно". Может быть "не оптимально" (с точки зрения количества квадратов, умножений и сложений). Хорошо для чтения.

Или, может быть, это "неправильно", потому что он не масштабируется, например, он не будет работать для матриц 4x4.