Can apply Farkas' Lemma in the ISL?

[sen yang]

Hi ISL team and community,

I am working on polyhedral loop scheduling and trying to extract valid scheduling coefficients (e.g., c_i, c_j) for dependence relations using Farkas' Lemma.

Specifically, consider a dependence map defined as follows:

  [N] -> { S[j, i] -> S[i, j] : 2 <= j <= N and 1 <= i <= N and i - j >= 1 }

Can we use Farkas' Lemma directly in ISL/islpy to eliminate the loop variables (i, j) and derive the legal constraint space for (c_i, c_j), which should yield c_i - c_j >= 0?

I am not very familiar with ISL's internal C/Python APIs for Farkas dual representations. Could anyone share some insights or standard code examples on how to model this in ISL?😉

Best regards,
lonelyeagle

[Sven Verdoolaege]

On Thu, Aug 13, 2026 at 11:05:42PM +0800, sen yang wrote:
> Hi ISL team and community,
>
> I am working on polyhedral loop scheduling and trying to extract valid
> scheduling coefficients (e.g., c_i, c_j) for dependence relations using
> Farkas' Lemma.
>
> Specifically, consider a dependence map defined as follows:
>
> [N] -> { S[j, i] -> S[i, j] : 2 <= j <= N and 1 <= i <= N and i - j >= 1 }
>
> Can we use Farkas' Lemma directly in ISL/islpy to eliminate the loop
> variables (i, j) and derive the legal constraint space for (c_i, c_j),
> which should yield c_i - c_j >= 0?

In iscc syntax:

coefficients(deltas [N] -> { S[j, i] -> S[i, j] : 2 <= j <= N and 1 <= i <= N and i - j >= 1 });

result:

$0 := { rat: coefficients[[c_cst, c_N] -> S[c_j, c_i]] : c_N >= 0 and c_i <= c_N + c_j and c_i <= c_cst + 3c_N + c_j }

You would typically set c_N to zero.

isl_map_deltas is exported to the bindings, but isl_set_coefficients
is not.

skimo