As stated above, the user would ideally like a simple formula, or perhaps a program, that would predict the running time as a function of a few simple facts about the problem to be solved, and the computer to be used to solve it. This implies that we need to build performance models for all the algorithms we provide. Realistically, for some dense algorithms we will be able to give operation counts, dependent on the size and mathematical properties of the problem to be solved, the information desired by the user, and perhaps some rough properties of the operator, like the clustering of the spectrum. For sparse problems, we can do the same for the inner loop of the iteration, counting operations like matrix-factorizations, matrix-vector multiplies, dot products, saxpys, and so on.

For particular machines, we can provide Matlab scripts to actually estimate
running times in terms of a few machine parameters, like megaflop rate
(for the 3 levels of BLAS), number of processors and
communication costs (for parallel machines),
matrix dimension, layout (on parallel machines), information desired by the
user, and so on. There are two basic approaches to
producing such performance models (hybrids are possible too). The first
is *intrinsic*, which uses operation counts plus simpler models for the
costs of each operation (BLAS operations and communication), and the second
is *extrinsic*, which simply does curve fitting of benchmark runs.
Intrinsic models are more difficult to produce, may be less accurate in
certain extreme cases, but are more flexible and illuminating than
extrinsic models.

Wed Jun 21 02:35:11 EDT 1995