Parallel, iterative solution of sparse linear systems: Models and architectures
type: Item
instance of: scholarly article
title: Parallel, iterative solution of sparse linear systems: Models and architectures
zbMATH Open document ID: 0599.65017
DOI: 10.1016/0167-8191(85)90017-1
author: Daniel A. Reed
author: Merrell L. Patrick
published in: Parallel Computing
publication date: 1985-01-01T00:00:00Z
full work available at URL: http://hdl.handle.net/2060/19850003278
review text: 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.
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 3967792
zbMATH Keywords: optimal partitioning
zbMATH Keywords: task allocation
zbMATH Keywords: parallel architecture
zbMATH Keywords: randomly sparse matrices
zbMATH Keywords: parallel implementation
zbMATH Keywords: data transfer probabilistic model
zbMATH Keywords: parallel iteration time
zbMATH Keywords: optimal scheduling
reviewed by: Lubomír Bakule
MaRDI profile type: Publication
OpenAlex ID: W2017561612
Recommended article: Parallel iterative methods for sparse linear systems
Recommended article: Parallel solution of arbitrarily sparse linear systems
Recommended article: Q4288588
Recommended article: Q3806672
Recommended article: Fast and Efficient Parallel Solution of Sparse Linear Systems
Recommended article: Résolution de grands systèmes linéaires creux par méthodes itératives parallèles
Recommended article: Q5750331
Recommended article: Parallel Algorithms for Sparse Linear Systems
Recommended article: Q4394583
Recommended article: Parallel Hybrid Sparse Linear System Solvers
description: scientific article; zbMATH DE number 3967792