George, Thomas (2009-12). A Recommendation System for Preconditioned Iterative Solvers. Doctoral Dissertation. Thesis uri icon

abstract

  • Solving linear systems of equations is an integral part of most scientific simulations. In

    recent years, there has been a considerable interest in large scale scientific simulation of

    complex physical processes. Iterative solvers are usually preferred for solving linear systems

    of such magnitude due to their lower computational requirements. Currently, computational

    scientists have access to a multitude of iterative solver options available as "plug-and-

    play" components in various problem solving environments. Choosing the right solver

    configuration from the available choices is critical for ensuring convergence and achieving

    good performance, especially for large complex matrices. However, identifying the

    "best" preconditioned iterative solver and parameters is challenging even for an expert due

    to issues such as the lack of a unified theoretical model, complexity of the solver configuration

    space, and multiple selection criteria. Therefore, it is desirable to have principled

    practitioner-centric strategies for identifying solver configuration(s) for solving large linear

    systems.

    The current dissertation presents a general practitioner-centric framework for (a) problem

    independent retrospective analysis, and (b) problem-specific predictive modeling of

    performance data. Our retrospective performance analysis methodology introduces new

    metrics such as area under performance-profile curve and conditional variance-based finetuning

    score that facilitate a robust comparative performance evaluation as well as parameter

    sensitivity analysis. We present results using this analysis approach on a number of popular

    preconditioned iterative solvers available in packages such as PETSc, Trilinos, Hypre, ILUPACK, and WSMP. The predictive modeling of performance data is an integral part

    of our multi-stage approach for solver recommendation. The key novelty of our approach

    lies in our modular learning based formulation that comprises of three sub problems: (a)

    solvability modeling, (b) performance modeling, and (c) performance optimization, which

    provides the flexibility to effectively target challenges such as software failure and multiobjective

    optimization. Our choice of a "solver trial" instance space represented in terms

    of the characteristics of the corresponding "linear system", "solver configuration" and their

    interactions, leads to a scalable and elegant formulation. Empirical evaluation of our approach

    on performance datasets associated with fairly large groups of solver configurations

    demonstrates that one can obtain high quality recommendations that are close to the ideal

    choices.

publication date

  • December 2009