-
Chapter 4 Implementation of the algorithms and numerical experiments
- Johns Hopkins University Press
- Chapter
- Additional Information
Chapter 4 Implementation of the algorithms and numerical experiments In Chapter 2 we proposed several algorithms to reduce matrices to semiseparable form. To calculate the computational complexity of these algorithms we always assumed that the part of the matrix already in semiseparable form could be represented in an efficient way. This efficient representation will be used in this chapter, and the corresponding implementation will be given. Moreover also some tools for working in an efficient way with the Givens-vector representation will be developed. In Chapter 3 we investigated in detail the interaction between the subspace iteration and the Lanczos convergence behavior of the proposed reduction algorithms. In this chapter several numerical examples will illustrate these theoretical investigations. In the first section we will not yet discuss implementation details nor show numerical experiments. We will provide some tools for figuring out algorithms and implementations related to the Givens-vector represented structured rank matrices. A graphical scheme of how the Givens transformations operate on the vector in the representation is given. Based on this graphical representation and the so-called shift through lemma we will be able to efficiently update the representation. In Section 4.2 we will discuss in a mathematical manner the implementation of the reduction algorithms deduced in the previous chapter. No real implementations are given, just the mathematical ideas with formulas. As in the previous chapters only insight was created due to operations on figures. At the end of this section a complexity analysis of these algorithms is also presented. Two types of complexities are considered. The case in which the reduction is performed from the beginning to the end, not exploiting the deflation possibilities and a second case in which we exploit the deflation. A theoretical test case is shown to compare this method for computing the eigenvalues with the traditional method based on tridiagonal matrices. In Section 4.3, several numerical experiments are performed to illustrate the theoretical results of the previous chapters. We start by examining the convergence behavior of the reduction to semiseparable form. Four different experiments are performed to illustrate the interaction between the subspace iteration and the Lanczos 109 110 Chapter 4. Implementation of the algorithms and numerical experiments convergence behavior. Also examples illustrating the convergence behavior due to the subspace iteration are presented. This might lead to deflation possibilities as mentioned before. The last subsection of this chapter shows a numerical experiment in which the reduction to semiseparable plus diagonal form is investigated. First the interaction between the Lanczos-Ritz values and the subspace iteration is examined. Secondly we investigate in detail the upper bound as it was derived in the previous chapter. The examples clearly illustrate that the presented bound is rather tight. ✎ This chapter discusses issues related to the implementation of the reduction algorithms and also examples related to the convergence properties as proved in the previous chapter are shown. If the reader is not interested in these topics, he can readily proceed with the next part. Details on the computational complexity and some examples are however interesting. Section 4.1 discusses the graphical patterns resulting from applying sequences of Givens transformations. These patterns were discussed extensively in the first volume of the book. These patterns can be useful when implementing algorithms related to structured rank matrices. Details on the implementation are given in Section 4.2. As already mentioned in the introduction to the part, reading of Subsection 4.2.5, considering the computational complexity in case of deflation, is recommended . Also the following experiments are worth reading as they illustrate the theoretical results of the previous chapter. The Experiments 2, 3 and 4 of Subsection 4.3.1 illustrate the interaction between the convergence behaviors. The examples starting from 5 in Subsection 4.3.2 compare the theoretical bound on the convergence speed with the real situation. 4.1 Working with Givens transformations In this section we will discuss some tools for working in an efficient way with Givens transformations. These tools might come in handy when designing algorithms for structured rank matrices as well as for implementing algorithms based on the Givens-vector representation. 4.1.1 Graphical schemes All the implementations considered in this book are based on the so-called Givensvector representation. This is an efficient representation for representing low rank parts in matrices. As a low rank part is not necessarily sparse, transformations involving these low rank parts do change the...