{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19970"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19970","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Numerical methods for the solution of large and very large, sparse Lyapunov equations","abstract":"In this dissertation we consider the numerical solution of large $(100 \\leq n \\leq 1000)$ and very large $(n \\geq 1000)$, sparse Lyapunov equations $AX + XA\\sp\\prime + Q = 0$. We first present a parallel version of the Hammarling algorithm for the solution of Lyapunov equations where the coefficient matrix A is large and dense. We then present a novel parallel algorithm for the solution of Lyapunov equations where A is large and banded. We provide a detailed analysis of the computational requirements in tandem with the results of numerical experiments with these algorithms on an Alliant FX-8 multiprocessor.","abstract_html":"In this dissertation we consider the numerical solution of large $(100 \\leq n \\leq 1000)$ and very large $(n \\geq 1000)$, sparse Lyapunov equations $AX + XA\\sp\\prime + Q = 0$. We first present a parallel version of the Hammarling algorithm for the solution of Lyapunov equations where the coefficient matrix A is large and dense. We then present a novel parallel algorithm for the solution of Lyapunov equations where A is large and banded. We provide a detailed analysis of the computational requirements in tandem with the results of numerical experiments with these algorithms on an Alliant FX-8 multiprocessor.","abstract_has_math":true,"creators":["Hodel, Alan Scottedward"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Poolla, Kameshwar"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:24:35Z","date_published":"2011-05-07T12:24:35Z","updated_at":"2026-07-22T22:25:15Z","subjects":["Engineering, Electronics and Electrical","Engineering, Mechanical","Computer Science"],"languages":["eng"],"rights":["Copyright 1989 Hodel, Alan Scottedward"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9010887","(UMI)AAI9010887"],"render_values":[{"text":"AAI9010887","href":null,"code":true},{"text":"(UMI)AAI9010887","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19970","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Poolla, Kameshwar"]},{"key":"dc:creator","label":"Author","values":["Hodel, Alan Scottedward"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:24:35Z","10000-01-01","1989"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Engineering, Mechanical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1989 Hodel, Alan Scottedward"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9010887","(UMI)AAI9010887","http://hdl.handle.net/2142/19970"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this dissertation we consider the numerical solution of large $(100 \\leq n \\leq 1000)$ and very large $(n \\geq 1000)$, sparse Lyapunov equations $AX + XA\\sp\\prime + Q = 0$. We first present a parallel version of the Hammarling algorithm for the solution of Lyapunov equations where the coefficient matrix A is large and dense. We then present a novel parallel algorithm for the solution of Lyapunov equations where A is large and banded. We provide a detailed analysis of the computational requirements in tandem with the results of numerical experiments with these algorithms on an Alliant FX-8 multiprocessor.","In the second half of this dissertation, we consider the numerical solution of Lyapunov equations where the coefficient matrix A is very large and sparse. Under these conditions, the solution X of the Lyapunov equation is typically full rank and dense. The associated excessive storage requirements compel us to compute low rank approximations of the solution X of the Lyapunov equation. We present in detail two methods for the low rank approximate solution of the Lyapunov equation. The first method, Trace Maximization, computes an orthogonal matrix $V \\in \\Re\\sp{n\\times k}$ that maximizes the trace of the solution $\\Sigma\\sb{V}$ of the associated reduced order Lyapunov equation $(V\\sp\\prime AV)\\Sigma\\sb{V}$ + $\\Sigma\\sb{V}(V\\sp\\prime A\\sp\\prime V)$ + $V\\sp\\prime QV = 0$. While Trace Maximization is an effective method for low rank approximation of explicitly specified Hermitian matrices, we show that Trace Maximization is not an effective strategy for low rank approximation of positive semidefinite Hermitian matrices X that are implicitly specified as the solution of a Lyapunov equation. Our second algorithm for low rank approximate solution of Lyapunov equations, Approximate Power Iteration, attempts to directly compute an orthogonal basis of the dominant eigenspace of the solution X. We are able to show that if the dominant eigenvalues $\\lambda\\sb1$ and $\\lambda\\sb2$ of X are sufficiently well separated $(\\lambda\\sb1 \\gg \\lambda\\sb2)$, then a special case of the Approximate Power Iteration algorithm has at least one fixed point v that is near to the dominant eigenvector $u\\sb1$ of X, and that there is a small attractive region in $\\Re\\sp{n}$ containing both $u\\sb1$ and v.","Made available in DSpace on 2011-05-07T12:24:35Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9010887.pdf: 5238813 bytes, checksum: 39cfc74a59da0e3177eb5e9b0f9d4fed (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:40:40Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:17:28-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Numerical methods for the solution of large and very large, sparse Lyapunov equations"]}]}],"canonical_facts":{"dc:contributor":["Poolla, Kameshwar"],"dc:creator":["Hodel, Alan Scottedward"],"dc:date":["2011-05-07T12:24:35Z","10000-01-01","1989"],"dc:description":["In this dissertation we consider the numerical solution of large $(100 \\leq n \\leq 1000)$ and very large $(n \\geq 1000)$, sparse Lyapunov equations $AX + XA\\sp\\prime + Q = 0$. We first present a parallel version of the Hammarling algorithm for the solution of Lyapunov equations where the coefficient matrix A is large and dense. We then present a novel parallel algorithm for the solution of Lyapunov equations where A is large and banded. We provide a detailed analysis of the computational requirements in tandem with the results of numerical experiments with these algorithms on an Alliant FX-8 multiprocessor.","In the second half of this dissertation, we consider the numerical solution of Lyapunov equations where the coefficient matrix A is very large and sparse. Under these conditions, the solution X of the Lyapunov equation is typically full rank and dense. The associated excessive storage requirements compel us to compute low rank approximations of the solution X of the Lyapunov equation. We present in detail two methods for the low rank approximate solution of the Lyapunov equation. The first method, Trace Maximization, computes an orthogonal matrix $V \\in \\Re\\sp{n\\times k}$ that maximizes the trace of the solution $\\Sigma\\sb{V}$ of the associated reduced order Lyapunov equation $(V\\sp\\prime AV)\\Sigma\\sb{V}$ + $\\Sigma\\sb{V}(V\\sp\\prime A\\sp\\prime V)$ + $V\\sp\\prime QV = 0$. While Trace Maximization is an effective method for low rank approximation of explicitly specified Hermitian matrices, we show that Trace Maximization is not an effective strategy for low rank approximation of positive semidefinite Hermitian matrices X that are implicitly specified as the solution of a Lyapunov equation. Our second algorithm for low rank approximate solution of Lyapunov equations, Approximate Power Iteration, attempts to directly compute an orthogonal basis of the dominant eigenspace of the solution X. We are able to show that if the dominant eigenvalues $\\lambda\\sb1$ and $\\lambda\\sb2$ of X are sufficiently well separated $(\\lambda\\sb1 \\gg \\lambda\\sb2)$, then a special case of the Approximate Power Iteration algorithm has at least one fixed point v that is near to the dominant eigenvector $u\\sb1$ of X, and that there is a small attractive region in $\\Re\\sp{n}$ containing both $u\\sb1$ and v.","Made available in DSpace on 2011-05-07T12:24:35Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9010887.pdf: 5238813 bytes, checksum: 39cfc74a59da0e3177eb5e9b0f9d4fed (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:40:40Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:17:28-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9010887","(UMI)AAI9010887","http://hdl.handle.net/2142/19970"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Hodel, Alan Scottedward"],"dc:subject":["Engineering, Electronics and Electrical","Engineering, Mechanical","Computer Science"],"dc:title":["Numerical methods for the solution of large and very large, sparse Lyapunov equations"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:15Z"}