2
$\begingroup$

Just want to check when you parallize Strassen's algorithm you get a time complexity of $O(\log n )$ because you divide and conquer $\log n$ times in parallel and a space complexity of $ O( n^{\log_2 7} ) $ because the space complexity in the parallel setting satisfies the same recursive identity as time complexity in the sequential setting.

Should be obvious but I couldn't find this by googling.

Also looking for a reference on parallel matrix algorithms.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Well, it calculates 7 products of matrices, so you can just hand each product to its own thread.

Or if you had eight cores, you could split a 8n x 8n product into 343 = 8 x 43 - 1 nxn products.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.