High performance linear algebra kernels are essential for scientific computing. Fast, accurate, and robust algorithms are required to process the large amount of data present in today's applications. In this thesis, we present new performance analysis, new error analysis, new stable algorithms, and new computational results.
An algorithm's performance depends on the computational cost and the communication cost. We begin with a study of the communication cost for dense linear algebra algorithms. We improve the lower bounds for the amount of communications in matrix multiplication. We also review optimal algorithms for dense linear algebra algorithms focusing on recursive algorithms.
We also consider the communication cost of the reduction operation. A reduction is a collective communication that is often used to communicate data in a parallel application. We present two new algorithms each developed under different models. In a unidirectional model, we prove our new algorithm is optimal. In a bidirectional model, we show experimentally our new algorithm has the same time complexity of a reverse optimal broadcast. Our implementations show that the new algorithms are viable options in practice.
In the remaining chapters, we turn our attention to error analysis. We present a complete error analysis study of computing an oblique QR factorization. As part of this study we introduce a new, stable, communication avoiding algorithm. Performance experiments confirm the benefit of the communication avoiding algorithms.
Finally, we consider the error due to the balancing algorithm, a preprocessing step to the nonsymmetric eigenvalue problem. We modify the balancing algorithm by improving its stopping criteria. We present several test cases where the previous balancing algorithm deteriorated the accuracy of the computation. The new algorithm successfully maintains satisfactory backward error for all test cases.
|Commitee:||Bennethum, Lynn, Billups, Stephen, Bosilca, George, Mandel, Jan|
|School:||University of Colorado at Denver|
|School Location:||United States -- Colorado|
|Source:||DAI-B 75/10(E), Dissertation Abstracts International|
|Subjects:||Mathematics, Computer science|
|Keywords:||Balancing, Communication, Communication avoiding algorithms, Factorization, Reduce, Stability|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be