Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations

Details Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations

2011-07-05

arxiv.org/abs/1107.1127v1

Computer Science

Numerical Analysis

32 pages, to be submitted to some distributed and parallel computing journal

Scientific paper

Matrix computations, especially iterative PDE solving (and the sparse matrix vector multiplication subproblem within) using conjugate gradient algorithm, and LU/Cholesky decomposition for solving system of linear equations, form the kernel of many applications, such as circuit simulators, computational fluid dynamics or structural analysis etc. The problem of designing approaches for parallelizing these computations, to get good speedups as much as possible as per Amdahl's law, has been continuously researched upon. In this paper, we discuss approaches based on the use of finite projective geometry graphs for these two problems. For the problem of conjugate gradient algorithm, the approach looks at an alternative data distribution based on projective-geometry concepts. It is proved that this data distribution is an optimal data distribution for scheduling the main problem of dense matrix-vector multiplication. For the problem of parallel LU/Cholesky decomposition of general matrices, the approach is motivated by the recently published scheme for interconnects of distributed systems, perfect difference networks. We find that projective-geometry based graphs indeed offer an exciting way of parallelizing these computations, and in fact many others. Moreover, their applications ranges from architectural ones (interconnect choice) to algorithmic ones (data distributions).

Affiliated with

Also associated with

No associations

Rating

Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-478134