Power iteration with probabilistic updates for systems with heterogeneous performance

This paper presents a probabilistic update model for the computation of the dominant eigenpair of a symmetric matrix via the power iteration algorithm. Each index of the approximate dominant eigenvector is updated according to a fixed probability, and at any given iteration, the update decision is guided by a Bernoulli trial with success probability equal to the update probability. Such probabilistic or stochastic models of the power iteration algorithm can model uncertainties in the update of the approximate eigenvector resulting either from faults during matrix-vector product computations or straggling in public cloud servers. In this paper we present an analysis of power iteration with probabilistic updates from a heterogeneous performance perspective, discuss practical details, and illustrate its performance on a set of matrix problems.