Our research focuses on a novel approach to dense and sparse linear algebra algorithms, which aims at minimizing the communication, where communication refers to both its volume and the number of messages exchanged. The main goal is to reformulate and redesign linear algebra algorithms so that they are optimal in an amount of the communication they perform, while retaining the numerical stability. In general, they reduce significantly the amount of time spent communicating, relative to conventional algorithms. The new algorithms are referred to as communication avoiding algorithms. Very often, they are based on a reformulation which expresses the operation on a block of columns of the input matrix as a reduce operation. The reduction tree influences the task dependency graph associated with the respective computation. Its choice depends on the underlying architecture.
Low Rank Approximation (LRA) algorithms usually aim to reduce the computation cost as well as storage occupation like in deep neuronal network or image compression, respectively. The idea is to approximate a matrix A of size M*N by a product of smaller matrices of size M*k and k*N where k is the rank i.e. the number of columns useful. The most accurate LRA is based on truncated Singular Values Decomposition (SVD). Unfortunately, truncated SVD is expansive. There are alternatives like QR or LU with partial pivoting. These could be good ideas but in general they give an incomplete approximation. Instead, applying RRQR or our low rank algorithm LU-CRTP with the same rank gets almost the same result and same compression as truncated SVD.