Parallel, iterative solution of sparse linear systems: Models and architectures (Q1080616)

Consider a system \(Kx=f\) (rewritten into the form \(x=Ax+c)\), where K,A are large \(N\times N\) randomly sparse matrices, x,f,c are N-vectors. Its solution is computed using the iterative formula \(x^{(i+1)}=Ax^{(i)}+c\) by partitioning into sets of rows and followed by parallel implementation of the computation. A data transfer probabilistic model is derived. It is used to construct an execution time model for predicting the parallel iteration time, the optimal number of partitions and the costs of computation, communication and synchronization. The allocation of tasks to the processors of parallel architecture is considered: The optimal scheduling which is NP-complete, and the broadcast bus architecture where scheduling is not needed. Optimistic and pessimistic matrix iteration performance models of the broadcast bus architecture are analyzed as a function of matrix sparsity and the costs of computation, communication and synchronization.