Some P-RAM Algorithms for Sparse Linear Systems | Science Publications

Journal of Computer Science

Rakesh K. Katare¹  N. S. Chaudhari¹ 

关键词: Parallel algorithms;    sparse linear systems;    cholesky method;    hypercubes;    symbolic factorization;   

DOI  :  10.3844/jcssp.2007.956.964

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

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 in²+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(log³n), number of addition/subtraction in O(log³n) and the storage in O(log²n) may be achieved.

【 授权许可】

Unknown