Fast algorithm for computing matrix multiplication!!!!

Discussion in 'C' started by asadullah.ansari, Jan 16, 2008.

  1. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Mostly people are using this algorithm to compute matrix multiplication:

    Code:
    #define n 1000
    int main()
    {
    	int a[n][n],b[n][n],c[n][n];
    	c[0][0]=0;
    	for( i=0;i<n;++i)
    	{
    		for(j=0;j<n;++j)
    		{
    			for(k=0;k<n;++k)
    			{
    				c[i][j] = c[i][j] + a[i][k] * b[k][j]
    			}
    		}
    	}
    	return 0;
    }
    
    In this program( a short algo) , every time we are taking one element of an array to catche and processing for it. Means At one time cpu reading one element value of a array and b Array and compute and store to c Array.

    To reading every time elements from array , why we are taking some group of element i.e. Block size, then no need to read every element. A groups of element will be on catche and we can do fast as given above algo. This algorithm called " Block Algorithm". This Block algorithm can be applied many place where this type of situation will come.

    Block Algorithm for Matrix Multiplication:
    Code:
    #define n 1000
    #define BlockSize  100
    int main()
    {
    	int a[n][n],b[n][n],c[n][n];
    	c[0][0]=0;
    	for( i1=0;i1<(n/BlockSize);++i1)
    	{
    		for(j1=0;j1<(n/BlockSize);++j1)
    		{
    			for(k1=0;k1<(n/BlockSize);++k1)
    			{
    				for(i=i1=0;i<min(i1+BlockSize-1);++i)
    				{
    					for(j=j1=0;j<min(j1+BlockSize-1);++j)
    					{
    						for(k=k1;k<min(k1+BlockSize-1);++k)
    						{               
    							c[i][j] = c[i][j] + a[i][k] * b[k][j]
    						}
    					}
    				}
    			}
    		}
               }
     return 0;
    }
    
     
    Last edited: Jan 16, 2008
  2. debleena_doll2002

    debleena_doll2002 New Member

    Joined:
    Feb 5, 2008
    Messages:
    119
    Likes Received:
    0
    Trophy Points:
    0
    Yes!!! But can you tell me how's senario of Catche memory here?
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    You can create a thread in the right category and it does not seem the right place.
     
  4. crazytolearn57

    crazytolearn57 New Member

    Joined:
    Feb 14, 2008
    Messages:
    48
    Likes Received:
    0
    Trophy Points:
    0
    i didnt understand
     
  5. parvez.yu

    parvez.yu New Member

    Joined:
    Feb 14, 2008
    Messages:
    100
    Likes Received:
    0
    Trophy Points:
    0
  6. aisha.ansari84

    aisha.ansari84 New Member

    Joined:
    Feb 13, 2008
    Messages:
    82
    Likes Received:
    1
    Trophy Points:
    0
    i feel its a reall nice way,good one
     
  7. alramesh

    alramesh New Member

    Joined:
    Feb 5, 2008
    Messages:
    22
    Likes Received:
    0
    Trophy Points:
    0
    i m not getting at all.
     
  8. alramesh

    alramesh New Member

    Joined:
    Feb 5, 2008
    Messages:
    22
    Likes Received:
    0
    Trophy Points:
    0
    Can you explain more about Block Algorithm?
     
  9. rahul.mca2001

    rahul.mca2001 New Member

    Joined:
    Feb 13, 2008
    Messages:
    103
    Likes Received:
    0
    Trophy Points:
    0
    what is Block Algorithm
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice