Self-adapting numerical software (SANS) effort

IBM Journal of Research and Development, Mar-May 2006 by Dongarra, J, Bosilca, G, Chen, Z, Eijkhout, V, Et al

We provide a general discussion of the issues in dynamic algorithm selection and tuning, present our approach, which uses statistical data modeling, and give some preliminary results obtained with this approach. Our context here is the selection of iterative methods for linear systems in the SALSA system.

Dynamic algorithm determination

In finding the appropriate numerical algorithm for a problem, we are faced with two issues: First, there are often several algorithms that, potentially, solve the problem; second, algorithms often have one or more parameters of some sort. Thus, given user data, we have to choose an algorithm and choose a proper parameter setting for it. Our strategy in determining numerical algorithms by statistical techniques is globally as follows:

* We solve a large collection of test problems by every available method, that is, every choice of algorithm, and a suitable binning (or categorizing) of algorithm parameters.

* Each problem is assigned to a class corresponding to the method that gives the fastest solution.

* We draw up a list of characteristics of each problem.

* We then compute a probability density function for each class.

As a result of this process, we find a function p^sub i^(x) where i ranges over all classes, that is, all methods, and x is in the space of the vectors of features of the input problems. Given a new problem and its feature vector x, we then decide to solve the problem with the method i for which p^sub i^(x) is maximized.

We now discuss the details of this statistical analysis and present some proof-of-concept numerical results evincing the potential usefulness of this approach.

Statistical analysis

In this section we give a short overview of the way in which a multivariate Bayesian decision rule can be used in numerical decision making. We stress that statistical techniques are merely one of the possible ways of using non-numerical techniques for algorithm selection and parameterization, and the technique we describe here is, in fact, only one among many possible statistical techniques. We describe here the use of parametric models, a technique with obvious implicit assumptions that very likely will not hold overall, but, as we show in the next section, have surprising applicability.

Feature extraction

The basis of the statistical decision process is the extraction of features from the application problem and the characterization of algorithms in terms of these features. In [36] we have given examples of relevant features of application problems. In the context of linear and nonlinear system solving, we can identify at least the following categories of features: structural features pertaining to the nonzero structure, simple quantities that can be computed exactly and cheaply, spectral properties that have to be approximated, and measures of the variance of the matrix.

Training stage

On the basis of the feature set described above, we now engage in an expensive and time-consuming training phase in which a large number of problems is solved by every available method. For linear system solving, methods can be described as an orthogonal combination of several choices: the iterative method, the preconditioner, and preprocessing steps, such as scaling or permuting the system. Several of these choices involve numerical parameters, such as the generalized minimal residual (GMRES) restart length or the number of incomplete LU factorization fill levels.