Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 SmallIntegerLinearSolve

Source Notebook

Find a small solution to a system of linear equations over the integers

Contributed by: Daniel Lichtblau

ResourceFunction["SmallIntegerLinearSolve"][mat,rhs]

finds a small solution for x to the system of integer linear equations mat.x=rhs.

Details and Options

The solution size is based on the Euclidean length of the resulting integer vector x.
An exactly determined system over the integers will have at most one integer-valued solution vector.
When the system is underdetermined, a "small" solution might be found from among the infinitely many solutions; this is the intended use case.
The underlying method uses lattice reduction and is not guaranteed to give the smallest possible solution.
In practice, the given solution will be close to the smallest possible solution.

Examples

Basic Examples (2) 

Solve a linear system with integer values:

In[1]:=
ResourceFunction[ "SmallIntegerLinearSolve"][{{12, 3}, {2, 16}}, {186, 17298}]
Out[1]=

Set up a random system over the integers:

In[2]:=
SeedRandom[1111]; max = 10^8; dims = {3, 6}; mat = RandomInteger[{-max, max}, dims]; rhs = RandomInteger[{-max, max}, dims[[1]]];

Find a small integer solution:

In[3]:=
smallSoln = ResourceFunction["SmallIntegerLinearSolve"][mat, rhs]
Out[3]=

Compare to the parametrized result from Solve for the corresponding system of explicit linear equations:

In[4]:=
vars = Array[x, dims[[2]]]; solveSoln = First[vars /. Solve[mat . vars == rhs, vars, Integers]]
Out[4]=

Verify that the result of SmallIntegerLinearSolve is in the parametrized solution set:

In[5]:=
solveSoln = solveSoln[[All, 1]]; cvars = Variables[solveSoln]; FindInstance[smallSoln == solveSoln, cvars]
Out[5]=

Properties and Relations (6) 

Set up and solve a random system over the integers:

In[6]:=
SeedRandom[1111]; max = 10^20; dims = {6, 12}; mat = RandomInteger[{-max, max}, dims]; rhs = RandomInteger[{-max, max}, dims[[1]]]; smallSoln = ResourceFunction["SmallIntegerLinearSolve"][mat, rhs]
Out[6]=

Compare to the parametrized result from Solve for the corresponding system of explicit linear equations:

In[7]:=
vars = Array[x, dims[[2]]]; solveSoln = First[vars /. Solve[mat . vars == rhs, vars, Integers]][[All, 1]]; Short[solveSoln, 8]
Out[124]=

Verify that the small solution is in the parametrized solution set:

In[125]:=
cvars = Variables[solveSoln]; cvals = FindInstance[smallSoln == solveSoln, cvars, Integers][[1]]; {cvals, smallSoln == (solveSoln /. cvals)}
Out[125]=

Though it is far slower than SmallIntegerLinearSolve, one can find a minimal solution in terms of the 1-norm (sum of absolute values):

In[126]:=
newvars = Array[z, dims[[2]]]; constraints = Join[Thread[vars <= newvars], Thread[-vars <= newvars]]; {Timing[{min, vals} = Minimize[{Total[newvars], Flatten[{constraints, Thread[mat . vars == rhs]}]}, Join[vars, newvars], Integers];][[1]], newSmallSoln = vars /. vals}
Out[126]=

This new solution is indeed smaller in 1-norm than the small solution:

In[127]:=
Column[{Total[Abs[smallSoln]], Total[Abs[newSmallSoln]]}]
Out[127]=

However, the small solution happens to be the smaller in Euclidean norm:

In[128]:=
Column[{smallSoln . smallSoln, newSmallSoln . newSmallSoln}]
Out[128]=

Possible Issues (1) 

A system need not have an integer-valued solution:

In[129]:=
ResourceFunction["SmallIntegerLinearSolve"][{{2, 4}, {3, 6}}, {6, 7}]
Out[129]=

Version History

  • 1.0.0 – 05 November 2019

Source Metadata

Related Resources

License Information