Randomization and the parallel solution of linear algebra problems

AbstractWe present randomized algorithms for the solution of some numerical linear algebra problems. The problems studied are the approximation of the dominant eigenvalue of a matrix, the computation of the determinist and of the rank of a matrix. The parallel cost of these methods is lower than that of the best deterministic algorithms for the same problems. In particular we show an O(log o) algorithm for the parallel computation of the determinant of matrix and an O(log n + log k) algorithm that allows to approximate the vector produced at the kth step of the power method. The “probabilistic” error is bounded in terms of the Chebyshev inequality