[Shootout-list] Organisation for numerical tests

[Jon Harrop]

On Tuesday 03 May 2005 22:29, Sebastien Loisel wrote:
> Ok, here's some scientific computing tests. Please contribute any of
> your suggestions.

I think this is an excellent idea. These benchmarks are representative of only 
part of scientific computing (numerical analysis, as the subject implies), of 
course. I'd like to see non-numerical (e.g. combinatorial optimization, 
shortest-path rings) and semi-numerical (e.g. relax, computational geometry) 
benchmarks as well. Such benchmarks shouldn't fill the FP-intensive quota (if 
any). However, there is some overlap so perhaps we should discuss them all at 
the same time?

>    1. FFT - performs a complex 1D fast Fourier transform
>    4. MM - multiplies two sparse matrices in compressed-row format

These are exactly the kinds of things that I'd farm out to an existing library 
if I were coding a solution to a problem myself, so I'd question their 
practical applicability (not their theoretical applicability, of course).

Perhaps the discrete wavelet transform would be better than the FFT as it is 
less common and the choice of library is much less clear-cut (AFAIK). Also, I 
think it will be feasible to do a non-integer-power-of-two FWT but not FFT.

>    2. SOR - solves the Laplace equation in 2D by successive over-relaxation

Good idea. Ideally, I'd like to see this produce an aesthetic diagram which 
the shootout site could display as a graphical representation of the "correct 
answer". That should be easy enough to do and would attract attention.

>    3. MC - computes pi by Monte Carlo integration

If this were computing something more useful than pi (meaning something that 
people might actually want to compute this way) then I'd like this sort of 
thing. Maybe we compute a useful physical quantity from an atomic simulation? 
Something entropic maybe?

Also, for such a trivial problem this is likely to become a slightly more 
sophisticated version of "random". Perhaps it should replace random?

>    5. LU - computes the LU factorization of a dense N x N matrix
> * dense LU
> * computing all eigenvalues/eigenvectors
> * singular value decomposition

Again, I have the practical concern that nobody would want to implement these 
themselves as they'd just use an existing library (LAPACK). More importantly, 
I have the theoretical concern that the performance measurements from these 
benchmarks will be hugely susceptable to slight algorithmic differences and 
any numerical instabilities, so it may prove practically impossible to 
compare equivalent implementations in many languages.

> * multipole

Yes, I'd like to see tree-based algorithms as they are more interesting to me 
and are likely to be more rewarding for others.

There is a very simple multipole-like example in my book, where the forces of 
a set of particles in a 1D system is computed via a tree rather than an 
array. For an accuracy of 1 part in 1 million, the tree-based method is 
1,000x faster than the array-based method.

> * Conjugate Gradient

It would be interesting to see this coded in different languages but, in terms 
of performance, you'd either be measuring the time taken to evaluate the 
function(s) or measuring the difference in performance of different 
algorithms.

> * Newton iteration

I think this could be interesting but I'd like to see it as part of something 
bigger. Maybe a torus renderer made from my ray tracer?

Perhaps my "relax" benchmark would fit the bills of both CG and Newton nicely 
(although it wouldn't use either of these methods). It is practically 
important, slightly more complicated (including some not-completely-trival 
data structures) and is based upon the same foundation.

> * Automatic differentiation

What exactly do you mean by this?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists