scientific article; zbMATH DE number 18296

From MaRDI portal
Publication:3975665





[For the entire collection see Zbl 0729.00015.] This paper surveys about thirty papers published in the last decade on the design and analysis of parallel factorization algorithms for solving dense linear systems of algebraic equations, with restriction to shared memory model of computation (a paper by Robert in this volume taking care of distributed memory architectures), and with emphasis on theory (not including experimental results on real computers). The discussion includes a graph-theoretic approach by which the design of a parallel algorithm is separated into two independent parts, namely, (i) the construction of a task system and determination of the precedence constraints and of the task graph associated with a sequential algorithm, (ii) the construction of scheduling algorithms compatible with the task graph. Tools for analyzing parallel algorithms associated with a sequential algorithm are discussed and applied to Gauss-Jordan, several Gauss elimination algorithms, Cholesky, Doolittle and QR. The paper concludes with an investigation of the parallelization of Givens factorization and a review of some complexity results.











This page was built for publication:

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