M.S. (Master of Science)
Department of Mathematical Sciences
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.
Chun, Ava A., "Symmetric eigenvalue and linear recurrence parallel algorithms for the HEP parallel computer" (1985). Graduate Research Theses & Dissertations. 5167.
x, 239 pages
Northern Illinois University
Rights Statement 2