Communication-efficient parallel Bruhat decomposition

Abstract

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. Bruhat decomposition is an important method in numerical linear algebra, generalising ordinary LU decomposition while providing a symmetric structured way of expessing pivoting. Block-recursive algorithms have been developed in the past for various numerical linear algebra problems, including Bruhat decomposition; however, expressing recursive algorithms in the BSP model still remains a challenge. In this paper, we consider the communication and synchronisation complexity of Bruhat decomposition in the BSP model. We develop a new block-recursive, communication-efficient BSP algorithm for Bruhat decomposition.