Multimethod solvers: Algorithms, applications and software

The solution of large sparse linear systems is a fundamental problem in scientific computing. A variety of solution schemes are available reflecting a wide range of performance and quality trade-offs. The "best" solution method can vary across application domains and often even across different phases in a single application. As noted by Ern et al. "The impossibility of uniformly ranking linear system solvers in any order of effectiveness...is widely appreciated." In this thesis, we attempt to deliver the benefits of the variety of sparse linear solution techniques to the application community, by developing multimethod solvers, i.e. solvers that use more than one basic sparse solution scheme.; More specifically, the thesis concerns the development of two types of multimethod sparse linear solvers, namely, composite and adaptive solvers. We develop a composite solver to provide highly reliable solution with low memory requirements by applying a sequence of limited memory iterative solution schemes to the same linear system. We develop an adaptive solver to dynamically select a linear solution scheme to match changing linear system attributes and thus reduce the time required for linear system solution.; Our main contributions are the development and analysis of algorithms to construct composite and adaptive multimethod solvers, and the design and implementation of software for their automatic instantiation. A central result includes the development of an optimal composite solver with increased reliability, low memory requirements, and minimal worst case time, using a combinatorial framework. Another contribution is the formulation of heuristics to enable dynamic linear solution method selection. Finally, we design a software architecture for providing multimethod solver service to the application community. We implement and test our new schemes on two applications; our results demonstrate that our multimethod schemes can significantly improve the reliability of linear system solution while reducing total application time.