Some P-RAM Algorithms for Sparse Linear Systems
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.
DOI: https://doi.org/10.3844/jcssp.2007.956.964
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.
- 3,289 Views
- 2,761 Downloads
- 0 Citations
Download
Keywords
- Parallel algorithms
- sparse linear systems
- cholesky method
- hypercubes
- symbolic factorization