We consider algorithms for going from a full'' matrix to a condensed band bidiagonal'' form using orthogonal transformations. We use the framework of algorithms by tiles''. Within this framework, we study: (i) the tiled bidiagonalization algorithm , which is a tiled version of the standard scalar bidiagonalization algorithm; and (ii) the R-bidiagonalization algorithm , which is a tiled version of the algorithm which consists in first performing the QR factorization of the initial matrix, then performing the band-bidiagonalization of the R-factor. For both bidiagonalization algorithms and , we use four main types of reduction trees, namely , , , and a newly introduced auto-adaptive tree, . We provide a study of critical path lengths for these tiled algorithms, which shows that (i) has a shorter critical path length than for tall and skinny matrices, and (ii) based schemes are much better than earlier proposed variants with unbounded resources. We provide experiments on a single multicore node, and on a few multicore nodes of a parallel distributed shared-memory system, to show the superiority of the new algorithms on a variety of matrix sizes, matrix shapes and core counts.
Approach to compute the SVD without going by bidiagonal form. We note that going to bidiagonal form is not a necessary step to compute the singular value decomposition of a matrix. There are approaches to compute the SVD of a matrix which avoid the reduction to bidiagonal form. In the direct method'' category, we can quote Jacobi SVD @cite_2 @cite_34 , QDWHSVD @cite_35 ; one can also think to think the singular value decomposition directly from the block bidiagonal form although not much work has been done in this direction so far. Also, we can also refer to all iterative methods'' for computing the singular values. The goal of these iterative methods is in general to compute a few singular triplets. As far as software packages, we can quote SVDPACK @cite_9 , PROPACK @cite_23 , and PRIMME SVD @cite_11 . As far methods, we can quote @cite_19 @cite_32 @cite_12 .
@cite_35 @cite_9 @cite_32 @cite_19 @cite_23 @cite_2 @cite_34 @cite_12 @cite_11
2087716616 2058443643 2169378749 2119759375
Abstract Most methods for calculating the SVD (singular value decomposition) require to first bidiagonalize the matrix. The blocked reduction of a general, dense matrix to bidiagonal form, as implemented in ScaLAPACK, does about one half of the operations with BLAS3. By subdividing the reduction into two stages dense → banded and banded → bidiagonal with cubic and quadratic arithmetic costs, respectively, we are able to carry out a much higher portion of the calculations in matrix–matrix multiplications. Thus, higher performance can be expected. This paper presents and compares three parallel techniques for reducing a full matrix to banded form. (The second reduction stage is described in another paper [B. Lang, Parallel Comput. 22 (1996) 1–18]). Numerical experiments on the Intel Paragon and IBM SP 1 distributed memory parallel computers demonstrate that the two-stage reduction approach can be significantly superior if only the singular values are required. We describe the design and implementation of a new algorithm for computing the singular value decomposition (SVD) of a real bidiagonal matrix. This algorithm uses ideas developed by Grosser and Lang that extend Parlett’s and Dhillon’s multiple relatively robust representations (MRRR) algorithm for the tridiagonal symmetric eigenproblem. One key feature of our new implementation is that @math singular triplets can be computed using only @math storage units and floating point operations, where @math is the dimension of the matrix. The algorithm will be made available as routine xBDSCR in the upcoming new release of the LAPACK library. The authors present a stable and efficient divide-and-conquer algorithm for computing the singular value decomposition (SVD) of a lower bidiagonal matrix. Previous divide-and-conquer algorithms all suffer from a potential loss of orthogonality among the computed singular vectors unless extended precision arithmetic is used. A generalization that computes the SVD of a lower banded matrix is also presented. This paper concerns accurate computation of the singular value decomposition (SVD) of an (m n ) matrix (A ). As is well known, cross-product matrix based SVD algorithms compute large singular values accurately but generally deliver poor small singular values. A new novel cross-product matrix based SVD method is proposed: (a) Use a backward stable algorithm to compute the eigenpairs of (A^ T A ) and take the square roots of the large eigenvalues of it as the large singular values of (A ) ; (b) form the Rayleigh quotient of (A^ T A ) with respect to the matrix consisting of the computed eigenvectors associated with the computed small eigenvalues of (A^ T A ) ; (c) compute the eigenvalues of the Rayleigh quotient and take the square roots of them as the small singular values of (A ). A detailed quantitative error analysis is conducted on the method. It is proved that if small singular values are well separated from the large ones then the method can compute the small ones accurately up to the order of the unit roundoff ( ). An algorithm is developed that is not only cheaper than the standard Golub–Reinsch and Chan SVD algorithms but also can update or downdate a new SVD by adding or deleting a row and compute certain refined Ritz vectors for large matrix eigenproblems at very low cost. Several variants of the algorithm are proposed that compute some or all parts of the SVD. Typical numerical examples confirm the high accuracy of our algorithm.