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.
Preprocessing the bidiagonalization with a QR factorization (preQR step). In 1982, Chan @cite_5 explains that, for tall-and-skinny matrices, in order to perform less flops, one can pre-process the bidiagonalization step (GE2BD) with a QR factorization. In other words, Chan propose to do preQR( @math , @math )+GE2BD( @math , @math ) instead of GE2BD( @math , @math ). A curiosity of this algorithm is that it introduces nonzeros where zeros were previously introduced; yet, there is a gain in term of flops. Chan proves that the crossover points when preQR( @math , @math )+GE2BD( @math , @math ) performs less flops than GE2BD( @math , @math ) is when @math is greater than @math . Chan also proved that, asymptotically, preQR( @math , @math )+GE2BD( @math , @math ) will perform half the flops than GE2BD( @math , @math ) for a fixed @math and @math going to infinity. If the singular vectors are sought, preQR has more overhead: (1) the crossover point is moved to more tall-and-skinny matrices, and there is less gain; also (2) there is some complication as far as storage goes.
@cite_5
2117026915
The most well-known and widely used algorithm for computing the Singular Value Decomposition (SVD) A --U V T of an m x n rectangular matrix A is the Golub-Reinsch algorithm (GR-SVD). In this paper, an improved version of the original GR-SVD algorithm is presented. The new algorithm works best for matrices with m >> n, but is more efficient even when m is only slightly greater than n (usually when m 2n) and in some cases can achieve as much as 50 percent savings. If the matrix U s exphcltly desired, then n 2 extra storage locations are required, but otherwise no extra storage is needed. The two main modifications are: (1) first triangularizing A by Householder transformations before bldmgonahzing it (thin idea seems to be widely known among some researchers in the field, but as far as can be determined, neither a detailed analysis nor an lmplementatmn has been published before), and (2) accumulating the left Givens transformations in GR-SVD on an n x n array instead of on an m x n array. A PFORT-verified FORTRAN Implementation m included. Comparisons with the EISPACK SVD routine are given.