Parallel numerical algorithms

This page contains a collection of parallel numerical algorithms. It includes a brief description of each algorithm along with the NESL code. These algorithms have been developed by the Scandal project.

If you have arrived here via a search engine, we suggest going to the toplevel algorithms page.

Fast Fourier Transform

This is a simple parallel version of the standard sequential fast Fourier transform algorithm. The algorithm does O(n log n) work and has O(log n) depth.

In the code we first give a general FFT that works with any commutative ring that has primitive nth roots of unity. In the code we first give a general FFT that works with any commutative ring. As well as the data, this FFT takes as arguments the n different nth-roots of unity (an array w) and the +, * functions on the ring (add, mult). We then specialize the algorithm to a particular commutative ring---the complex numbers.

Matrix Multiply

The following multiplies two dense matrices.

Matrix Inverse

The following inverts a dense matrix. It uses Gauss-Jordan elimination without pivoting.

Linear Solve

The following solves a linear system of the form Ax = b. It uses Gauss-Jordan elimination without pivoting (the same routine as used in Matrix Inversion above).

Null space of a dense Matrix

The following algorithm finds a nontrivial vector in the null space of a dense matrix, if it has one (i.e. a weighted sum of the rows that adds to all zeros). If it does not have one then a vector of zero's is returned.

Line Fit

This is an algorithm for fitting a set of (x,y) data points to a line. It is based on the chi-square method described in Numerical Recipes (Press et. al., Cambridge University Press, 1987, Section 14.2). It returns the intercept a, the slope b, as well as the sigma for both a and b. The sigmas are the fitted standard deviations (an approximate +- error bound). For n points the algorithm does O(n) work and has constant depth.

Sparse-Matrix Vector Multiply


Conjugate Gradient

Temporarily unavailable -- Being used as class assignment.

Prime Numbers

The following algorithm generates the primes up to n (not inclusive). It works using a primes sieve algorithm, by first generating the primes up to sqrt(n) and then using those to sieve the values up to n. It has work O(n log log n) and depth O(log log n).