STUDY OF TOPOLOGICAL PROPERTY OF INTERCONNECTION NETWORKS AND ITS MAPPING TO SPARSE MATRIX MODEL
Rakesh Kumar Katare, Narendra S. Chaudhari · 2009
Sparse matrix elements on hypercube and perfect difference network have been studied. Gaussian symmetric factorization algorithm is being used to map the matrix on these two architectural topologies. A comparative study of hypercube and perfect difference network is done on the basis of topological properties. It has been shown that the access function or routing function contains topological properties. It has also been proved that the perfect difference network is not an instance of the generalized hypercube. A matrix multiplication algorithm using PDN has also been given in this paper. The complexity of these algorithm is O(log 3 n). Parallel algorithms for the symbolic factorization and triangular factor for sparse linear systems have also been demonstrated. Here we are using P-RAM model for the mapping of sparse matrix on interconnection networks. P-RAM model is a shared memory model and this model will survive as a theoretical convenient model of parallel computation and will used as a starting point for a methodology.