FACTORIZATION, MULTIPLICATION AND VIEWS ON PARALLEL FOR SPARE MATRICES

D.A.GISMALLA , MOHAMED H. A. ELHEBIR

Abstract

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 .