Robust preconditioning for indefnite and Ill-conditioned sparse linear systems
2011-12
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Robust preconditioning for indefnite and Ill-conditioned sparse linear systems
Authors
Published Date
2011-12
Publisher
Type
Thesis or Dissertation
Abstract
Linear systems originating from certain applications in the physical sciences can be challenging to solve by iterative methods. In the past, direct methods like Gaussian elimination have been often used to solve these systems, due to their robust nature. However, as problems are now often formulated in 3-D geometries, the use of direct solvers is becoming prohibitive. Moreover, unlike iterative solvers, direct solvers cannot be easily parallelized. Two classes of methods have attracted the interest of researchers in recent years. First, is the class of multigrid methods, which have been shown to be very efficient for elliptic-type problems, and for which various adaptations have been brought. Second, is the class of preconditioned Krylov subspace methods. Here, work has focused mainly on improving the preconditioning. The underlying challenge is to develop or identify techniques that are robust and efficient in terms of accuracy, stability, and scalability. As problems in computational science continue to evolve, so do preconditioning techniques, as new ideas are incorporated to develop solver technologies that are well adapted to solve novel and challenging problems. To further contribute to this endeavor, my research uses ideas from numerical linear algebra to address algorithmic and computational issues in the numerical solution of application problems. The ideas presented in this thesis will focus on improving the stability and effectiveness of ILU-based preconditioners to better handle challenging problems characterized by indefinite and poorly conditioned linear systems.
First, we present various strategies designed to improve the quality of the ILU factorization in order to safeguard stability without compromising the accuracy of the resulting factors. These strategies introduce new contributions to the areas of shifted ILU methods, modified ILU and compensation-based techniques, and reordering techniques for ILU. The resulting factors yield good and more robust preconditioners that are effective on highly indefinite and ill-conditioned linear systems.
Next, we demonstrate the effectiveness of combining ILU factorizations with multilevel methods. Multilevel ILU methods have become a popular area of research, as researchers seek to take advantage of the superior robustness of ILU, coupled with the efficiency and scalability of multilevel methods. We discuss issues related to constructing the next-level matrices in the multilevel hierarchy and present ideas from multilevel graph coarsening and reordering strategies to construct an algebraic multilevel ILU-based preconditioner.
Finally, we discuss key concepts necessary for an efficient adaptation of the ILU-based preconditioner into a parallel framework. We discuss the parallel implementation within the structure of the parallel algebraic multilevel solver (pARMS) framework. We demonstrate how different preconditioning techniques may be incorporated into this framework, and discuss issues relating to scalability.
Description
University of Minnesota Ph.D. dissertation. December 2011. Major: Scientific Computation.
Advisor: Yousef Saad. 1 computer file (PDF); xiv, 136 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Osei-Kuffuor, Danie. (2011). Robust preconditioning for indefnite and Ill-conditioned sparse linear systems. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/119987.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.