Newman
----------------------
This package contains a parallel implementation (using the LAM implementation of the MPI
specification) of Newman's algorithm for the exact solution of linear systems of equations
over the integers.

Installation
----------------------
Since the code deals with large integers, we use the gmp (GNU MP) library for arbitrary
precision arithmetic.  The code has been tested with libgmp version 2.0.2.  Since this is
a parallel program, we also require an implementation of the MPI specification.  The scripts
provided to generate runtime data and run automated tests assume that the user is using the
LAM package (this has been tested with LAM 6.5.8), although in theory, any implementation
of the MPI specification should work.

The user may download these two packages at the following URLs:

libgmp:	ftp://mirrors.kernel.org/gnu/gmp/
lam:	http://www.lam-mpi.org/download/

Once these have been installed, the package should be decompressed by running
	gzip -cd newman.tar.gz | tar -xf -

Compilation is then accomplished by running make in the created directory ./newman/

Running
----------------------
The scripts/ directory contains a number of scripts which make running and testing
the code simple.  A description of the files contained in this directory and their
purposes follows:

	FILE		DESCRIPTION
        ---------------------------------------------------------------------------------
	analyze		Intermediary script for the collection of runtime data.
	average		Intermediary script for the collection of runtime data.
	generate_data	Intermediary script for the collection of runtime data.
			Runs the code on automatically generated matrices of specified
			sizes.
	hankel		Produces hankel matrices.
	ones		Produces matrices with entries -/+ 1.
	pascal		Produces pascal matrices.
	random		Produces random matrices.
	run		Runs the code on an input file test.data
	run_experiment	Begins the collection of runtime data.  Generates a set of files
	toeplitz	Produces toeplitz matrices.

In order to run the code, the MPI environment must first be initialized.  See the specific
implementation documentation for detailed instructions.  In the case of LAM, documentation
is available in the lamboot(1) manual page.  The ``run'' script described above may then
be used to run the code on an input file ``test.data'' in the directory in which
the package was decompressed. (The user should be in this directory and execute ``scripts/run''
from the command line).

A sample of the automated tests may be run by initializing the MPI environment and running
scripts/run_experiment pascal '10 15 20 25 30'
This creates a directory test containing the results of timing the execution of the code solving
the pascal matrices of sizes 10, 15, 20, 25, and 30 for 10 trials.  The data is then extracted and
averaged to produce a file test/pascal.data containing the average times for each problem size, as well
as the number of singular subproblems encountered.

Input File
----------------------
The input file is formatted as follows.

<n>
<a_11> <a_12> . . . <a_1n>
<a_21> <a_22> . . . <a_2n>
.
.
.
<a_n1> <a_n2> . . . <a_nn>
<b_1> <b_2>   . . . <b_n>

where <a_ij> denotes the (i,j)th element of the matrix
and <b_i> denotes the ith element of the right hand side
vector.

A sample input describing the problem

( 1 0 0 )(x_1)   (1)
( 0 1 0 )(x_2) = (2)
( 0 0 1 )(x_3)   (3)

would then look like:

----------
3
1 0 0
0 1 0
0 0 1
1 2 3
----------

Output Format
----------------------
The output consists of a single integer followed by an integer
vector of size n.  The solution vector may be obtained by dividing
each element of the integer vector by the first integer.

Algorithm
----------------------
The algorithm is a straightforward parallelization of the algorithm
described in 

Newman, M. Solving Equations Exactly. J. Res. Nat. Bur. Standards Sect. B 71B 1967 171--179.

Newman established the following result:

(Newman) Let $d=det(A)$, $y=A^{adj}b$. Suppose $m \in Z$ satisfies $(m,d)=1$ and
 $m>2\max(|d|,M(y))$, where $M(y)$ denotes the maximum element of $y$.  Then any
 $d_m, y_m$ satisfying \[ d\equiv d_m \pmod{m} \]
 \[ Ay_m\equiv db \pmod{m} \] and $|d_m|<\frac{m}{2}, M(y_m)<\frac{m}{2}$ must 
 equal $d,y$.

Newman's insight was to apply the Chinese Remainder Theorem to this problem, so that
we choose a set of primes such that their product is equal to the m in the theorem.  We
then may solve each of these problems *independently* in O(n^3) time using a variant of
Gaussian elimination modified to work in the integers modulo a prime.  It is this Independence
of the subproblems that makes our parallel implementation feasible.

Future research lies in the establishment of an appropriate condition number for this method (similar
to the ratio of largest to smallest eigenvalues for the numerical stability of Gaussian
elimination), as well as investigating the possibility of more efficient computation through the use
of relatively prime factors (since the Chinese Remainder Theorem only requires that the moduluses be 
relatively prime).