Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Comparison of methods for solving Sylvester systems
Thesis (MSc)--Stellenbosch University, 2018.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2018
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614023162265600 |
|---|---|
| access_status_str | Open Access |
| author | Kirsten, Gerhardus Petrus |
| author2 | Hale, Nicholas Peter |
| author_browse | Hale, Nicholas Peter Kirsten, Gerhardus Petrus |
| author_facet | Hale, Nicholas Peter Kirsten, Gerhardus Petrus |
| author_sort | Kirsten, Gerhardus Petrus |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2018. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/104855 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:45:26.037Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2018 |
| publishDateRange | 2018 |
| publishDateSort | 2018 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/104855 Comparison of methods for solving Sylvester systems Kirsten, Gerhardus Petrus Hale, Nicholas Peter Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Applied Mathematics. Lyapunov functions Algebras, Linear Sylvester equations UCTD Differential equations -- Numerical solutions Thesis (MSc)--Stellenbosch University, 2018. 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. 2018-09-18T10:08:31Z 2018-12-07T06:47:56Z 2018-09-18T10:08:31Z 2018-12-07T06:47:56Z 2018-12 Thesis http://hdl.handle.net/10019.1/104855 en_ZA Stellenbosch University application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Lyapunov functions Algebras, Linear Sylvester equations UCTD Differential equations -- Numerical solutions Kirsten, Gerhardus Petrus Comparison of methods for solving Sylvester systems |
| title | Comparison of methods for solving Sylvester systems |
| title_full | Comparison of methods for solving Sylvester systems |
| title_fullStr | Comparison of methods for solving Sylvester systems |
| title_full_unstemmed | Comparison of methods for solving Sylvester systems |
| title_short | Comparison of methods for solving Sylvester systems |
| title_sort | comparison of methods for solving sylvester systems |
| topic | Lyapunov functions Algebras, Linear Sylvester equations UCTD Differential equations -- Numerical solutions |
| url | http://hdl.handle.net/10019.1/104855 |
| work_keys_str_mv | AT kirstengerharduspetrus comparisonofmethodsforsolvingsylvestersystems |