Parallel Algorithms for Linear Algebra on a Shared Memory Multiprocessor

Tez Türü: Doktora

Tezin Yürütüldüğü Kurum: University of Newcastle Upon Tyne, Fen Bilimler Enstitüsü, Bilgisayar Bilimleri Bölümü, İngiltere

Tez Danışmanı: Kenneth Wright

Tezin Onay Tarihi: 1995

Tezin Dili: İngilizce

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Desteklendiği Program: YÖK 100/2000 Programı

Özet:

This thesis discusses a variety of parallel algorithms for linear algebra problems including the solution of the linear system of equations Ax = b using QR and L U decomposition, reduction of a general matrix A to Hessenberg form, reduction of a real symmetric matrix B to tridiagonal form, and solution of the symmetric tridiagonal eigenproblem. Empirical comparisons are carried out using various different versions of the above algorithms and this is described in this thesis. We also compare three different synchronisation mechanisms when applied to the reduction to Hessenberg form problem. We implement Cuppen's method for computing both eigenvalues and eigenvectors of a real symmetric tridiagonal matrix T using both recursive and non-recursive implementations. We consider parallel implementations of these versions and also consider parallelisation of the matrix multiplication part of the algorithm. We present some numerical results illustrating an experimental evaluation of the effect of deflation on accuracy, comparison of the parallel implementations and comparison of the additional parallelisation for matrix multiplication.