0
$\begingroup$

SHORT VERSION

Given 2t Ranges, each of length len, what is the fastest way of finding the tuples created from these Ranges that satisfy the constraints in the 5-point list below? 2t is in the range 10-15, len is typically 5 or 7. Filtering the output of Tuples is not viable because that output is often much too large to hold in RAM.

LONG VERSION

Background

While working on finding the constrained maxima of some functions in 2*t variables, I am evaluating the functions over a part of a square 2t-dimensional grid. The part of the grid I'm interested in satisfies the following constraints: Assume t == n1 + n2 with n1 <= n2, and denote the 2t variables x[i], i = Range[2t]. Then

  1. x[i] <= x[i + 1] for 1 <= i <= n1 - 1
  2. x[i] <= x[i + 1] for n1 + 1 <= i <= t
  3. x[i]^2 + x[i + t]^2 <= x[n1 + 1]^2 for n1 + 2 <= i <= t
  4. x[n1 + 1] <= 0
  5. x[n1 + 1 + t] == 0

During my code, I am "zooming" in on parts of the grid, so that at a particular time I may have the following ranges available for the coordinates:

SeedRandom[0];
n1 = 2;
n2 = 3;
t = n1 + n2;
len = 4;
ranges = Range[#, # + len] & /@ 
   RandomInteger[{-10, 10 - len}, 2 t - 2];
ranges = Insert[
  Insert[ranges, Range[#, # + len] &@RandomInteger[{-10, 0 - len}], 
   1], {0}, n1 + 1 + t]

With this, constraints 4 and 5 are already satisfied.

The two approaches

In order to find the tuples that satisfy the rest of the constraints, I may either

  1. create all tuples with Tuples and then filter them according to the constraints, or
  2. I can try to bake in the constraints from the start, perhaps using Table with restrictions on iterator values.

For 1., I have tried:

tup = Tuples[ranges];
cons3ok = Pick[tup,
  With[{squared = Transpose[tup^2]},
   Plus @@ (
     UnitStep@
      Chop@Table[
        squared[[n1 + 1]] - squared[[i]] - squared[[t + i]], {i, 
         n1 + 2, t}])
   ], n2 - 1];
valid = Select[
  cons3ok, (OrderedQ[Take[#, {1, n1}]] && 
     OrderedQ[Take[#, {n1 + 1, t}]]) &];

This works well for small t because Tuples is so incredibly fast, but as t grows Tuples suffers from the curse of dimensionality, so I use up all my RAM storing the intermediate tup.

For 2. I made recursive use of Table; it's long, but the constraints are easy to "read off":

recTable[ind_] :=
 Which[
  ind == 1, 
  Table[recTable[ind + 1], {x[ind], ranges[[1, 1]], 
    ranges[[1, -1]]}],
  ind <= n1, 
  Table[recTable[ind + 1], {x[ind], Max[ranges[[ind, 1]], x[ind - 1]],
     ranges[[ind, -1]]}],
  ind == n1 + 1, 
  Table[recTable[ind + 1], {x[ind], ranges[[ind, 1]], 
    ranges[[ind, -1]]}],
  ind <= t, 
  Table[recTable[ind + 1], {x[ind], Max[ranges[[ind, 1]], x[ind - 1]],
     Min[ranges[[ind, -1]], -x[n1 + 1]]}],
  ind <= n1 + t, 
  Table[recTable[ind + 1], {x[ind], ranges[[ind, 1]], 
    ranges[[ind, -1]]}],
  ind <= 2 t, 
  Table[recTable[ind + 1], {x[ind], 
    Max[ranges[[ind, 1]], Ceiling[-Sqrt[x[n1 + 1]^2 - x[ind - t]^2]]],
     Min[ranges[[ind, -1]], Floor[Sqrt[x[n1 + 1]^2 - x[ind - t]^2]]]}],
  ind == 2 t + 1, Array[x, 2 t]
  ]

valid2 = Flatten[recTable[1], 2 t - 1];

This should not eat up all my RAM as quickly as 1., but it's a lot slower than using Tuples...

QUESTION

How can I improve either of the methods (or create a new one altogether) such that I don't spend all my RAM, and still get a result without waiting for days? I'm hoping for results with n1 = 3, n2 = 5.

Also, how can Tuples be so much faster than using Table or Outer? Am I messing something up?

$\endgroup$
  • $\begingroup$ Might CylindricalDecomposition help? $\endgroup$ – mikado Aug 23 '16 at 22:35
  • $\begingroup$ I have a look at this, but I'm put of trying further as I think that there are mistakes in your problem specification. E.g. what is tot? $\endgroup$ – mikado Aug 24 '16 at 19:34
  • $\begingroup$ @mikado, sorry for the typos, corrected now I think $\endgroup$ – Marius Ladegård Meyer Aug 24 '16 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.