Journal of Computer Science

Some P-RAM Algorithms for Sparse Linear Systems

Rakesh Kumar Katare and N.S. Chaudhari

DOI : 10.3844/jcssp.2007.956.964

Journal of Computer Science

Volume 3, Issue 12

Pages 956-964

Abstract

PRAM algorithms for Symmetric Gaussian elimination is presented. We showed actual testing operations that will be performed during Symmetric Gaussian elimination, which caused symbolic factorization to occur for sparse linear systems. The array pattern of processing elements (PE) in row major order for the specialized sparse matrix in formulated. We showed that the access function in2+jn+k contains topological properties. We also proved that cost of storage and cost of retrieval of a matrix are proportional to each other in polylogarithmic parallel time using P-RAM with a polynomial numbers of processor. We use symbolic factorization that produces a data structure, which is used to exploit the sparsity of the triangular factors. In these parallel algorithms number of multiplication/division in O(log3n), number of addition/subtraction in O(log3n) and the storage in O(log2n) may be achieved.

Copyright

© 2007 Rakesh Kumar Katare and N.S. Chaudhari. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.