Thread: recursive Strassens Algorithm Problem

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    114

    recursive Strassens Algorithm Problem

    I am trying to multiply two matrix whose order is power of 2 using strassens algorithm,The problem I am facing is,when the base case is hit, I always have to keep the base case half of the order, or else i wont work, heres my code
    Code:
    #include <iostream>
    
    using namespace std;
    
    void Add(int **A,int **B,int **C,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;
    
    }
    
    
    void subtract(int **A,int **B,int **C,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;
    }
    
    void AB(int **A,int **B,int **C,int n)
    {
       for(int i=0;i<n;++i)
       {
        for(int j=0;j<n;++j)
        {
          C[i][j]=0;
         for(int k=0;k<n;++k)
            C[i][j]+=A[i][k]*B[k][j];
        }
    
       }
    }
    
    
    
    
    
    
    void strassen(int **A,int **B,int **C,int n)
    {
        /*
         if(n==1)
         {
         C[0][0]=A[0][0]*B[0][0];
         return;
         }
        */
        if(n<=2)
        {
            AB(A,B,C,n);
            return;
        }
    
    
         int s=n/2;
         int **A11=new int*[s];
         int **A12=new int*[s];
         int **A21=new int*[s];
         int **A22=new int*[s];
    
    
         int **B11=new int*[s];
         int **B12=new int*[s];
         int **B21=new int*[s];
         int **B22=new int*[s];
    
         int **C11=new int*[s];
         int **C12=new int*[s];
         int **C21=new int*[s];
         int **C22=new int*[s];
    
         for(int i=0;i<s;++i)
         {
            A11[i]=new int[s];
            A12[i]=new int[s];
            A21[i]=new int[s];
            A22[i]=new int[s];
    
    
            B11[i]=new int[s];
            B12[i]=new int[s];
            B21[i]=new int[s];
            B22[i]=new int[s];
    
    
    
            C11[i]=new int[s];
            C12[i]=new int[s];
            C21[i]=new int[s];
            C22[i]=new int[s];
    
    
    
         }
    
         for(int i=0;i<s;++i)
         {
               for(int j=0;j<s;++j)
               {
                   A11[i][j]=A[i][j];
                   A12[i][j]=A[i][j+s];
                   A21[i][j]=A[i+s][j];
                   A22[i][j]=A[i+s][j+s];
    
    
                   B11[i][j]=A[i][j];
                   B12[i][j]=A[i][j+s];
                   B21[i][j]=A[i+s][j];
                   B22[i][j]=A[i+s][j+s];
    
    
               }
    
    
         }
    
    
         int **s1=new int*[s];
         int **s2=new int*[s];
         int **s3=new int*[s];
         int **s4=new int*[s];
         int **s5=new int*[s];
         int **s6=new int*[s];
         int **s7=new int*[s];
         int **s8=new int*[s];
         int **s9=new int*[s];
         int **s10=new int*[s];
         int **p1=new int*[s];
         int **p2=new int*[s];
         int **p3=new int*[s];
         int **p4=new int*[s];
         int **p5=new int*[s];
         int **p6=new int*[s];
         int **p7=new int*[s];
    
         for(int i=0;i<s;++i)
         {
          s1[i]=new int[s];
         s2[i]=new int[s];
         s3[i]=new int[s];
         s4[i]=new int[s];
         s5[i]=new int[s];
         s6[i]=new int[s];
         s7[i]=new int[s];
         s8[i]=new int[s];
         s9[i]=new int[s];
         s10[i]=new int[s];
           p1[i]=new int[s];
         p2[i]=new int[s];
         p3[i]=new int[s];
         p4[i]=new int[s];
         p5[i]=new int[s];
         p6[i]=new int[s];
         p7[i]=new int[s];
    
         }
         subtract(B12,B22,s1,s);
         subtract(B21,B11,s4,s);
         subtract(A12,A22,s7,s);
         subtract(A11,B21,s9,s);
         Add(A11,A12,s2,s);
         Add(A21,A22,s3,s);
         Add(A11,A22,s5,s);
         Add(B11,B22,s6,s);
         Add(B21,B22,s8,s);
         Add(B11,B12,s10,s);
    
    
        strassen(A11,s1,p1,s);
        strassen(s2,B22,p2,s);
        strassen(s3,B11,p3,s);
        strassen(A22,s4,p4,s);
        strassen(s5,s6,p5,s);
        strassen(s7,s8,p6,s);
        strassen(s9,s10,p7,s);
    
    
        Add(p5,p4,C11,s);
        subtract(C11,p2,C11,s);
        Add(C11,p6,C11,s);
    
        Add(p1,p2,C12,s);
    
        Add(p3,p4,C21,s);
    
        Add(p5,p1,C22,s);
        subtract(C22,p3,C22,s);
        subtract(C22,p3,C22,s);
    
        for(int i=0;i<s;++i)
        {
            for(int j=0;j<s;++j)
            {
                C[i][j]=C11[i][j];
                C[i][j+s]=C12[i][j];
                C[i+s][j]=C21[i][j];
                C[i+s][j+s]=C22[i][j];
            }
            delete C11[i];
            delete C12[i];
            delete C21[i];
            delete C22[i];
    
            delete A11[i];
            delete A12[i];
            delete A21[i];
            delete A22[i];
    
            delete B11[i];
            delete B12[i];
            delete B21[i];
            delete B22[i];
    
            delete s1[i];
            delete s2[i];
            delete s3[i];
            delete s4[i];
            delete s5[i];
            delete s6[i];
            delete s7[i];
            delete s8[i];
            delete s9[i];
            delete s10[i];
    
           delete p1[i];
           delete p2[i];
           delete p3[i];
           delete p4[i];
            delete p5[i];
           delete p6[i];
           delete p7[i];
    
        }
    
             delete C11;
            delete C12;
            delete C21;
            delete C22;
    
            delete A11;
            delete A12;
            delete A21;
            delete A22;
    
            delete B11;
            delete B12;
            delete B21;
            delete B22;
    
            delete s1;
            delete s2;
            delete s3;
            delete s4;
            delete s5;
            delete s6;
            delete s7;
            delete s8;
            delete s9;
            delete s10;
    
           delete p1;
           delete p2;
           delete p3;
           delete p4;
            delete p5;
           delete p6;
           delete p7;
    
    
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    int main()
    {
    int n;
    cin>>n;
    int **A=new int*[n],**B=new int*[n],**C=new int*[n];
    for(int i=0;i<n;++i)
    {
        A[i]=new int[n];
        B[i]=new int[n];
        C[i]=new int[n];
    }
    
    for(int i=0;i<n;++i)
    {
         for(int j=0;j<n;++j)
             A[i][j]=B[i][j]=C[i][j]=j+1;
    }
    
    strassen(A,B,C,n);
    
    
    for(int i=0;i<n;++i)
    {
     for(int j=0;j<n;++j)
         cout<<C[i][j]<<" ";
     cout<<endl;
    }
    
    
    for(int i=0;i<n;++i)
    {
        delete A[i];
        delete B[i];
        delete C[i];
    }
    
    
    
    }

    Now if my input matrix is n, than I must have the base case<=n/2 or else it is giving different result. Can someone help?
    for convenience
    Multiplication of
    1 2 3 4 1 2 3 4 10 20 30 40
    1 2 3 4 * 1 2 3 4= 10 20 30 40
    1 2 3 4 1 2 3 4 10 20 30 40
    1 2 3 4 1 2 3 4 10 20 30 40

    I have followed every step of strassens algorithm.. still wrong

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    I'm not familiar with the algorithm myself, but what I can tell you that your programming methodologies are about as unsafe and bug prone as imaginable.

    (1) Never use the "new" operator unless you're assigning the result directly to the constructor of a "smart pointer" object. Note: conveniently, this will also rid you of the need for the explicit "delete" calls.
    (2) Stop using arrays! std::array, std::vector, and the like aren't just safer - they're much easier to use! You won't have to manage memory, and all of the size info and such is readily accessible.
    (3) Eventually you should move towards using templates instead of hard-coded data types. Just a suggestion, of course.

    Also bear in mind that getting (1) and (2) down is pretty much essential if you expect anyone here to help you - few will want to wade through hundreds of lines of buggy container management code just to inspect a simple algorithm...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81
    In practice, the Strasen algorithm provides only a small improvement in the number of operations, its complexity is O(N^2.807), where N is the size of the NXN matrix, instead of the usual O(N^3) operations. In practice, not only there is only a 10 % improvement in execution speed, but this is only after the matrices have size at least 1,000. Three decades ago before my sophomore year I tried to understand Strassen's algorithm, but since then I have never looked at it.

    I assume that this is a homework assignment in a course, and so you are forced to complete this project, but overall you will probably never have to use this algorithm in real life, unless you are trying to improve it further as your specialty. There has been some new progress that improves the complexity to O(N^2.3727), and there are hopes that the complexity can one day be reduced to O(N^2), but I suspect that if and when this is done, it will probably require very large matrices to be effective.
    Last edited by FortranLevelC++; 06-05-2013 at 11:22 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. deleting a node in a recursive way algorithm..
    By cfan in forum C Programming
    Replies: 10
    Last Post: 08-02-2009, 03:15 AM
  2. subset recursive algorithm
    By transgalactic2 in forum General Discussions
    Replies: 15
    Last Post: 07-22-2009, 10:28 PM
  3. Help with recursive algorithm
    By rafael_josem in forum C Programming
    Replies: 4
    Last Post: 09-04-2006, 06:50 PM
  4. recursive algorithm
    By vienne in forum C Programming
    Replies: 4
    Last Post: 07-18-2004, 06:03 PM
  5. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM

Tags for this Thread