In lieu of an abstract, here is a brief excerpt of the content:

Chapter 10 Divide-and-conquer algorithms for the eigendecomposition This chapter will be devoted to the description of divide-and-conquer techniques to compute the eigendecomposition of some special symmetric structured rank matrices . More precisely we will describe divide-and-conquer methods for both tridiagonal and quasiseparable matrices. The divide-and-conquer techniques for structured rank matrices as they will presented here originate from [40, 28]. The main idea of the algorithm is to divide the original problem into two similar independent subproblems (divide step). Once the latter subproblems have been solved, they are glued together to solve the original one (conquer step). This procedure can be recursively applied on the two independent subproblems until their size is sufficiently small to be handled by standard techniques, like the QR or the QL-methods, previously described. A special role in the conquer step of the divide-and-conquer algorithms is played either by symmetric arrowhead matrices or diagonal plus rank one matrices. Section 10.1 emphasizes the properties of the latter matrices. Attention is paid to the interlacing property of the eigenvalues and to the computation of the eigenvectors of these matrices. It will be shown that the eigendecomposition of both these matrices can be computed fast and accurately. In Section 10.2 the main ideas of the divide-and-conquer algorithms for computing the eigendecomposition of symmetric tridiagonal matrices are described. Two types of decompositions in smaller subproblems are presented. The first method uses the arrowhead matrix properties in the conquer step. The second method exploits the diagonal plus rank 1 properties. The main ideas of the divide-and-conquer algorithms for quasiseparable matrices developed in [40, 117] are described in Section 10.3. Several types of divide-andconquer methods are discussed. A direct splitting method is developed in which the original matrix is immediately split up, a method in which a rank 1 matrix is subtracted before splitting the problem and two methods involving initial orthogonal similarity transformations. In the last section of the chapter some numerical experiments concerning tim367 368 Chapter 10. Divide-and-conquer algorithms for the eigendecomposition ings and accuracy are presented. ✎ This chapter is an important one. The eigenvalue decomposition as presented in this chapter has proven to be very fast and very accurate. Section 10.1 discusses some general properties of arrowhead and rank 1 perturbations of diagonal matrices. These properties are not essential for a thorough understanding of the divide-and-conquer methods. Section 10.2 discusses the traditional tridiagonal case, one can also skip this part. The important results of this chapter are contained in Section 10.3. This section contains four different types of divide-andconquer methods and contains the basic ideas of these methods. It is worth reading all four different methods as they differ significantly. Section 10.4 discusses the complexities as well some numerical experiments related to the different methods. 10.1 Arrowhead and diagonal plus rank 1 matrices The kernel of the divide-and-conquer algorithms to compute the spectral decomposition of symmetric matrices proposed in the literature is either the computation of the spectral decomposition of symmetric arrowhead matrices or the computation of the spectral decomposition of symmetric diagonal plus rank 1 matrices, that are both special cases of symmetric quasiseparable matrices1 . In the next subsections we describe the spectral properties of these matrices. 10.1.1 Symmetric arrowhead matrices In this subsection we describe the main properties of symmetric arrowhead matrices and how the spectral decomposition of such matrices can be retrieved in a stable way. Symmetric arrowhead matrices have entries different from zero on the main diagonal, in the last row and in the last column, A = ⎡ ⎢ ⎢ ⎢ ⎣ α1 β1 ... . . . αn−1 βn−1 β1 · · · βn−1 γ ⎤ ⎥ ⎥ ⎥ ⎦ , (10.1) by using pivoting, one can assume α1 ≥ α2 ≥ . . . ≥ αn−1. Obviously, arrowhead matrices are special quasiseparable matrices. Let λi, i = 1, . . . , n be the eigenvalues of A. By the Cauchy interlacing property [94, 129], the eigenvalues of A(1 : n − 1, 1 : n − 1) = D, i.e., {αi}n−1 i=1 , interlace those of A, this means that λ1 ≥ α1 ≥ λ2 ≥ α2 ≥ . . . ≥ λn−1 ≥ αn−1 ≥ λn. (10.2) In the following cases some eigenvalues of A are explicitly known. 1. If βj = 0, then λj = αj, with corresponding eigenvector ej, were ej is the j-th vector of the canonical basis of Rn . 1In fact they have even more structure. They are of semiseparable plus diagonal form...

Share