For more information about this meeting, contact Mary Anne Raymond.
|Title:||Reduction to Bidiagonal Form—New Algorithms and Issues|
|Seminar:||CCMA PDEs and Numerical Methods Seminar Series|
|Speaker:||Jesse Barlow, Department of Computer Science and Engineering The Pennsylvania State University|
|Since Golub and Kahan’s 1965 landmark paper, bidiagonal reduction has been an important first step in computing the singular value decomposition. The algorithm also plays an important role in the solution of ill-posed least squares problems and the computation of matrix functions. Two algorithms for bidiagaonal reduction were presented in that original paper---a Householder based reduction usually used for dense matrices and a Lanczos based reduction that is traditionally used to extract a subset of singular values and vectors from a large, sparse or structured matrix. Variants to the Householder based reduction have been proposed by Lawson and Hansen, Chan, and Trefethen and Bau.
The Lanczos-based reduction has always suffered from the same problem as the Lanczos algorithm for symmetric matrices—loss of orthogonality in the reduction resulting in simple singular values converging as clusters. Simon and Zha proposed a version of the algorithm that reorthogonalizes just one of the two sets of Lanczos vectors, the speaker along with Bosner and Drmač developed a hybrid algorithm that produces one set of Lanczos vectors using Householder transformations, the other using the Lanczos recurrence. In this talk, a framework based on an observation by Charles Sheffield and recent work by Paige, is used to understand both the Simon and Zha and Barlow, Bosner, and Drmač variants of the Golub-Kahan-Lanczos (GKL) bidiagonal reduction. It is shown that if good orthogonality is maintained in just one set of Lanczos vectors, the algorithm retains a number of desirable properties. These include good orthogonality in leading left and right singular vectors, and that the algorithm acts exactly as the GKL algorithm in exact arithmetic on a nearby matrix. At the end of the talk, issues involving generalization to a block GKL algorithm and implementation are discussed.|
Room Reservation Information
|Date:||04 / 23 / 2013|
|Time:||03:30pm - 05:00pm|