Assignment and scheduling in parallel matrix factorization
type: Item
instance of: scholarly article
title: Assignment and scheduling in parallel matrix factorization
zbMATH Open document ID: 0587.65014
DOI: 10.1016/0024-3795(86)90172-2
author: Dianne P. O'Leary
author: G. W. Stewart
published in: Linear Algebra and its Applications
publication date: 1986-01-01T00:00:00Z
review text: We consider the problem of factoring a dense \(n\times n\) matrix on a network consisting of P MIMD processors, with no shared memory, when the network is smaller than the number of elements in the matrix \((P<n^ 2)\). The specific example analyzed is a computational network that arises in computing the LU, QR, or Cholesky factorizations. We prove that if the nodes of the network are evenly distributed among processors and if computations are scheduled by a round-robin or a least-recently-executed scheduling algorithm, then optimal order of speedup is achieved. However, such speedup is not necessarily achieved for other scheduling algorithms or if the computation for the nodes is inappropriately split across processors, and we give examples of these phenomena. Lower bounds on execution time for the algorithm are established for two important node- assignment strategies.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 3942899
zbMATH Keywords: LU factorization
zbMATH Keywords: QR factorization
zbMATH Keywords: MIMD processors
zbMATH Keywords: Cholesky factorizations
zbMATH Keywords: scheduling algorithms
MaRDI profile type: Publication
full work available at URL: 0024-3795(86)90172-2
OpenAlex ID: W1982983417
cites work: Torus data flow for parallel computation of missized matrix problems
cites work: Parallel Cholesky factorization on a shared-memory multiprocessor
cites work: Q3318088
cites work: Complexity of dense-linear-system solution on a multiprocessor ring
cites work: Data-flow algorithms for parallel matrix computation
cites work: Optimal Parallel Scheduling of Gaussian Elimination DAG's
Recommended article: Q3975665
Recommended article: Task scheduling for parallel sparse Cholesky factorization
Recommended article: Q4728100
Recommended article: Implementation of some concurrent algorithms for matrix factorization
Recommended article: Computational models and task scheduling for parallel sparse Cholesky factorization
Recommended article: Q4306865
Recommended article: Q4855525
description: scientific article; zbMATH DE number 3942899