This report provides an introduction to algorithms for fundamental linear algebra problems on various parallel computer architectures, with the emphasis on distributed-memory MIMD machines. To illustrate the basic concepts and key issues, we consider the problem of parallel solution of a nonsingular linear system by Gaussian elimination with partial pivoting. This problem has come to be regarded as a benchmark for the performance of parallel machines. We consider its appropriateness as a benchmark, its communication requirements, and schemes for data distribution to facilitate communication and load balancing. In addition, we describe some parallel algorithms for orthogonal (QR) factorization and the singular value decomposition (SVD).
翻译:本报告介绍了关于各种平行计算机结构基本线性代数问题的算法,重点是分布式模拟MIMD机器;为说明基本概念和关键问题,我们考虑了通过部分支线消除高斯清除非单线性系统平行解决的问题;这一问题已被视为平行机器性能的基准;我们认为,它作为一个基准、通信要求和数据分配计划来便利通信和负载平衡是适当的;此外,我们描述了一些正向因子化和单值分解的平行算法(SVD)。