Comparison of methods for solving Sylvester systems

[摘要] 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, controltheory, 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 efficientsolution of Sylvester equations typically fall into two categories, namely direct and iterativemethods. 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 numericallinear algebra. We shall see, however, that unless the matrix is very sparse and structured, thisapproach 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 suchas Bartels–Stewart and Hessenberg–Schur, which are based on suitable factorisations of A andB, 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 useKrylov subspace techniques to project the system onto a much smaller subspace, which can besolved efficiently using one of the direct methods mentioned above as an internal solver. In thisthesis we consider two different subspaces for the comparison of projection methods, namely thestandard Krylov subspace and an enriched approximation space known as the extended Krylovsubspace. We shall see that when the matrix C is of low rank, then the extended Krylov subspacemethod 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 usedto 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 isthe 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 mostefficient approximation space.

[发布机构] Stellenbosch University