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.
In 1965, Golub and Kahan @cite_1 provides a singular value solver based on an initial reduction to bidiagonal form. In [Th. 1] doi:10.1137 0702016 , the GE2BD step is done using a QR step on the first column, then an LQ step on the first row, then a QR step on the second column, etc. The steps are done one column at a time using Householder transformation. This algorithm is implemented as a Level-2 BLAS algorithm in as xGEBD2 . For an @math -by- @math matrix, the cost of this algorithm is (approximately) @math .
@cite_1
2087716616 2097897435 2058443643 1581582143
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. An iterative method is given for solving Ax ffi b and minU Ax b 112, where the matrix A is large and sparse. The method is based on the bidiagonalization procedure of Golub and Kahan. It is analytically equivalent to the standard method of conjugate gradients, but possesses more favorable numerical properties. Reliable stopping criteria are derived, along with estimates of standard errors for x and the condition number of A. These are used in the FORTRAN implementation of the method, subroutine LSQR. Numerical tests are described comparing I QR with several other conjugate-gradient algorithms, indicating that I QR is the most reliable algorithm when A is ill-conditioned. 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 objective of this paper is to enhance the parallelism of the tile bidiagonal transformation using tree reduction on multicore architectures. First introduced by Ltaief et. al [LAPACK Working Note #247, 2011], the bidiagonal transformation using tile algorithms with a two-stage approach has shown very promising results on square matrices. However, for tall and skinny matrices, the inherent problem of processing the panel in a domino-like fashion generates unnecessary sequential tasks. By using tree reduction, the panel is horizontally split, which creates another dimension of parallelism and engenders many concurrent tasks to be dynamically scheduled on the available cores. The results reported in this paper are very encouraging. The new tile bidiagonal transformation, targeting tall and skinny matrices, outperforms the state-of-the-art numerical linear algebra libraries LAPACK V3.2 and Intel MKL ver. 10.3 by up to 29-fold speedup and the standard two-stage PLASMA BRD by up to 20-fold speedup, on an eight socket hexa-core AMD Opteron multicore shared-memory system.