Bidiagonalization with Parallel Tiled Algorithms

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 tiledbidiagonalization algorithm \bidiag, which is a tiled version of thestandard scalar bidiagonalization algorithm; and(ii) the R-bidiagonalization algorithm \rbidiag, whichis a tiled version of the algorithm whichconsists in first performing the QR factorization ofthe initial matrix, then performing the band-bidiagonalization of the R-factor.For both bidiagonalization algorithms \bidiag and \rbidiag,we use four maintypes of reduction trees, namely \FlatTS, \FlatTT, \Greedy,and a newly introduced auto-adaptive tree, \Auto.We provide a study of critical path lengths for these tiled algorithms, which showsthat (i) \rbidiag has a shorter critical path length than\bidiag for tall and skinny matrices, and (ii) \Greedy 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 distributedshared-memory system, to show the superiority of the new algorithms on avariety of matrix sizes, matrix shapes and core counts