Алгоритм Штрассена - это алгоритм умножения матриц. Это быстрее, чем простой алгоритм умножения матриц. Чтобы узнать, как это сделать, давайте сравним оба этих алгоритма вместе с их реализацией на C ++.
Предположим, мы перемножаем 2 матрицы A и B, и обе они имеют размерность n x n. Результирующая матрица C после умножения в наивном алгоритме получается по формуле:
для i = 1,…, n и j = 1,…, n
Реализация этой формулы в C ++:
int** multiply(int** A, int** B, int n) {
int** C = initializeMatrix(n);
setToZero(C, n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
for(int k=0; k<n; k++)
C[i][j] += A[i][k] * B[k][j];
return C;
}
В этом алгоритме оператор «C [i] [j] + = A [i] [k] * B [k] [j]» »выполняется n³ раз, как видно из трех вложенных циклов for, и является наиболее затратной операцией в алгоритм. Итак, временная сложность наивного алгоритма составляет O (n³).
Теперь давайте посмотрим на алгоритм Штрассена. Алгоритм Штрассена - это рекурсивный метод умножения матриц, при котором мы делим матрицу на 4 подматрицы размеров n / 2 x n / 2 на каждом рекурсивном шаге.
Например, рассмотрим две матрицы 4 x 4 A и B, которые нам нужно умножить. Матрицу 4 x 4 можно разделить на четыре матрицы 2 x 2.
Здесь Aᵢⱼ и Bᵢⱼ - матрицы 2 x 2.
Теперь мы можем вычислить произведение A и B (матрица C) по следующим формулам:
Мне легче всего запомнить эту версию формул. Вы также можете найти руководство о том, как легко их запомнить на https://www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/
Неясно, как Штрассен пришел к этим формулам, но мы можем проверить, что они работают. Также есть условия для работы алгоритма Штрассена.
- Обе входные матрицы должны иметь размер n x n.
- n должно быть степенью 2.
Если вышеуказанные условия не выполняются, мы должны дополнить матрицы нулем, чтобы удовлетворить вышеуказанным условиям.
Теперь посмотрим на реализацию алгоритма на C ++.
Нам нужны основные матричные операции, сложение и вычитание для реализации алгоритма, поскольку мы видим, что это необходимо в формуле. Код для функций:
int** add(int** M1, int** M2, int n) {
int** temp = initializeMatrix(n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
temp[i][j] = M1[i][j] + M2[i][j];
return temp;
}
int** subtract(int** M1, int** M2, int n) {
int** temp = initializeMatrix(n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
temp[i][j] = M1[i][j] - M2[i][j];
return temp;
}
Теперь давайте реализуем функцию умножения матриц Штрассена. Нам нужно вызвать функцию StrassenMultiply рекурсивно, разделив матрицы на четыре матрицы размерности n / 2 x n / 2 и вычислить произведение, используя формулы, упомянутые ранее, чтобы умножить все матрицы. Также нам нужен базовый случай, чтобы остановить рекурсию. В базовом случае матрица имеет размерность 1 x 1 и возвращается произведение двух элементов.
Код:
Базовый вариант:
if (n == 1) {
int** C = initializeMatrix(1);
C[0][0] = A[0][0] * B[0][0];
return C;
}
Объявление C и вычисление размерности подматриц:
int** C = initializeMatrix(n); int k = n/2;
Инициализация подматриц и определение подматриц:
int** A11 = initializeMatrix(k);
int** A12 = initializeMatrix(k);
int** A21 = initializeMatrix(k);
int** A22 = initializeMatrix(k);
int** B11 = initializeMatrix(k);
int** B12 = initializeMatrix(k);
int** B21 = initializeMatrix(k);
int** B22 = initializeMatrix(k);
for(int i=0; i<k; i++)
for(int j=0; j<k; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][k+j];
A21[i][j] = A[k+i][j];
A22[i][j] = A[k+i][k+j];
B11[i][j] = B[i][j];
B12[i][j] = B[i][k+j];
B21[i][j] = B[k+i][j];
B22[i][j] = B[k+i][k+j];
}
Вычисление произведения P1 на P7 и полученной матрицы C по формулам:
int** P1 = strassenMultiply(A11, subtract(B12, B22, k), k); int** P2 = strassenMultiply(add(A11, A12, k), B22, k); int** P3 = strassenMultiply(add(A21, A22, k), B11, k); int** P4 = strassenMultiply(A22, subtract(B21, B11, k), k); int** P5 = strassenMultiply(add(A11, A22, k), add(B11, B22, k), k); int** P6 = strassenMultiply(subtract(A12, A22, k), add(B21, B22, k), k); int** P7 = strassenMultiply(subtract(A11, A21, k), add(B11, B12, k), k); int** C11 = subtract(add(add(P5, P4, k), P6, k), P2, k); int** C12 = add(P1, P2, k); int** C21 = add(P3, P4, k); int** C22 = subtract(subtract(add(P5, P1, k), P3, k), P7, k);
Копирование значений в C и возврат C
for(int i=0; i<k; i++)
for(int j=0; j<k; j++) {
C[i][j] = C11[i][j];
C[i][j+k] = C12[i][j];
C[k+i][j] = C21[i][j];
C[k+i][k+j] = C22[i][j];
}
return C;
Теперь давайте посчитаем временную сложность алгоритма с помощью мастер-метода. Алгоритм делает семь рекурсивных вызовов при вычислении от P1 до P7, поэтому a = 7. Размер входной матрицы делится на 2 при каждом рекурсивном вызове, поэтому b = 2. Работа, выполняемая вне рекурсивного вызова и слияния решений, заключается в добавлении, вычитании и копировании значений в C, который равен O (n²), поэтому d = 2.
Итак, уравнение мастера: T (n) = 7T (n / 2) + O (n²).
Это удовлетворяет условию a ›b ^ d, поэтому временная сложность алгоритма умножения матриц Штрассена составляет O (n ^ log2 (7)) = O (n ^ 2,81). Итак, алгоритм умножения матриц Штрассена асимптотически быстрее, чем наивный алгоритм.
Это может показаться незначительным улучшением, но для больших размеров ввода разница значительна. Мы можем видеть разницу на графике ниже.
Как вы можете видеть, когда входные данные становятся больше, алгоритм Штрассена показывает значительное увеличение производительности по сравнению с наивным алгоритмом. Алгоритм Штрассена также можно распараллелить, как наивный алгоритм, для дальнейшего повышения производительности.
Алгоритм умножения матриц Штрассена также имеет несколько недостатков:
- Стек рекурсии потребляет больше памяти.
- Рекурсивные вызовы увеличивают задержку.
По этим причинам наивный алгоритм является лучшим вариантом для небольших входов, которые также можно определить по графику.
Спасибо за чтение, если вы обнаружите какие-либо ошибки или у вас есть способ оптимизировать код, укажите их в комментариях, и я исправлю или внедрю их. Если вам нужна полная рабочая программа, вы можете найти код для прямого (наивного) умножения матриц и алгоритма умножения матриц Штрассена, реализованного на C ++, Java и Python, в моем репозитории на github. Ссылка приведена ниже:
