title: Scalable and fault tolerant orthogonalization based on randomized distributed data aggregation.
abstract: The construction of distributed algorithms for matrix computations built on top of distributed data aggregation algorithms with randomized communication schedules is investigated. For this purpose, a new aggregation algorithm for summing or averaging distributed values, the push-flow algorithm, is developed, which achieves superior resilience properties with respect to failures compared to existing aggregation methods. It is illustrated that on a hypercube topology it asymptotically requires the same number of iterations as the optimal all-to-all reduction operation and that it scales well with the number of nodes. Orthogonalization is studied as a prototypical matrix computation task. A new fault tolerant distributed orthogonalization method rdmGS, which can produce accurate results even in the presence of node failures, is built on top of distributed data aggregation algorithms.
authors.affiliation: University of Vienna, Research Group Theory and Applications of Algorithms, Währinger Straße 29, A-1090 Vienna, Austria.
authors.forename: Wilfried N
authors.initials: WN
authors.lastname: Gansterer
authors.affiliation: University of Vienna, Research Group Theory and Applications of Algorithms, Währinger Straße 29, A-1090 Vienna, Austria.
authors.forename: Gerhard
authors.initials: G
authors.lastname: Niederbrucker
authors.affiliation: University of Vienna, Research Group Theory and Applications of Algorithms, Währinger Straße 29, A-1090 Vienna, Austria.
authors.forename: Hana
authors.initials: H
authors.lastname: Straková
authors.affiliation: University of Vienna, Research Group Theory and Applications of Algorithms, Währinger Straße 29, A-1090 Vienna, Austria.
authors.forename: Stefan
authors.initials: S
authors.lastname: Schulze Grotthoff
keywords: Distributed matrix computations; Distributed orthogonalization; Distributed reduction operation; Fault tolerant matrix computations; Push-flow algorithm