Author:

Keywords:

orthogonal similarity reductions, tridiagonal, semiseparable, semiseparable plus diagonal, lanczos-ritz values, multi-shift, subspace iteration, Science & Technology, Physical Sciences, Mathematics, Applied, Mathematics, Lanczos-Ritz values, MATRICES, DIVIDE, EIGENDECOMPOSITION, ALGORITHMS, 0101 Pure Mathematics, 0102 Applied Mathematics, 0103 Numerical and Computational Mathematics, Numerical & Computational Mathematics, 4901 Applied mathematics, 4904 Pure mathematics

Abstract:

In this paper, we will compare the convergence properties of three basic reduction methods, by placing them in a general framework. It covers the reduction to tridiagonal, semiseparable and semiseparable plus diagonal form. These reductions are often used as the first step in the computation of the eigenvalues and/or eigenvectors of arbitrary matrices. In this way, the calculation of the eigenvalues using, for example, the QR-algorithm reduces in complexity. First we will investigate the convergence properties of these three reduction algorithms. It will be shown that for the partially reduced matrices at step k of any of these reduction algorithms, the lower right k x k (already reduced) sub-block will have the Lanczos-Ritz values, w.r.t. a certain starting vector. It will also be shown that the reductions to semiseparable and to semiseparable plus diagonal form have an extra convergence behavior a special type of subspace iteration is performed on the lower right k x k submatrix, which contains these Ritz-values. Secondly we look in more detail at the behavior of the involved subspace iteration. It will be shown that the reduction method can be interpreted as a nested type of multi-shift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms. Also a theoretical bound on the convergence rate is presented. Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it can become a powerful tool for certain applications.