Salsa Adaptive Large-scale Solver Architecture (SALSA)

Overview

SALSA is a software project that aims to assist applications in finding suitable linear and nonlinear system solvers based on analysis of the application-generated data. The SALSA system features heuristic decision making, based on a database of performance results that can tune the heuristics over time.

In various areas of numerical analysis, there are several possible algorithms for solving a problem. Examples are the various direct and iterative solvers for sparse linear systems, or routines for eigenvalue computation or numerical optimization. Typically, there is no governing theory for finding the best method, or the theory is in essence uncomputable. For instance, in iterative linear system solving, there are many preconditioners and iterative schemes; the convergence behaviour is determined by the decomposition of the right-hand side in terms of the eigenvectors of the preconditioned operator. However, computing this spectrum is expensive, and the dependency of the iterative cheme on this decomposition is not known in explicit form. Thus, the choice of the optimal method is in practice determined by experimentation and ‘numerical folklore'. However, a more systematic approach is needed, for instance since such choices may need to be made in a dynamic context such as a time-evolving system. We propose tackling this situation by the application of various automatic learning techniques. Such methods perform mining of the roblem eatures, typically relying on a database of prior knowledge, in order to recommend a suitable method. The SALSA system is a collection of interaction software components.

The SALSA project was joint work with Erika Fuentes (now at Microsoft), performed at the University of Tennessee, Knoxville and at TACC. Other participants were David Keyes, Yoav Freund, Thomas Eidson, Sanjukta Bhowmick./p>

People

The unassembled hyper-matrices project is a collaboration between:

• Victor Eijkhout (PI), Texas Advanced Computing Center
• Robert van de Geijn (co-PI), Department of Computer Science, and Institute for Computational Engineering and Sciences
• Leszek Demkowicz (advisor), Department of Aerospace Engineering and Engineering Mechanics, and Institute for Computational Engineering and Sciences
• Kyungjoo Kim (graduate student), Department of Aerospace Engineering

Downloads

Our software can be downloaded from SourceForge. The following packages are available:

• NMD: the Numerical MetaData library. This supplies routines for managing a two-level object for storing numerical metadata in categories containing elements.
• AndMod: the Analysis Modules library. This contains a large number of routines for computing numerical metadata.
• SysPro: the System preProcessors. This is the testbed for iterating over various linear system preprocessors (scaling, permutation, preconditioning) before solving the system.
• Salsa: the main program that integrates all these libraries.

Publications

• Machine Learning for Multi-stage Selection of Numerical Methods, with Erika Fuentes

  @INCOLLECTION{EijkFuen2010:multistage,
  author = {Victor Eijkhout and Erika Fuentes},
  title = {Machine Learning for Multi-stage Selection of Numerical Methods},
  booktitle = {Machine Learning},
  publisher = {Intech},
  year = {2010},
  note = {To appear} }

• Multi-stage Learning of Linear Algebra Algorithms, with Erika Fuentes

  @INPROCEEDINGS{EijkFuen:icmla2008,
  author = {Victor Eijkhout and Erika Fuentes},
  title = {Multi-stage Learning of Linear Algebra Algorithms},
  booktitle = {International Conference on Machine Learning and its Applications, San Diego, CA, 11-13 December 2008},
  year = {2008} }