Ava A. Chun

Publication Date

1985

Document Type

Dissertation/Thesis

First Advisor

Datta, Karabi

Degree Name

M.S. (Master of Science)

Legacy Department

Department of Mathematical Sciences

LCSH

Algorithms; Eigenvalues

Abstract

The parallel QR algorithm of Datta (with and without shifting and deflation), the parallel QR algorithm of Sameh and Kuck (with and without shifting and deflation), the parallel bisection algorithm (with tolerance values 0.1E-06 and 0.1E-12), the second-order linear recurrence parallel algorithm of Sameh and Kuck and the modified linear recurrence algorithm of Sameh and Kuck are evaluated in this study. The objective of this study is to determine the class of algorithms that maximizes speedup, minimizes computation time, maximizes efficiency, maximizes effectiveness and gives the most accurate solution on the HEP MIMD computer. The results of the experiments show that algorithms with large-grain parallel structure, such as the parallel bisection algorithm and the modified linear recurrence algorithm of Sameh and Kuck, give better speedup, efficiency and effectiveness. However, a parallel algorithm structure alone does not guarantee least execution time. A part sequential, part parallel structured algorithm, such as the parallel QR algorithm of Sameh and Kuck with shifting and deflation and the linear recurrence algorithm of Sameh and Kuck, may give least execution time, if it has the least total operation count per process. Therefore, the class of algorithms that is most ideally suited for the HEP is the one that has a large-grain parallel algorithm structure and has the least total operation count per process. The parallel bisection algorithm with a tolerance value of 0.1E-12 gives the most accurate solution and ranks third, in terms of minimum execution time. If minimum execution time can be compromised for accuracy of solutions, better speedup, better efficiency and more effectiveness, then the bisection algorithm with a very small tolerance value is a good choice.

Comments

Bibliography: pages [162] - 163.

Extent

x, 239 pages

Language

eng

Publisher

Northern Illinois University

Rights Statement

In Copyright

Rights Statement 2

NIU theses are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.

Media Type

Text

Download

Share

COinS