cmu-1.3: Unification in a Commutative Monoid

Algebra.CommutativeMonoid.HomLinDiaphEq

Description

Homogeneous Linear Diaphantine Equation solver.

The solver uses the algorithm of Contejean and Devie as specified by David Papp and Bela Vizari in "Effective Solutions of Linear Diophantine Equation Systems with an Application to Chemistry", Rutcor Research Report RRR 28-2004, September, 2004, http://rutcor.rutgers.edu/pub/rrr/reports2004/28_2004.ps, after modification so as to ensure every basis vector is considered.

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. [test] If A = {}, stop
  5. [breadth-first search] A := {a + e[k] | a in A, 1 <= k <= n, <sum(i=1,n,a[i]*v[i]),v[k]> < 0}; go to step 2

Synopsis

Documentation

homLinDiaphEq :: [Int] -> [[Int]]Source

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