Volume- 3
Issue- 6
Year- 2016
Article Tools: Print the Abstract | Indexing metadata | How to cite item | Email this article | Post a Comment
D.A.GISMALLA , MOHAMED H. A. ELHEBIR
The complexity of multiplying two matrices with the natural algorithm that of order O(ÝŠ ଷ ) has been improved to generate Stassen's algorithm to improve the complexity to be of order O( ÝŠ àªà¬ (଻)à°® ) ≈ O(ÝŠ ଶ.଼ ) using recursive procedure for divide-and –conquer algorithm[1]. Multiplication of matrices is essential when solving a large system of equation using iterative techniques or direct factorization method. For iterative technique the conjugategradient method is viewed [3]. For direct factorization of matrices, the Gram-Schmidt's with complexity (2 mÝŠ ଶ ) and Householder's algorithms with complexity (2 mÝŠ ଶ − ଶ ଷ ÝŠ ଷ ) , the MATLAB PROGRAM are given. When m and n are large it can be seen that the flops for the three algorithm Stassen , Schmidt and Householder are not differ very much while the iterative techniques specially conjugate-gradient method may be executed in a less time than the others as in [4]. If one looks deeper in these algorithms , all apply the operations to multiply two matrices. So if We reduce the number of flops for multiplication ,the efficiency for times can be achieved . To achieved such goal either to write PAREALLEL algorithms for sparse matrices or investigate LIBARAY ROUTINES IN DIFFERENT LANGUAGES But the problem with parallel computing to get more efficient programs , all must be run on SUPPER or PARALLEL computing machine which is not available to us to run problems with intensive data ,never the less beginners to parallel computing can grab a little lot of information. Here , We first , give both the Schmidt's and Householder's algorithms with Matlab Program for them. In these algorithms , all apply the operations to multiply two matrices. Second ,factorization and linear system of equations are considered with some analysis considering Cholesky factors the matrix A=LLT where L is a lower triangular matrix and the system can be solved with the forward and backward algorithm while the inverse for an upper triangular matrix is given in Fig.(3)for the file INV_LOWER.m Third, sparse matrices representation as Compressed Sparse Column format CSC and Compressed Sparse Row format CSR will be given with an algorithm to multiply two matrices as in Fig.(6. ). Fourth, parallelism and multination of matrices algorithm such as FOX'S algorithm and CUDA program are given in Fig.(10) &Fig.(11), respectively. Multiple approaches to demonstrate Parallelism on matrices and solve a system of equation are given in section IV part C . Finally computational remarks are given .
[1] Aho|Hopcroft|Ullman . The Design and Analysis of Computer Algorithms.Addison-Wesley Publishing Company,1974
[2] E.Horowitz &S. Sahni, Fundamental of Data Structures. PITMANN PUBLISHING Limited ,1977
[3] D.A.Gismalla , Matlab Software for Iterative Methods and Algorithms to Solve a Linear System , International Journal of Engineering and Technical Research (IJETR) , ISSN :2321-0869,Volume-2 Issue-2, Februray 2014 http://www.erpublication.org/IJETR/vol_issue.php?abc1= 20
[4] Akshay Panajwar,Prof.M.A.Shah Efficient Solver for Linear Algebraic Equations on Parallel Architecture using MPI . 6th International Conference on Computer Science and Information Technology (ICCIT 2015) ISBN: 978- 93- 85225-32-1, 31st May 2015, Pune
[5] Working with Distributed Arrays . Boston University Information Sciences &Technology http://www.bu.edu/tech/support/research/trainingconsulting/online-tutorials/matlab-pct/distributed-arrayexamples
[6] Implicit Parallelism (Multithreading).Boston University Information Sciences & Technology http://www.bu.edu/tech/support/research/trainingconsulting/online-tutorials/matlab-pct/implicit-parallelism
[7] Parallel and GPU Computing Tutorials https://www.mathworks.com/videos/parallel-computingtutorial-deeper-insights-into-using-parfor-4-of-9- 91566.html
[8] Working with Codistributed Arrays https://www.mathworks.com/help/distcomp/workingwith-codistributed-arrays.html#bqjuvpl
[9] SuiteSparse is a Suite for Sparse Matrices Algogithm http://www.cise.ufl.edu/research/sparse
[9] Configuring the MATLAB Parallel Computing Toolbox at OSC | Ohio https://www.osc.edu/research/hll/matlab
[10] [Parallel MATLAB: Single Program Multiple Data - Interdisciplinary www.icam.vt.edu/Computing/fdi_2012_spmd.pdf
[11] Mondriaan for sparse matrix partitioning http://www.staff.science.uu.nl/~bisse101/Mondriaan/
Faculty of Mathematics & Computer Sciences , Gezira University Wad Medani,P.O.Box 20 , SUDAN
No. of Downloads: 6 | No. of Views: 761
D.A.GISMALLA, OHAMED H.A.ELHEBER .
January 2017 - Vol 4, Issue 1