scientific article; zbMATH DE number 18296
Cholesky factorizationcomplexitydense linear systemsdistributed memory architecturesDoolittle methodGauss eliminationGauss-Jordan methodGivens factorizationgraph-theoretic methodparallel factorization algorithmsQR factorizationscheduling algorithmssequential algorithmshared memory model of computationsurvey article
Factorization of matrices (15A23) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Numerical algorithms for specific classes of architectures (65Y10) Distributed algorithms (68W15)
[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.
- Assignment and scheduling in parallel matrix factorization
- Parallel Cholesky factorization on a shared-memory multiprocessor
- scientific article; zbMATH DE number 4155892 (Why is no real title available?)
- Parallélisation de l'algorithme du chemin critique pour une machine à mémoire partagée
- Parallel two-stage reduction to Hessenberg form using dynamic scheduling on shared-memory architectures
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)