close

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]=
Image

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]=
Image

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]=
Image

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]=
Image

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]=
Image

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]=
Image

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]=
Image

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]=
Image

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

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

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

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

Possible Issues (1) 

A system need not have an integer-valued solution:

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

Version History

  • 1.0.0 – 05 November 2019

Source Metadata

Related Resources

License Information