The program 'birkhoff' calculates the Earhart polynomial, or just the top
coefficient, of the birkhoff polytope.  The methods involved are general
enough that it can be adapted to calculate a number of similar quantities.
As an example, this version of the program also counts the number of
integral points in a "transportation polytope."

----------------------------------------------------------------------

Installation:

I have successfully compiled this on a Linux system (RedHat 7.2) and on a
Windows system using the Cygwin environment.  In both cases I used gcc.
One non-standard package must be available:  gmp, the GNU MP library for
arbitrary precision arithmetic.  This is available from
http://www.gnu.org/software/gmp/gmp.html.  I am using version 4.0.

NOTE: gmp must be compiled with C++ support.  To enable this, the
'--enable-cxx' option must be passed to configure.

----------------------------------------------------------------------

Version 1.0a:

I made a few minor changes (on 3/31/04) to get the program to compile with
newer releases of gcc and gmp; the modified version is 1.0a.  The files in
this directory are the newer files.  I have compiled and tested this version
with gcc-3.2.2-5 and gmp-4.1.2-13.

The older version 1.0 is still available in SOURCE-old.tar.gz and
SOURCE-old.zip.

----------------------------------------------------------------------

Usage:

birkhoff [options] [path or margins]

Options for computing the Earhart polynomial, or just the top coefficient,
or one of the integrals resulting from the initial expansion (a "path"
integral -- and this has nothing to do with integration along a path!):

-u n	integrate all strictly upper triangular paths for given n
-w n	integrate all upper triangular paths for given n
-a n	integrate all paths for given n

Note: all integrals specified by -w or -a which are not specified by -u will
evaluate to 0, so -w and -a are practically useless.

-f	use factoring if possible
-z	look harder for zero integrals -- probably a win on large problems,
	but not always effective, and sometimes a slight loss
-p	calculate and display the full polynomial

-b	show the full result as a sum of products of binomials
	     each term is also expanded as a polynomial if -p is specified
	     this does not collect terms, and presents them in
	     the order calculated
-n	show the full result as a sum of products of binomials, but with 
	     constant binomials evaluated as integers
	     each term is also expanded as a polynomial if -p is specified
	     this collects terms and presents the output sorted (somewhat
	     arbitrarily).  this can use a lot of memory.

-l	list the starting integrands.  if repeated (-ll) exit after listing

-m x	use method x to calculate integrals; values for x are

	i   "interior" integrals only, variables in order (1,2,3,...),
	    no factoring
	        this is the slowest method
	e   "exterior" integrals only, variables in reverse order
	    no factoring
	b   branchcount: choose either exterior or interior integral, based
	    on an evaluation of the number of terms that will be generated
	    and whether factoring is possible
	    it only looks one step ahead
	        this is the default method
	t   top coefficient: this follows method b, but discards integrals
	    that cannot contribute to the top coefficient, both in
	    calculating and in evaluating
	q   query: this is interactive: it presents the evaluation of
	    each integral and asks the user to specify the variable,
	    direction and (optionally) factorization to use

-t	generates lots of hard to read and confusing trace output.

-q	suppresses the internal statistics that are usually printed

-v	prints the version number and exits

-h	prints a short usage message and exits

-e range
	prints evaluations of the polynomial for variables in the given
	range, which must be in the form start:stop (no spaces)

-s num	if specifying a single path (see below) use num as a numeric
	coefficient.  

Note: the top coefficient is always printed.

If the problem isn't specified using -u or -w or -a then you can specify a
single integral as a space-separated path in the form m1 m2 ... mn where the
sum of the n terms is n.  

Options for computing the number of solutions of a tranportation problem.

These include the options above that make sense, along with the following:

-T      do a transportation problem

The problem is defined by specifying the margins -- these are the row and
column sums.  These are specified as two space-separated lists, separated by
":" (";" will also work, but must be quoted or escaped to hide it from the
shell).  So the form is a1 a2 ... am : b1 b2 ... bn