Matrix Multiplication Algorithms
Khaled Thabet · 2012
Summary Algorithm can be written in various ways, executes sequential or parallel, and gives the same results. One of the main factors of determining the efficient of an algorithm is the execution time factor, how much time the algorithm takes to accomplish its work. Because matrix multiplication widely used in a variety of applications and is often one of the core components of many scientific computations, it will be taken as a problem in this work and different algorithms are given to solve this problem. Then the execution time of all the methods will be calculated to find the best method for matrix multiplication. After testing Twenty three methods, we find that parallel Strassen algorithm is the best method for finding matrix multiplication. Key words: Algorithm, parallel execution, matrix multiplication, Strassen algorithm. 1. Introduction Algorithm is a set of instructions for solving a problem and the efficiency of implementation of the algorithm depends upon speed, size, and resources consumption. Many instructions can give the same result for a particular problem .On the other hand, the execution of these instructions are different. Some of them take less time and space than the others. Some of them become more efficient when it executes parallel. As a result, we try to select the suitable instruction that gives the best execution, less time and space. Small Algorithms need one processor to execute efficiently and give the required result in a record time. But one processor is not enough for executing large and complex problems, so we need more than one processor to enhance the execution time of algorithm and this called parallel computing. In the simplest sense, parallel execution is the simultaneous use of multiple compute resources to solve a computational problem. Parallel execution has the following characteristics, use multiple CPUs, the problem to be solved is broken to sub problems that can be solved concurrently, each sub problem is broken down to a series of instructions and instructions from each sub problem executes simultaneously on different CPUs . The complexity of matrix multiplication has attracted a lot of attention in the last forty years. In this paper we will consider matrix multiplication as the problem, give various methods to solve this problem and find the best one that takes the least time. Matrix multiplication is the kernel of many scientific applications [8, 9]. It is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the equal to the number of rows of the right matrix B. The result of matrix multiplication is a matrix whose elements are found by multiplying the elements within a row from the first matrix by the associated elements within a column from the second matrix and summing the products. The procedure for finding an element of the resultant matrix is to multiply the first element of a given row from the first matrix times the first element of a given column from the second matrix, then add to that the product of the second element of the same row from the first matrix and the second element of the same column from the second matrix, then add the product of the third elements and so on, until the last element of that row from the first matrix is multiplied by the last element of that column from the second matrix and added to the sum of the other products. Ex: As we mentioned before there are many methods to calculate the multiplication of matrixes. All of them give the same result but each one consumes different space in memory and takes different processor time. The methods that we will test are: 1. Row by Column method 2. Row by Row method 3. Column by Column method 4. Strassen method We will test each of them with all the possible types of each one, “sequential, blocked and parallel”. The rest of this paper is organized as follows: in section II, we give a brief review of some related works about matrix multiplication, in section III we presents Row by Column method with all its type, section IV displays Row by Row