- 期刊
Strassen Algorithm and Its Performance
摘要
There are many algorithms developed over time for computation. Where some tend to be limited to some ranges, some tend to handle bigger problems. With the advancements in processing world, a lot of platforms have been created for computing, CUDA being one of them. CUDA is a well-known parallel computing platform developed by NVIDIA that enables developers to harness the power of GPU's in solving intensive problems. We are using CUDA to compute different mathematical matrices. Strassen's algorithm was used on CUDA to implement matrix multiplication. As we all know the phrase 'divide and conquer'. This is exactly what Strassen's algorithm does. Hence, it is a much better way of computing matrices than the standard method. The computation can be done on both CPU and GPU. On practical analysis, it was noticed that the computation of matrices of bigger sizes was much faster in GPU implementation than that of CPU implementation. Small matrices also came into account and it was found out that algorithms vary depending upon the size of the matrix. For example, when computing a 2*2 matrix multiplication, the classic method is a better method to implement. Because of this, recursions were put in the code that chooses which algorithm to implement depending upon the sizes of the matrices. Matrix multiplication using Strassen's algorithm on the CPU has a smaller recursion limit than doing the same matrix multiplication on a GPU.