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.
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.
The following multiplies two dense matrices.
The following inverts a dense matrix. It uses Gauss-Jordan
elimination without pivoting.
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).
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
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.
Temporarily unavailable -- Being used as class assignment.
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).