Manchester Applied Mathematics and Numerical Analysis Seminars Winter 1998

October 7, 1998, 4.30 pm

Lecture Theatre 2.14, Maths Building, Oxford Road

Computing the Singular Value Decomposition to High Relative Accuracy

Nick Higham, Department of Mathematics, University of Manchester

The singular value decomposition (SVD) is a widely used tool in numerical linear algebra because it provides much useful information about a matrix. The standard method for computing the SVD guarantees high relative accuracy in the large singular values but not the small ones. We describe an algorithm of Demmel et al. (1997) that aims to obtain the complete SVD to high relative accuracy. Key ideas are the computation of a rank-revealing decomposition and the subsequent use of the one-sided Jacobi algorithm. Demmel et al. analyse the use of Gaussian elimination with complete pivoting (GECP) for computing the rank-revealing decomposition. We investigate the use of QR factorization with complete pivoting (that is, column pivoting together with row sorting or row pivoting) as an alternative to GECP, since this leads to a faster SVD algorithm. We show that the QR-based approach has similar accuracy properties to the one based on GECP.

For further info contact either Matthias Heil (mheil@ma.man.ac.uk), Mark Muldoon (M.Muldoon@umist.ac.uk)or the seminar secretary (Tel. 0161 275 5800).