cmu-1.7: Unification in a Commutative Monoid

Safe Haskell Safe-Infered

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 after a modification explained below.

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 modified 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. [breadth-first search] A := {a + e[k] | a in A, 1 <= k <= n, <sum(i=1,n,a[i]*v[i]),v[k]> < 0}
4. [unnecessary branches] A := {a in A | all m in M : some 1 <= k <= n : m[k] < a[k]}
5. [test] If A = {}, stop, else go to 2.

The original algorithm reversed steps 3 and 4.

This module provides a solver for a single linear Diophantine equation a*v = b, where a and v are vectors, not matrices. Conceptually, it uses the homogeneous solver after appending -b as the last element of v and by appending 1 to a at each step in the computation. The extra 1 is omitted when an answer is produced.

Steps 3 and 4 were switched because the use of the original algorithm for the problem 2x + y - z = 2 produces a non-minimal solution. linDiophEq [2,1,-1] 2 = [[1,0,0],[0,2,0]], but the original algorithm produces [[1,0,0],[0,2,0],[1,1,1]].

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. I learned how to extend Contejean and Devie's results to an inhomogeneous equation by reading "Effective Solutions of Linear Diophantine Equation Systems with an Application to Chemistry" by David Papp and Bela Vizari, Rutcor Research Report RRR 28-2004, September, 2004, http://rutcor.rutgers.edu/pub/rrr/reports2004/28_2004.ps.

The example that shows a problem with the original algorithm follows. For the problem linDiophEq [2,1,-1] 2, the value of a and m at the beginning of the loop is:

```                    a                                 m
[[0, 0, 1], [0, 1, 0], [1, 0, 0]]       []
[[0, 1, 1], [0, 2, 0]]                  [[1, 0, 0]]
[]                                      [[1, 0, 0], [0, 2, 0]]
```

Consider [0, 1, 1] in a. If you remove unnecessary branches first, the element will stay in a. After performing breadth-first search, a will contain [1, 1, 1], which is the unwanted, non-minimal solution.

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, solve the related homogeneous equation and add in those solutions.