engleski

Fast Methods for Large Scale Singular Value Decomposition

This thesis is dealing with two major topics in numerical linear algebra: the singular value decomposition (SVD) and the eigenvalue problem. Two new algorithms are proposed: one for finding the singular value decomposition, and one for solving the partial eigenvalue problem of a symmetric positive definite matrix. The one-sided bidiagonalization algorithm proposed by Barlow is analyzed, and is proven to be numerically stable. The bidiagonalization constitutes the first step in computing the SVD. Next, the block version of the one-sided bidiagonalization is proposed, which increases its efficiency and retains numerical stability. The parallel version of the same algorithm was also studied and numerical tests show that it is faster than the parallel algorithm implemented in the ScaLAPACK software package. One-sided bidiagonalization turned out to be competitive to other standard bidiagonalization algorithms, and there are several applications where it can be successfully applied. Another algorithm presented in this thesis is the new subspace method for computing eigenvectors corresponding to the several smallest eigenvalues of a symmetric positive definite matrix. The name of the method is multispace, and it is a combination of multigrid approach and of two very well known subspace methods: inverse iteration and the block Lanczos method. The new multigrid approach is designed to speed up the convergence of slow converging inverse iteration. A convergence rate for multispace is also presented, proving that the whole process converges to an invariant subspace. In addition to the algorithms, a new perturbation result for singular value approximations from subspaces is presented. The new result represents a measure for relative errors in singular values expressed by terms involving angles of appropriate subspaces.

singular value decomposition ; computational methods ; numerical analysis ; perturbation theory

nije evidentirano