Fast Polar Decomposition of an Arbitrary Matrix

Abstract

The polar decomposition of an $m \times n$ matrix A of full rank, where $m \geqq n$, can be computed using a quadratically convergent algorithm of Higham [SIAM J. Sci. Statist. Comput., 7(1986), pp. 1160–1174]. The algorithm is based on a Newton iteration involving a matrix inverse. It is shown how, with the use of a preliminary complete orthogonal decomposition, the algorithm can be extended to arbitrary A. The use of the algorithm to compute the positive semidefinite square root of a Hermitian positive semidefinite matrix is also described. A hybrid algorithm that adaptively switches from the matrix inversion based iteration to a matrix multiplication based iteration due to Kovarik, and to Björck and Bowie, is formulated. The decision when to switch is made using a condition estimator. This “matrix multiplication rich” algorithm is shown to be more efficient on machines for which matrix multiplication can be executed 1.5 times faster than matrix inversion.