# 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.