<p>This research presents new preconditioners for linear systems. We proceed fromthe most general case to the very specific problem area of sparse optimal control.In the first most general approach, we assume only that the coefficient matrix isnonsingular. We target highly indefinite, nonsymmetric problems that cause difficultiesfor preconditioned iterative solvers, and where standard preconditioners, likeincomplete factorizations, often fail. We experiment with nonsymmetric permutationsand scalings aimed at placing large entries on the diagonal in the context of preconditioningfor general sparse matrices. Our numerical experiments indicate that thereliability and performance of preconditioned iterative solvers are greatly enhancedby such preprocessing.Secondly, we present two new preconditioners for KKT systems. KKT systemsarise in areas such as quadratic programming, sparse optimal control, and mixedfinite element formulations. Our preconditioners approximate a constraint preconditionerwith incomplete factorizations for the normal equations. Numerical experimentscompare these two preconditioners with exact constraint preconditioning andthe approach described above of permuting large entries to the diagonal.Finally, we turn to a specific problem area: sparse optimal control. Many optimalcontrol problems are broken into several phases, and within a phase, mostvariables and constraints depend only on nearby variables and constraints. However,free initial and final times and time-independent parameters impact variables andconstraints throughout a phase, resulting in dense factored blocks in the KKT matrix.We drop fill due to these variables to reduce density within each phase. Theresulting preconditioner is tightly banded and nearly block tri-diagonal. Numericalexperiments demonstrate that the preconditioners are effective, with very little fill inthe factorization.<P>
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-20020323-195621 |
| Date | 25 March 2002 |
| Creators | Haws, John Courtney |
| Contributors | Carl D. Meyer, Ilse C.F. Ipsen, Jeffrey Scroggs, Ernest Stitzinger |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-20020323-195621 |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.1039 seconds