An improved DQDS algorithm

DOI10.1137/120881087MaRDI QIDQ2878975zbMATH OpenOpenAlexFDO

Authors Ming Gu, Beresford N. Parlett, Shengguo Li

Publication date 5 September 2014

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5462

zbMATH Keywords

bidiagonal matrixconvergence accelerationd-deflationdifferential quotient difference with stifts algorithmnumerical experimentsingular value

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

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 techniques 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 deflation strategy (AggDef2 in [SIAM J. Matrix Anal. Appl., 33(2012), 22-51]). Numerical results show that HDLASQ is the fastest among these different versions.

Recommendations

• dqds with aggressive early deflation
• An improved dqds type algorithm
• A shift for accurate singular values in the differential qd algorithm
• Accurate singular values and differential qd algorithms
• A shift strategy for superquadratic convergence in the dqds algorithm for singular values

Cited in

(10)

• An improved dqds type algorithm
• PACF: a precision-adjustable computational framework for solving singular values
• Corrections to the ``improved Q-M algorithm.
• Improving a CGS-QE Algorithm
• dqds with aggressive early deflation
• An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
• An application of the Kato-temple inequality on matrix eigenvalues to the dqds algorithm for singular values
• Implementation details of an extended OQDS algorithm for singular values
• Accurate restricted singular value decomposition via deflation on Neville representations
• Superquadratic convergence of DLASQ for computing matrix singular values

Describes a project that uses

Uses Software

• LAPACK
• DLASQ
• AggDef2
• HDLASQ

This page was built for publication: An improved DQDS algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878975)