Comparison of methods for solving Sylvester systems

Kirsten, Gerhardus Petrus (2018-12)

Thesis (MSc)--Stellenbosch University, 2018.

Thesis

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.

AFRIKAANSE OPSOMMING : Hierdie tesis is ’n vergelykende studie van numeriese metodes om Sylvester-vergelykings op te los, wat lineêre matriksvergelykings is met die vorm AX + XB + C = 0. Die vergelykings het belangrike toepassings in verskeie wetenskaplike en ingenieursvelde soos seinverwerking, beheerteorie en stelselingenieurswese, en die doeltreffende oplos daarvan is dus van praktiese belang. Soos wat die geval is met gewone lineêre stelsels (met die vorm Ax = b), bestaan daar normaalweg twee kategorieë vir die doeltreffende oplos van Sylvester-vergelykings, naamlik direkte en iteratiewe metodes. As ’n naïewe benadering kan ’n mens ’n Sylvester-vergelyking in ’n gewone lineêre stelsel omskakel deur die gebruik van Kronecker-bewerkings en dan standaardmetodes van numeriese lineêre algebra toepas. Tensy die matriks (wat nou veel groter is) baie yl en gestruktureerd is, is hierdie benadering egter selde doeltreffend. In plaas van bogenoemde benadering word moderne algoritmes vir die oplos van Sylvestervergelykings direk in Sylvester-vorm toegepas. Wanneer die matrikse A en B klein is, is direkte metodes soos Bartels–Stewart en Hessenberg–Schur, wat op gepaste faktoriserings van A en B gebaseer is, doeltreffend. Wanneer die matrikse egter vergroot, word daar normaalweg na ’n projeksie-gebaseerde of ander iteratiewe metode oorgeskakel. Die projeksiemetodes wat in hierdie tesis bespreek word, gebruik Krylov-subruimtetegnieke om die stelsel op ’n kleiner subruimte te projekteer, wat dan doeltreffend opgelos kan word deur een van die direkte metodes hierbo genoem as ’n interne oplosser te gebruik. In die tesis word twee verskillende subruimtes vir die vergelyking van projeksiemetodes oorweeg, naamlik die gewone Krylov-subruimte en die verrykte benaderingsruimte bekend as die uitgebreide Krylov-subruimte. Ons sien dat wanneer die matriks C van lae rang is, die uitgebreide Krylov-subruimte kompeterend met direkte metodes is, selfs wanneer die stelselgrootte relatief klein is. Elke metode wat hierbo bespreek word, word vergelyk — teoreties, deur middel van wisselpuntbewerkingstellings, sowel as numeries, deur berekenings-doeltreffendheid en -akkuraatheid — wanneer dit gebruik word om verskeie voorbeeldprobleme op te los wat in toepassings voorkom. Die bevindings van hierdie eksperimente toon dat ’n metode gebaseer op die eiewaarde-ontbindings van A en B die doeltreffendste direkte metode is, hoewel dit in ’n mate ten koste van numeriese stabiliteit is. In die geval van projeksiemetodes word daar bevind dat die uitgebreide Krylovsubruimte die doeltreffendste benaderingsruimte is.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/104855
This item appears in the following collections: