Research Article Open Access

Some P-RAM Algorithms for Sparse Linear Systems

Rakesh Kumar Katare1 and N.S. Chaudhari1
  • 1 , Afganistan
Journal of Computer Science
Volume 3 No. 12, 2007, 956-964

DOI: https://doi.org/10.3844/jcssp.2007.956.964

Submitted On: 1 December 2007 Published On: 31 December 2007

How to Cite: Katare, R. K. & Chaudhari, N. (2007). Some P-RAM Algorithms for Sparse Linear Systems. Journal of Computer Science, 3(12), 956-964. https://doi.org/10.3844/jcssp.2007.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.

  • 1,076 Views
  • 1,715 Downloads
  • 0 Citations

Download

Keywords

  • Parallel algorithms
  • sparse linear systems
  • cholesky method
  • hypercubes
  • symbolic factorization