Scribd Logo
Upload

Welcome to Scribd!

  • 4K views

    Strassen's Matrix Multiplication

    Uploaded by

    api-3745527
    This document discusses Strassen's algorithm for matrix multiplication. It begins by explaining basic matrix multiplication, which takes O(N3) time. Strassen showed that 2x2 matrix multiplication can be done in 7 multiplications instead of 8, reducing the time complexity. Strassen's algorithm uses divide and conquer approach to recursively break down matrices into smaller sub-matrices and multiply them using fewer operations than basic multiplication. This reduces the time complexity of matrix multiplication to O(N^log27) ≈ O(N2.807), better than the O(N3) of basic multiplication.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Strassen's Matrix Multiplication

    Uploaded by

    api-3745527
    4K views12 pages
    This document discusses Strassen's algorithm for matrix multiplication. It begins by explaining basic matrix multiplication, which takes O(N3) time. Strassen showed that 2x2 matrix multiplication can be done in 7 multiplications instead of 8, reducing the time complexity. Strassen's algorithm uses divide and conquer approach to recursively break down matrices into smaller sub-matrices and multiply them using fewer operations than basic multiplication. This reduces the time complexity of matrix multiplication to O(N^log27) ≈ O(N2.807), better than the O(N3) of basic multiplication.

    Original Title

    Strassen's Matrix Multiplication[1]

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses Strassen's algorithm for matrix multiplication. It begins by explaining basic matrix multiplication, which takes O(N3) time. Strassen showed that 2x2 matrix multiplication can be done in 7 multiplications instead of 8, reducing the time complexity. Strassen's algorithm uses divide and conquer approach to recursively break down matrices into smaller sub-matrices and multiply them using fewer operations than basic multiplication. This reduces the time complexity of matrix multiplication to O(N^log27) ≈ O(N2.807), better than the O(N3) of basic multiplication.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    4K views12 pages

    Strassen's Matrix Multiplication

    Uploaded by

    api-3745527
    This document discusses Strassen's algorithm for matrix multiplication. It begins by explaining basic matrix multiplication, which takes O(N3) time. Strassen showed that 2x2 matrix multiplication can be done in 7 multiplications instead of 8, reducing the time complexity. Strassen's algorithm uses divide and conquer approach to recursively break down matrices into smaller sub-matrices and multiply them using fewer operations than basic multiplication. This reduces the time complexity of matrix multiplication to O(N^log27) ≈ O(N2.807), better than the O(N3) of basic multiplication.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 12

    Strassen's Matrix

    Multiplication

    THAMARAISELVI.J
    Basic Matrix Multiplication

    Suppose we want to multiply two matrices of size N


    x N: for example A x B = C.

    C11 = a11b11 + a12b21

    C12 = a11b12 + a12b22

    C21 = a21b11 + a22b21 2x2 matrix multiplication can be


    accomplished in 8 multiplication.(2log28 =23)
    C22 = a21b12 + a22b22
    Basic Matrix Multiplication
    void matrix_mult (){
    for (i = 1; i <= N; i++) { algorithm

    for (j = 1; j <= N; j++) {


    compute Ci,j;
    }
    N
    }}
    Ci , j = ∑ ai ,k bk , j
    Time k =1
    N N N
    analysis Thus T ( N ) = ∑∑∑ c = cN 3 = O ( N 3 )
    i =1 j =1 k =1
    Strassens’s Matrix
    Multiplication

    Strassen showed that 2x2 matrix multiplication


    can be accomplished in 7 multiplication and 18
    additions or subtractions. .(2log27 =22.807)

    This reduce can be done by Divide and Conquer


    Approach.
    Divide-and-Conquer
    Divide-and conquer is a general algorithm design
    paradigm:
     Divide: divide the input data S in two or more disjoint
    subsets S1, S2, …
     Recur: solve the subproblems recursively
     Conquer: combine the solutions for S1, S2, …, into a
    solution for S
    The base case for the recursion are subproblems of
    constant size
    Analysis can be done using recurrence equations
    Divide and Conquer Matrix Multiply
    A × B = R

    A0 A1 B0 B1 A0×B0+A1×B2 A0×B1+A1×B3
    × =
    A2 A3 B2 B3 A2×B0+A3×B2 A2×B1+A3×B3

    •Divide matrices into sub-matrices: A0 , A1, A2 etc


    •Use blocked matrix multiply equations
    •Recursively multiply sub-matrices
    Divide and Conquer Matrix Multiply
    A × B = R

    a0 × b0 = a0 × b0

    • Terminate recursion with a simple base case


    Strassens’s Matrix Multiplication

    P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7


    P2 = (A21 + A22) * B11 C12 = P3 + P5
    P3 = A11 * (B12 - B22) C21 = P2 + P4
    P4 = A22 * (B21 - B11) C22 = P1 + P3 - P2 + P6
    P5 = (A11 + A12) * B22
    P6 = (A21 - A11) * (B11 + B12)
    P7 = (A12 - A22) * (B21 + B22)
    Comparison

    C11 = P1 + P4 - P5 + P7
    = (A11+ A22)(B11+B22) + A22 * (B21 - B11) - (A11 + A12) * B22+
    (A12 - A22) * (B21 + B22)
    = A11 B11 + A11 B22 + A22 B11 + A22 B22 + A22 B21 – A22 B11 -

    A11 B22 -A12 B22 + A12 B21 + A12 B22 – A22 B21 – A22 B22
    = A11 B11 + A12 B21
    Strassen Algorithm
    void matmul(int *A, int *B, int *R, int n) {
    if (n == 1) {
    (*R) += (*A) * (*B);
    } else {
    matmul(A, B, R, n/4);
    matmul(A, B+(n/4), R+(n/4), n/4);
    matmul(A+2*(n/4), B, R+2*(n/4), n/4);
    matmul(A+2*(n/4), B+(n/4), R+3*(n/4), n/4);
    matmul(A+(n/4), B+2*(n/4), R, n/4);
    matmul(A+(n/4), B+3*(n/4), R+(n/4), n/4);
    matmul(A+3*(n/4), B+2*(n/4), R+2*(n/4), n/4);
    matmul(A+3*(n/4), B+3*(n/4), R+3*(n/4), n/4); Divide matrices in
    }
    sub-matrices and
    recursively multiply
    sub-matrices
    Time Analysis
    THANK ‘U’

    You might also like