cmu-1.9: Unification in a Commutative Monoid

Algebra.CommutativeMonoid.LinDiophEq

Description

Linear Diophantine Equation solver.

The solver uses the algorithm of Contejean and Devie as specified in "An Efficient Incremental Algorithm for Solving Systems of Linear Diophantine Equations", Information and Computation Vol. 113, pp. 143-174, 1994.

The algorithm for systems of homogeneous linear Diophantine equations follows. Let e[k] be the kth basis vector for 1 <= k <= n. To find the minimal, non-negative solutions M to the system of equations sum(i=1,n,a[i]*v[i]) = 0, the algorithm of Contejean and Devie is:

1. [init] A := {e[k] | 1 <= k <= n}; M := {}
2. [new minimal results] M := M + {a in A | a is a solution}
3. [unnecessary branches] A := {a in A | all m in M : some 1 <= k <= n : m[k] < a[k]}
4. [breadth-first search] A := {a + e[k] | a in A, 1 <= k <= n, <sum(i=1,n,a[i]*v[i]),v[k]> < 0}
5. [test] If A = {}, stop, else go to 2.

This module provides a solver for a single linear Diophantine equation a*v = b, where a and v are vectors, not matrices.

When solving an inhomogeneous equation, it uses the homogeneous solver after adding -b as the first element of v and by bounding the first element of a to be one at each step in the computation. The first element of a solution is zero if it is a solution to the associated homogeneous equation, and one if it is a solution to the inhomogeneous equation.

The algorithm is likely to be Fortenbacher's algorithm, the one generalized to systems of equations by Contejean and Devie, but I have not been able to verified this fact.

Synopsis

# Documentation

linDiophEq :: [Int] -> Int -> [[Int]]Source

The `linDiophEq` function takes a list of integers that specifies the coefficients of linear Diophantine equation and a constant, and returns the equation's minimal, non-negative solutions.

When solving an inhomogeneous equation, the first element of a solution is zero if it solves the associated homogeneous equation, and one otherwise.

Thus to solve 2x + y - z = 2, use

``` linDiophEq [2,1,-1] 2 = [[0,0,1,1],[1,1,0,0],[0,1,0,2],[1,0,2,0]]
```

The two minimal solutions to the homogeneous equation are [0,1,1] and [1,0,2], so any linear combinations of these solutions contributes to a solution. The solution that corresponds to [1,0,0] is x = w + 1, y = v, and z = v + 2w. The solution that corresponds to [0,2,0] is x = w, y = v + 2, and z = v + 2w.