Assignment and scheduling in parallel matrix factorization

DOI10.1016/0024-3795(86)90172-2MaRDI QIDQ1072330zbMATH OpenOpenAlexFDO

Authors Dianne P. O'Leary, G. W. Stewart

Publication date 1986

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(86)90172-2

zbMATH Keywords

Cholesky factorizationsLU factorizationMIMD processorsQR factorizationscheduling algorithms

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Deterministic scheduling theory in operations research (90B35)

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.

Recommendations

• scientific article; zbMATH DE number 18296
• Task scheduling for parallel sparse Cholesky factorization
• scientific article; zbMATH DE number 4003353
• Implementation of some concurrent algorithms for matrix factorization
• Computational models and task scheduling for parallel sparse Cholesky factorization
• scientific article; zbMATH DE number 641618
• scientific article; zbMATH DE number 815482

Cites work

• Complexity of dense-linear-system solution on a multiprocessor ring
• Data-flow algorithms for parallel matrix computation
• scientific article; zbMATH DE number 3848585 (Why is no real title available?)
• Optimal Parallel Scheduling of Gaussian Elimination DAG's
• Parallel Cholesky factorization on a shared-memory multiprocessor
• Torus data flow for parallel computation of missized matrix problems

Cited in

(7)

• Avoiding the square-root bottleneck in the Choleski factorization of a matrix on a parallel computer
• Independent set orderings for parallel matrix factorization by Gaussian elimination
• scientific article; zbMATH DE number 18296 (Why is no real title available?)
• scientific article; zbMATH DE number 720649 (Why is no real title available?)
• A parallel boundary element formulation for determining effective properties of heterogeneous media
• scientific article; zbMATH DE number 278837 (Why is no real title available?)
• Task scheduling for parallel sparse Cholesky factorization

This page was built for publication: Assignment and scheduling in parallel matrix factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072330)