Strassen-algoritmus

Üdvözlöm, Ön a Strassen-algoritmus szó jelentését keresi. A DICTIOUS-ban nem csak a Strassen-algoritmus szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a Strassen-algoritmus szót egyes és többes számban mondani. Minden, amit a Strassen-algoritmus szóról tudni kell, itt található. A Strassen-algoritmus szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. AStrassen-algoritmus és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Kiejtés

  • IPA:

Főnév

Strassen-algoritmus

  1. (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. **Hagyományos mátrixszorzás komplexitása**

Két -es mátrix szorzása hagyományos módszerrel időbonyolultságú, mivel minden mátrixelem kiszámításához szorzás és összeadás szükséges.

Strassen algoritmusa optimalizálja ezt a folyamatot, és a komplexitást -re csökkenti.

      1. **Strassen-algoritmus működése**
        1. **Fő ötlet** Az algoritmus a mátrixszorzást **rekurzív felbontással** végzi: 1. A két -es mátrixot négy -es blokkmátrixra bontja. 2. A 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 -ról -re).
        1. **Mátrixok felbontása**: Legyen és az -es mátrixok:
        1. **Strassen-féle 7 szorzás**: A hét szorzás az alábbiak szerint történik:
        1. **Végeredmény összeállítása**: A mátrix blokkjai az alábbi módon állnak elő:

      1. **Időbonyolultság**

- **Rekurzív felosztás**: - Az algoritmus minden lépésben szorzást és összeadást/levonást végez. - **Összkomplexitás**: Ez a **Master-tétel** alapján:

      1. **Példa**
        1. **Mátrixok**:
        1. **Blokkok**: Hasonlóképpen feloszthatók .
        1. **Strassen-módszer**: 1. Számítsuk ki a értékeit. 2. Állítsuk össze a 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
    if n == 1:
        return A * B
    
    k = n // 2

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

    # 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, C, C, C = C11, C12, C21, C22

    return C

# Példa használat
A = np.array(, ])
B = np.array(, ])

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

Kimenet:

A × B =

 ]

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 = A + B;
    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 = A - B;
    return C;
}

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

    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 = A;
            A12 = A;
            A21 = A;
            A22 = A;
            B11 = B;
            B12 = B;
            B21[j

] = B;
            B22 = B;
        }
    }

    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 = M1 + M4 - M5 + M7;
            C = M3 + M5;
            C = M2 + M4;
            C = M1 - M2 + M3 + M6;
        }
    }

    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

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



Hátrányok

  1. További memóriaigény a mátrixok felosztása miatt.
  2. 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