Implementing the Conjugate Gradient Algorithm in a Functional Language
Pascal R. Serrarens

Computer Science Institute
University of Nijmegen, The Netherlands
e-mail: pascalrs@cs.kun.nl

Abstract. This paper evaluates the elegance and efficiency of functional
programming in numerical scientific computing, an interesting area be-
cause time and space efficiency are important: many scientific programs
work with large data sets and run for a long time. The example we use is
the conjugate gradient algorithm, an iterative method to solve systems
of linear equations. We investigated various implementations of the algo-
rithm in the functional languages Clean and Haskell and the imperative
language C. Good results are obtained when comparing the algorithm
written in Clean with the same algorithm in C and Haskell.
The expressive power of functional programming languages seems to equal
to that of traditional imperative languages, while many current compilers pro-
duce time- and space-efficient code, using various optimisations including the
important update-in-place. Two traditionally weak points of functional language
implementations are speed and memory usage, which are very important in nu-
merical scientific computing. The ``pseudoknot'' paper [H + 96] showed that, for a
numerical algorithm, only a couple of functional-language compilers could pro-
duce code comparable with to that produced by C compilers.
In this paper we investigate writing the conjugate gradient algorithm in the
general purpose lazy functional language Clean [PvE93] and compare it against
similar implementations in C and Haskell [HPJW92]. In Section 1 we will look
at the algorithm itself. We look how the choice of data structure influences the
performance in Section 2. We describe some optimisations that yield an efficient
implementation in Section 3. In Section 4 we compare our implementation in
Clean with implementations in the languages C and Haskell, while Section 5
concludes.