Я проходил курс алгоритмов. Когда я освещал разделяй и властвуй, я наткнулся на алгоритм Штрассена.
Итак, проблема в том, как мы умножаем матрицы с нечетными степенями или четными степенями, которые не являются степенями двойки?
Кроме того, как мы применяем алгоритм Штрассена для матриц разных размеров (например, умножение матрицы 2X3 на матрицу 3X1)?
Скажем, матрицы имеют степень n. Если вы хотите умножить A и B, вы можете просто дополнить A и B нулями (скажем, A_pad, B_pad так, чтобы они были равны (k,k), где k — наименьшая степень двойки, превышающая верхнюю границу n. Поскольку k равно не более чем в два раза больше исходных размеров,
k^log_2(7)<=3 * N^log_2(7)
Так что алгоритм по-прежнему O(N^log_2(7)).
Этот подход не совсем работает с матрицами разных размеров в ситуации, когда одна из матриц «тонкая» (скажем, длина A преобладает над высотой A). В этом случае вам нужно будет разрезать матрицы, чтобы получить более квадратные матрицы, как упоминалось в комментарии @neil-edelman. То, как вы могли бы определить худобу, могло бы заключаться в том, чтобы увидеть, является ли BND>dim(A)[1]/dim(A)[0]>bnd, где bnd и BND, некоторыми постоянными параметрами, выбранными заранее, близкими к 1.
