AN IMPROVED DQDS ALGORITHM

Abstract. In this paper we present an improved dqds algorithm for computing all the singular values of a bidiagonal matrix to high relative accuracy. There are two key contributions: a novel deflation strategy that improves the convergence for badly scaled matrices, and some modifications to certain shift strategies that accelerate the convergence for most bidiagonal matrices. These tech-niques together ensure linear worst case complexity of the improved algorithm (denoted by V5). Our extensive numerical experiments indicate that V5 is typically 1.2x–4x faster than DLASQ (the LAPACK-3.4.0 implementation of dqds) without any degradation in accuracy. On matrices for which DLASQ shows very slow convergence, V5 can be 3x–10x faster. At the end of this paper, a hybrid algorithm (HDLASQ) is developed by combining our improvements with the aggressive early defla-tion strategy (AggDef2 in [SIAM J. Matrix Anal. Appl., 33(2012), 22-51]). Numerical results show that HDLASQ is the fastest among these different versions