Application of alternating decision trees in selecting sparse linear solvers

Sanjukta Bhowmick, Victor Eijkhout, Yoav Freund, Erika Fuentes, David Keyes

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Scopus citations


The solution of sparse linear systems, a fundamental and resource-intensive task in scientific computing, can be approached through multiple algorithms. Using an algorithm well adapted to characteristics of the task can significantly enhance the performance, such as reducing the time required for the operation, without compromising the quality of the result. However, the best solution method can vary even across linear systems generated in course of the same PDE-based simulation, thereby making solver selection a very challenging problem. In this paper, we use a machine learning technique, Alternating Decision Trees (ADT), to select efficient solvers based on the properties of sparse linear systems and runtime-dependent features, such as the stages of simulation. We demonstrate the effectiveness of this method through empirical results over linear systems drawn from computational fluid dynamics and magnetohydrodynamics applications. The results also demonstrate that using ADT can resolve the problem of over-fitting, which occurs when limited amount of data is available.

Original languageEnglish (US)
Title of host publicationSoftware Automatic Tuning
Subtitle of host publicationFrom Concepts to State-of-the-Art Results
PublisherSpringer New York
Number of pages21
ISBN (Print)9781441969347
StatePublished - 2010
Externally publishedYes

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Application of alternating decision trees in selecting sparse linear solvers'. Together they form a unique fingerprint.

Cite this