Matrix Computations and Semiseparable Matrices: Eigenvalue and Singular Value Methods

Chapter 3 Convergence properties of the reduction algorithms

Chapter 3 Convergence properties of the reduction algorithms In the previous chapter, several types of reduction algorithms to either sparse or structured rank matrices were presented. It was stated there that the orthogonal similarity reduction to a similar semiseparable matrix could also be achieved by first transforming the matrix to a similar tridiagonal one and then transforming the tridiagonal matrix into a similar semiseparable one. It is a known result that the already reduced part in the tridiagonal reduction contains the Lanczos-Ritz values. In this chapter we will see to which extent these classical results for tridiagonal matrices are valid for the semiseparable case. Secondly there was also a remark, which stated that the reduction, although it costs an extra 9n2 +O(n) with respect to the tridiagonalization, inherited an extra kind of convergence behavior. These extra operations create a subspace iteration convergence behavior, which also will be addressed here. This chapter contains three sections. The layout of all three sections is similar. First we describe the property we want to investigate for the reduction to semiseparable form. Then we extend this property to a general framework, and finally we apply this general framework to all the reduction algorithms as proposed in the previous chapter, i.e., the reduction to semiseparable, semiseparable plus diagonal, Hessenberg-like and so forth. In the first section we deduce a general theorem, providing necessary and sufficient conditions, for an orthogonal similarity transformation to obtain the ArnoldiRitz values in the already reduced part of the matrix. The theorem provided is very simple, only two conditions have to be placed on the reduction algorithm, but it is completely general. This means, that using this theorem the convergence properties of the transformations to tridiagonal, semiseparable, Hessenberg and Hessenberglike can be proved in one line. In the second section we will investigate in detail the extra convergence behavior of the reductions to structured rank form, with regard to the reductions to sparse form. We will prove that the extra performed Givens transformations cause a convergence behavior, which can be interpreted as a type of nested subspace 67 68 Chapter 3. Convergence properties of the reduction algorithms iteration. In the last section the interaction between the Lanczos convergence behavior and the subspace iteration will be investigated. We will prove that the subspace iteration will start converging as soon as the Lanczos-Ritz values approximate well enough the eigenvalues the subspace iteration tends to converge to. The interaction behavior as proposed in this section is affirmed by the derivation of the convergence speed. Moreover a detailed complexity analysis, if deflation is possible, will be given. The theoretical results in this chapter will be confirmed by numerical experiments in the following chapter. ✎ In this chapter, the convergence properties of the reduction algorithms proposed in the previous chapter are examined. Two types of behavior are covered . The Lanczos-Ritz values convergence behavior and the subspace iteration convergence behavior. An introduction to Lanczos-Ritz values and an explanation of the notation used can be found in Subsection 3.1.1. The Lanczos-type of convergence behavior is summarized into two theorems, namely Theorem 3.2 and Theorem 3.3, providing the necessary and sufficient conditions, respectively. The case of invariant subspaces is left to the interested reader and is rather similar to the standard case (Subsection 3.1.5). Important for our analysis is the application of these theorems (Theorems 3.2 and 3.3) towards the proposed reduction algorithms. This is done in Subsection 3.1.7. The second convergence behavior is analyzed in its most general form in Subsection 3.2.2 and Subsection 3.2.3. Especially Theorem 3.6 covers the global picture. The different formulations of the theorem leading to different interpretations covered in Corollaries 3.7, 3.8 and 3.9 help to understand the convergence behavior. The interaction of both convergence behaviors is neatly summarized in Subsection 3.3.2. Estimates on the convergence speed towards a block diagonal matrix are given in Subsection 3.3.3. The paragraph titled “the convergence speed of the nested multishift iteration” contains the theoretical upper bound on the convergence speed. 3.1 The Arnoldi(Lanczos)-Ritz values It is well-known that while reducing a symmetric matrix into a similar tridiagonal one the intermediate tridiagonal matrices contain the Lanczos-Ritz values as eigenvalues . Or for a Hessenberg matrix they contain the so-called Arnoldi-Ritz values. More information can be found...