Matrix Project - Report Example

Matrix Project By Matrix Project Introduction The problem is to write a program that enables basic matrix arithmetic operations. The application developed in this case is able to generate two random matrices X (A, B) and Y (B, C), and allow basic matric operations such as multiplication using, first, the Strassen’s algorithm, and a sequential method, resulting in matrix Z (A, C). Then, the application is able to parallelize the two matrices and compare the results of the two different multiplications in order to ensure that they match. In general, algorithms that are run in, while Strassen’s Algorithm run in time, often takes the flowing 7th recursive divide and conquer technique (Storer 2001: 169-170), in which the matrices X and Y are divided into four different quarters and their seven factors computed; then, they are combined in four parts to result in matrix Z. In this application, the algorithms are described as below: Let X, Y be two square matrices inside a ring W. The goal in this case is to compute the matrix product Z as Thus, in case the matrices X and Y are not square matrices, there will be a need to fill the missing columns and rows with zeros. Matrices X, Y, and Z, are thus partitioned into equally sized block matrices ], , ] Having Then, Even with this design, the number of multiplications have not reduced, 8 multiplications are still required to calculate the matrices; this is just the same as the number of multiplications required when the standard matrix multiplication method is used (Scheinerman 2006: 278). An important part, thus, is to define new matrices as below. These are then used to express the product matrix in terms of. Due to how the product matrix has been defined, it is easy to eliminate one matrix multiplication and thus decrease the number of multiplications required to just 7, one for every, and express as Then, the process of division is then iterated n times until the sub-matrices result into elements of the ring W. It is important to note that the Strassen’s algorithm can be efficiently implemented when carrying out multiplication of small sub-matrices using standard matric multiplication techniques. Numerical Analysis Standard matrix multiplication often takes roughly (in which ) additions and multiplications. The number of multiplications and additions that are needed in the Stressen Algorithm can be calculated by considering the function (n) to be the number of required operations for any random matrix (Stoller & Bennett 2014: 77). Then, by applying the Strassen Algorithm recursively, it can be seen that f(n) = 7f(n− d) + l4n for a given constant d which depends on the number of additions carried out at every point of application of the algorithm. However, reducing the number of multiplications and additions required comes at the expense of a reduced numerical stability. The code for performing random matrix multiplication using the Strassen’s algorithm //seven factors to be added or subtracted are recorded double **M1, **M2, **M3, **M4, **M5, **M6, **M7; //division of the two matrices X and Y double **X11, **X12, **X21, **X22; double **Y11, **Y12, **Y21, **Y22; //storing the middle variables double **kXM1, **kYM1,**kXM2,**kYM2,**kXM3, **kYM3,**kXM4, **kYM4,**kXM5, **kYM5,**kXM6, **kYM6,**kXM7,**kYM7 //main code StrassenMMult(): if ((ad-aw)*(bd-bw)*(cd-cw) < GRAIN) matmultleaf(ad,aw,bd,bw,cd,cw,X,Y,Z); else { //M1=(X11 + X22)*(Y11 + Y22) AddMatBlocks(kXM1,a2,b2, X11,X22); AddMatBlocks(kYM1,b2,c2,Y11,Y22); strassenMMult(0,a2,0,c2,0,b2,kXM2,Y11,M2); //M2=(X21 + X22)*Y11 AddMatBlocks(kXM2,a2,b2,X21,X22); strassenMMult(0,a2,0,c2,0,b2,kXM2,X11,M2); //M3=X11*(Y12-Y22) SubMatBlocks(kYM3,b2,c2,Y12,Y22); strassenMMult(0,a2,0,c2,0,b2,X11,kYM3,M3); //M4=X22*(Y21-Y11) SubMatBlocks(kYM4,b2,c2,Y21,Y11); strassenMMult(0,a2,0,c2,0,b2,X22,kYM4,M4); //M5=(X11+X12)*Y22 AddMatBlocks(kXM5,a2,b2,X11,X12); strassenMMult(0,a2,0,c2,0,b2,kXM5,Y22,M5); //M6=(X21-X11)*(Y11+Y12) SubMatBlocks(kXM6,a2,b2,X21,X11); AddMatBlocks(kYM6,b2,c2,Y11,Y12); strassenMMult(0,a2,0,c2,0,b2,kXM6,kYM6,M6); //M7=(X12-X22)*(Y21+Y22) SubMatBlocks(kXM7,a2,b2,X12,X22); AddMatBlocks(kYM7,b2,c2,Y21,Y22); strassenMMult(0,a2,0,c2,0,b2,kXM7,kYM7,M7); for (int i=0; i Read More