A lower bound on the computational complexity of the QR decomposition on a shared memory SIMD computer

The time complexity of the Greedy algorithm is investigated. This algorithm provides the parallel QR decomposition of a dense rectangular matrix, through Givens rotations, and it is the optimal procedure within the class of parallel algorithms. The study is carried out analyzing the dynamical evolution of the Greedy automation that we introduce. The known lower bounds for the number of steps required by the Greedy algorithm, for the square matrix case, are improved.