Algorithm 977

Algorithm 977: A QR-preconditioned QR SVD method for computing the SVD with high accuracy. A new software for computing the singular value decomposition (SVD) of real or complex matrices is proposed. The method implemented in the code xGESVDQ is essentially the QR SVD algorithm available as xGESVD in LAPACK. The novelty is an extra step, the QR factorization with column (or complete row and column) pivoting, also already available in LAPACK as xGEQP3. For experts in matrix computations, the combination of the QR factorization and an SVD computation routine is not new. However, what seems to be new and important for applications is that the resulting procedure is numerically superior to xGESVD and that it is capable of reaching the accuracy of the Jacobi SVD. Further, when combined with pivoted Cholesky factorization, xGESVDQ provides numerically accurate and fast solvers (designated as xPHEVC, xPSEVC) for the Hermitian positive definite eigenvalue problem. For instance, using accurately computed Cholesky factor, xPSEVC computes all eigenvalues of the 200×200 Hilbert matrix (whose spectral condition number is greater that 10 300 to nearly full machine precision. Furthermore, xGESVDQ can be used for accurate spectral decomposition of general (indefinite) Hermitian matrices.