Matrix multiplication

[Zdenko]

On 4.1.2011 11:15, Ulrich Eckhardt wrote:
> Zdenko wrote:
>> Please, can anybody write me a simple recursive matrix multiplication
>> using multiple threads in Python, or at least show me some guidelines
>> how to write it myself
>
> No problem, I just need your bank account data to withdraw the payment and
> the address of your teacher whom to send the results. ;^)
>
> Seriously, things don't work like this. If you show effort, you will get
> help, but you don't get working solutions without even a bit of effort on
> your own.
>
> Start with a recursive algorithm, then make it multithreaded. Be prepared to
> make some experiments on how to distribute tasks to threads and collect
> them again.
>
> Uli
>

Ok, I expected something like this :)
Lets try this way:

I wrote these two codes for example:

this one is naive way of matrix multiplication using one thread

from random import *
from time import clock
import threading

t0 = clock()
A=[]
B=[]
C=[]
m=300  #size of matrix m x m

for i in range(m):
     A.append([])
     B.append([])
     C.append([])
     for j in range(m):
         A[i].append(randint(1,9))
         B[i].append(randint(1,9))
         C[i].append(0)

class MyThread ( threading.Thread ):

    def run ( self ):
            for i in range(m):
                 for j in range(m):
                     for k in range(m):
                         C[i][j]+=A[i][k]*B[k][j]

t=MyThread()
t.start()
t.join()
print clock() - t0, "seconds"



this one is using two threads, each one is multiplying half of matrix

import time
from threading import Thread
from random import randint

t0 = time.clock()
class MyThread(Thread):
     def __init__(self, poc, kr):
         Thread.__init__(self)
         self.poc=poc
         self.kr=kr
     def run(self):
            for i in range(self.poc,self.kr):
                 for j in range(m):
                     for k in range(m):
                         C[i][j]+=A[i][k]*B[k][j]

A=[]
B=[]
C=[]
m=300 #size of matrix m x m

for i in range(m):
     A.append([])
     B.append([])
     C.append([])
     for j in range(m):
         A[i].append(randint(1,9))
         B[i].append(randint(1,9))
         C[i].append(0)
thr1=MyThread(0,m/2)
thr2=MyThread(m/2,m)
thr1.start()
thr2.start()
thr1.join()
thr2.join()
print time.clock() - t0, "seconds"

why is second one more than twice slower than first when it should be 
faster. I suspect that problem is in simultaneous access to matrix C but 
i don't know how to solve this.

I used this just for example to see how the threading works so i can 
work on recursive and Strassen algorithm.