Department of Applied Mathematics

Permanent URI for this community

https://scholar.sun.ac.za/handle/10019.1/96341

Browse

Browsing Department of Applied Mathematics by Subject "Algebras, Linear"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Comparison of methods for solving Sylvester systems
    (Stellenbosch : Stellenbosch University, 2018-12) Kirsten, Gerhardus Petrus; Hale, Nicholas Peter; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Applied Mathematics.
    ENGLISH ABSTRACT :This thesis serves as a comparative study of numerical methods for solving Sylvester equations, which are linear matrix equations of the form AX + XB + C = 0. These equations have important applications in many areas of science and engineering, such as signal processing, control theory, and systems engineering, and their efficient solution is therefore of practical significance. As with standard linear systems (i.e., those of the form Ax = b), algorithms for the efficient solution of Sylvester equations typically fall into two categories, namely direct and iterative methods. As a naive approach, one can convert a Sylvester equation to a standard linear system (of larger size) using Kronecker operations, and then apply standard methods from numerical linear algebra. We shall see, however, that unless the matrix is very sparse and structured, this approach is usually inefficient. Instead, modern algorithms for solving Sylvester equations are applied directly to the equation in Sylvester form. When the matrices A and B are small and dense, direct methods such as Bartels–Stewart and Hessenberg–Schur, which are based on suitable factorisations of A and B, are efficient. As the matrices become larger, however, one typically switches to a projectionbased or some other iterative method. The projection methods considered in this thesis use Krylov subspace techniques to project the system onto a much smaller subspace, which can be solved efficiently using one of the direct methods mentioned above as an internal solver. In this thesis we consider two different subspaces for the comparison of projection methods, namely the standard Krylov subspace and an enriched approximation space known as the extended Krylov subspace. We shall see that when the matrix C is of low rank, then the extended Krylov subspace method is competitive with direct methods, even when the system size is relatively small. Each of the methods discussed above are compared, both theoretically by consideration of floating point operation counts and numerically by computational efficiency and accuracy, when used to solve several example problems arising in applications. Based on the results of these experiments, it is concluded that a method based on the eigenvalue decompositions of A and B is the most efficient direct method, although to some degree at the expense of numerical stability. In the class of projection methods, we find that the extended Krylov subspace to be the most efficient approximation space.