Dissertation/Thesis Abstract

Topics in communication avoiding algorithms and stability analysis
by Lowery, Bradley R., Ph.D., University of Colorado at Denver, 2014, 136; 3621837
Abstract (Summary)

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.

Indexing (document details)
Advisor: Langou, Julien
Commitee: Bennethum, Lynn, Billups, Stephen, Bosilca, George, Mandel, Jan
School: University of Colorado at Denver
Department: Applied Mathematics
School Location: United States -- Colorado
Source: DAI-B 75/10(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Mathematics, Computer science
Keywords: Balancing, Communication, Communication avoiding algorithms, Factorization, Reduce, Stability
Publication Number: 3621837
ISBN: 9781303932564
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest