Strassen-algoritmus

Magyar

Kiejtés

IPA: [ ˈʃtrɒʃːɛnɒlɡoritmuʃ]

Főnév

(matematika, algoritmusok) A **Strassen-algoritmus** egy hatékony mátrixszorzási algoritmus, amely csökkenti a hagyományos mátrixszorzás számítási komplexitását. Hans Werner Strassen fejlesztette ki 1969-ben, és különösen nagy méretű mátrixok szorzásakor nyújt jelentős előnyt.

—

1. 1. **Hagyományos mátrixszorzás komplexitása**

Két ${\textstyle n\times n}$ -es mátrix szorzása hagyományos módszerrel ${\textstyle O(n^{3})}$ időbonyolultságú, mivel minden mátrixelem kiszámításához ${\textstyle n}$ szorzás és összeadás szükséges.

Strassen algoritmusa optimalizálja ezt a folyamatot, és a komplexitást ${\textstyle O(n^{\log _{2}7})\approx O(n^{2.81})}$ -re csökkenti.

—

1. 1. **Strassen-algoritmus működése**

1. 1. 1. **Fő ötlet** Az algoritmus a mátrixszorzást **rekurzív felbontással** végzi: 1. A két ${\textstyle n\times n}$ -es mátrixot négy ${\textstyle n/2\times n/2}$ -es blokkmátrixra bontja. 2. A ${\textstyle 7}$ al-mátrixszorzás kiszámítása után a végeredményt ezekből állítja össze, csökkentve a szükséges szorzások számát (a hagyományos ${\textstyle 8}$ -ról ${\textstyle 7}$ -re).

1. 1. 1. **Mátrixok felbontása**: Legyen ${\textstyle A}$ és ${\textstyle B}$ az ${\textstyle n\times n}$ -es mátrixok: $A={\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}}$

1. 1. 1. **Strassen-féle 7 szorzás**: A hét szorzás az alábbiak szerint történik: $M_{1}=(A_{11}+A_{22})(B_{11}+B_{22})$ $M_{2}=(A_{21}+A_{22})B_{11}$ $M_{3}=A_{11}(B_{12}-B_{22})$ $M_{4}=A_{22}(B_{21}-B_{11})$ $M_{5}=(A_{11}+A_{12})B_{22}$ $M_{6}=(A_{21}-A_{11})(B_{11}+B_{12})$ $M_{7}=(A_{12}-A_{22})(B_{21}+B_{22})$

1. 1. 1. **Végeredmény összeállítása**: A mátrix ${\textstyle C=A\cdot B}$ blokkjai az alábbi módon állnak elő: $C_{11}=M_{1}+M_{4}-M_{5}+M_{7}$ $C_{12}=M_{3}+M_{5}$ $C_{21}=M_{2}+M_{4}$ $C_{22}=M_{1}-M_{2}+M_{3}+M_{6}$

—

1. 1. **Időbonyolultság**

- **Rekurzív felosztás**: - Az algoritmus minden lépésben ${\textstyle 7}$ szorzást és ${\textstyle 18}$ összeadást/levonást végez. - **Összkomplexitás**: $T(n)=7T(n/2)+O(n^{2})$ Ez a **Master-tétel** alapján: $T(n)=O(n^{\log _{2}7})\approx O(n^{2.81})$

—

1. 1. **Példa**

1. 1. 1. **Mátrixok**: $A={\begin{bmatrix}1&2\\3&4\end{bmatrix}},\quad B={\begin{bmatrix}5&6\\7&8\end{bmatrix}}$

1. 1. 1. **Blokkok**: $A_{11}={\begin{bmatrix}1\end{bmatrix}},\quad A_{12}={\begin{bmatrix}2\end{bmatrix}},\quad A_{21}={\begin{bmatrix}3\end{bmatrix}},\quad A_{22}={\begin{bmatrix}4\end{bmatrix}}$ Hasonlóképpen feloszthatók ${\textstyle B_{11},B_{12},B_{21},B_{22}}$ .

1. 1. 1. **Strassen-módszer**: 1. Számítsuk ki a ${\textstyle M_{1},\dots ,M_{7}}$ értékeit. 2. Állítsuk össze a ${\textstyle C}$ mátrixot.

—

Python implementáció

import numpy as np

def add_matrix(A, B):
    return np.add(A, B)

def sub_matrix(A, B):
    return np.subtract(A, B)

def strassen(A, B):
    n = A.shape[0]
    if n == 1:
        return A * B
    
    k = n // 2

    # Mátrixok felosztása
    A11, A12, A21, A22 = A[:k, :k], A[:k, k:], A[k:, :k], A[k:, k:]
    B11, B12, B21, B22 = B[:k, :k], B[:k, k:], B[k:, :k], B[k:, k:]

    # Strassen-féle szorzások
    M1 = strassen(add_matrix(A11, A22), add_matrix(B11, B22))
    M2 = strassen(add_matrix(A21, A22), B11)
    M3 = strassen(A11, sub_matrix(B12, B22))
    M4 = strassen(A22, sub_matrix(B21, B11))
    M5 = strassen(add_matrix(A11, A12), B22)
    M6 = strassen(sub_matrix(A21, A11), add_matrix(B11, B12))
    M7 = strassen(sub_matrix(A12, A22), add_matrix(B21, B22))

    # Mátrix blokkok összeállítása
    C11 = add_matrix(sub_matrix(add_matrix(M1, M4), M5), M7)
    C12 = add_matrix(M3, M5)
    C21 = add_matrix(M2, M4)
    C22 = add_matrix(sub_matrix(add_matrix(M1, M3), M2), M6)

    # Mátrixok összeillesztése
    C = np.zeros((n, n))
    C[:k, :k], C[:k, k:], C[k:, :k], C[k:, k:] = C11, C12, C21, C22

    return C

# Példa használat
A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])

C = strassen(A, B)
print("A × B =")
print(C)

Kimenet:

A × B =
[[19 22]
 [43 50]]

C++ implementáció

#include <iostream>
#include <vector>

using namespace std;

using Matrix = vector<vector<int>>;

Matrix add_matrix(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            C[i][j] = A[i][j] + B[i][j];
    return C;
}

Matrix sub_matrix(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            C[i][j] = A[i][j] - B[i][j];
    return C;
}

Matrix strassen(const Matrix& A, const Matrix& B) {
    int n = A.size();
    if (n == 1) {
        return {{A[0][0] * B[0][0]}};
    }

    int k = n / 2;
    Matrix A11(k, vector<int>(k)), A12(k, vector<int>(k)),
           A21(k, vector<int>(k)), A22(k, vector<int>(k)),
           B11(k, vector<int>(k)), B12(k, vector<int>(k)),
           B21(k, vector<int>(k)), B22(k, vector<int>(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][j + k];
            A21[i][j] = A[i + k][j];
            A22[i][j] = A[i + k][j + k];
            B11[i][j] = B[i][j];
            B12[i][j] = B[i][j + k];
            B21[i][j

] = B[i + k][j];
            B22[i][j] = B[i + k][j + k];
        }
    }

    auto M1 = strassen(add_matrix(A11, A22), add_matrix(B11, B22));
    auto M2 = strassen(add_matrix(A21, A22), B11);
    auto M3 = strassen(A11, sub_matrix(B12, B22));
    auto M4 = strassen(A22, sub_matrix(B21, B11));
    auto M5 = strassen(add_matrix(A11, A12), B22);
    auto M6 = strassen(sub_matrix(A21, A11), add_matrix(B11, B12));
    auto M7 = strassen(sub_matrix(A12, A22), add_matrix(B21, B22));

    Matrix C(n, vector<int>(n));
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < k; ++j) {
            C[i][j] = M1[i][j] + M4[i][j] - M5[i][j] + M7[i][j];
            C[i][j + k] = M3[i][j] + M5[i][j];
            C[i + k][j] = M2[i][j] + M4[i][j];
            C[i + k][j + k] = M1[i][j] - M2[i][j] + M3[i][j] + M6[i][j];
        }
    }

    return C;
}

int main() {
    Matrix A = {{1, 2}, {3, 4}};
    Matrix B = {{5, 6}, {7, 8}};

    Matrix C = strassen(A, B);

    cout << "A × B = " << endl;
    for (const auto& row : C) {
        for (int val : row)
            cout << val << " ";
        cout << endl;
    }
    return 0;
}

Kimenet:

A × B =
19 22
43 50

Előnyök

Gyorsabb, mint a hagyományos módszer nagyobb mátrixok esetén.
Hatékony rekurzív algoritmus.

Hátrányok

További memóriaigény a mátrixok felosztása miatt.
Nehéz implementáció nagyobb rendszerekhez.

Alkalmazások

Nagy mátrixok szorzása gépi tanulásban, jelfeldolgozásban.
Tudományos számítások optimalizálása.

Összegzés

A Strassen-algoritmus hatékony módszer a mátrixszorzás gyorsítására, amely csökkenti a számítási költségeket nagy mátrixok esetén. Bár komplexebb, mint a hagyományos módszer, jelentős előnyt nyújt modern alkalmazásokban.

Fordítások

Tartalom

angol: Strassen algorithm (en)

További információk

Strassen-algoritmus - Értelmező szótár (MEK)
Strassen-algoritmus - Etimológiai szótár (UMIL)
Strassen-algoritmus - Szótár.net (hu-hu)
Strassen-algoritmus - DeepL (hu-de)
Strassen-algoritmus - Яндекс (hu-ru)
Strassen-algoritmus - Google (hu-en)
Strassen-algoritmus - Helyesírási szótár (MTA)
Strassen-algoritmus - Wikidata
Strassen-algoritmus - Wikipédia (magyar)