Max Number in isl_union_pw_qpolynomial

[Kelvin Yang]

I have a question about finding the maximal number in the isl_union_pw_qpolynomial.
For example, I have  isl_union_pw_qpolynomial: { T[i0, i1, i2, i3] -> (3 - i3) : i0 = 0 and i1 = 0 and i2 = 0 and 0 < i3 <= 2; T[i0, i1, i2, i3] -> (1 + i3) : i0 = 0 and i1 = 0 and i2 = 0 and i3 = 0 }.
That is, {
T[0, 0, 0, 1] -> 3-1=2
T[0, 0, 0, 2] -> 3-2=1
T[0, 0, 0, 0] -> 1+0=0
}
Therefore, the maximal number is 2 from T[0, 0, 0, 1] -> 3-1=2 of these 3 cases.
How can I get this information via isl functions?

[Sven Verdoolaege]

On Sun, Feb 12, 2023 at 04:41:04AM -0800, Kelvin Yang wrote:
> I have a question about finding the maximal number in the
> isl_union_pw_qpolynomial.
> For example, I have isl_union_pw_qpolynomial: { T[i0, i1, i2, i3] -> (3 -
> i3) : i0 = 0 and i1 = 0 and i2 = 0 and 0 < i3 <= 2; T[i0, i1, i2, i3] -> (1
> + i3) : i0 = 0 and i1 = 0 and i2 = 0 and i3 = 0 }.
> That is, {

> *T[0, 0, 0, 1] -> 3-1=2*

> T[0, 0, 0, 2] -> 3-2=1
> T[0, 0, 0, 0] -> 1+0=0
> }

> Therefore, the maximal number is *2* from *T[0, 0, 0, 1] -> 3-1=2 *of these

> 3 cases.
> How can I get this information via isl functions?

isl_union_pw_qpolynomial_bound can give you an upper bound
(and it will also tell you whether this upper bound is equal
to the maximum), however, it is not guaranteed to find
the maximum. In the cae of your example, it does.

skimo

[Kelvin Yang]

Thank you for the reply.
unique_access_num  is { T[i0, i1, i2, i3] -> (3 - i3) : i0 = 0 and i1 = 0 and i2 = 0 and 0 < i3 <= 2; T[i0, i1, i2, i3] -> (1 + i3) : i0 = 0 and i1 = 0 and i2 = 0 and i3 = 0 }
I tried 
    isl_union_pw_qpolynomial_fold *f = isl_union_pw_qpolynomial_bound(
        unique_access_num, isl_fold_max, NULL);
but I got "malloc(): memory corruption (fast)."
Did I pass the wrong value?

Sven Verdoolaege 在 2023年2月12日 星期日晚上8:54:42 [UTC+8] 的信中寫道：

[Kelvin Yang]

Oh, the bug is from other lines.
Thank you very much! This does return what I want.

Kelvin

Kelvin Yang 在 2023年2月12日 星期日晚上9:17:45 [UTC+8] 的信中寫道：

[Kelvin Yang]

How to compute the bound when it comes to wrapped relation in  isl_union_pw_qpolynomial?
For example, I have { [A[i0, i1] -> B[i2, i3, i4, i5]] -> (12 - 4 * floor((i1 + i5)/2)) : i0 = 1 and i2 = 0 and i3 = 0 and 0 <= i1 <= 1 and 0 <= i4 <= 2 and 4 <= i5 <= 5; [A[i0, i1] -> B[i2, i3, i4, i5]] -> (4 * i5 - 4 * floor((i1 + i5)/2)) : i0 = 1 and i2 = 0 and i3 = 0 and 0 <= i1 <= 1 and 0 <= i4 <= 2 and 0 < i5 <= 3; [A[i0, i1] -> B[i2, i3, i4, i5]] -> ((2 - 2 * i1) + 2 * floor((i1)/2)) : i0 = 0 and i2 = 0 and i3 = 0 and i5 = 1 and 0 <= i1 <= 1 and 0 <= i4 <= 2; [A[i0, i1] -> B[i2, i3, i4, i5]] -> 2 : i0 = 0 and i2 = 0 and i3 = 0 and i5 = 2 and 0 <= i1 <= 1 and 0 <= i4 <= 2; [A[i0, i1] -> B[i2, i3, i4, i5]] -> (((6 - 2 * i1) - 2 * i5) + 2 * floor((i1 + i5)/2)) : i0 = 0 and i2 = 0 and i3 = 0 and 0 <= i1 <= 1 and 0 <= i4 <= 2 and 3 <= i5 <= 4 }.
After using  isl_union_pw_qpolynomial_bound, I get { A[i0, i1] -> max((3 - i1)) : i0 = 0 and 0 <= i1 <= 1; A[i0, i1] -> max((8 - 2 * i1)) : i0 = 1 and 0 <= i1 <= 1 }.
That is, {A[0, 0] -> max(3); A[0, 1] -> max(2); A[1, 0] -> max(8); A[1, 1] -> max(6)}.

I have two questions:
1. How can I get {max(8)} from the previous output? 8 is greater than others.
2. Can I enumerate all elements in  isl_union_pw_qpolynomial_fold? For example, can I get {A[0, 0] -> max(3); A[0, 1] -> max(2); A[1, 0] -> max(8); A[1, 1] -> max(6)} instead of  { A[i0, i1] -> max((3 - i1)) : i0 = 0 and 0 <= i1 <= 1; A[i0, i1] -> max((8 - 2 * i1)) : i0 = 1 and 0 <= i1 <= 1 } since the function in max() is not easy to parsing.

Thank you!

Kelvin

Kelvin Yang 在 2023年2月12日 星期日晚上9:27:01 [UTC+8] 的信中寫道：

[Sven Verdoolaege]

On Mon, Feb 13, 2023 at 11:02:26PM -0800, Kelvin Yang wrote:
> How to compute the bound when it comes to wrapped relation in
> isl_union_pw_qpolynomial?
> For example, I have { [A[i0, i1] -> B[i2, i3, i4, i5]] -> (12 - 4 *
> floor((i1 + i5)/2)) : i0 = 1 and i2 = 0 and i3 = 0 and 0 <= i1 <= 1 and 0
> <= i4 <= 2 and 4 <= i5 <= 5; [A[i0, i1] -> B[i2, i3, i4, i5]] -> (4 * i5 -
> 4 * floor((i1 + i5)/2)) : i0 = 1 and i2 = 0 and i3 = 0 and 0 <= i1 <= 1 and
> 0 <= i4 <= 2 and 0 < i5 <= 3; [A[i0, i1] -> B[i2, i3, i4, i5]] -> ((2 - 2 *
> i1) + 2 * floor((i1)/2)) : i0 = 0 and i2 = 0 and i3 = 0 and i5 = 1 and 0 <=
> i1 <= 1 and 0 <= i4 <= 2; [A[i0, i1] -> B[i2, i3, i4, i5]] -> 2 : i0 = 0
> and i2 = 0 and i3 = 0 and i5 = 2 and 0 <= i1 <= 1 and 0 <= i4 <= 2; [A[i0,
> i1] -> B[i2, i3, i4, i5]] -> (((6 - 2 * i1) - 2 * i5) + 2 * floor((i1 +
> i5)/2)) : i0 = 0 and i2 = 0 and i3 = 0 and 0 <= i1 <= 1 and 0 <= i4 <= 2
> and 3 <= i5 <= 4 }.
> After using isl_union_pw_qpolynomial_bound, I get { A[i0, i1] -> max((3 -
> i1)) : i0 = 0 and 0 <= i1 <= 1; A[i0, i1] -> max((8 - 2 * i1)) : i0 = 1 and
> 0 <= i1 <= 1 }.
> That is, {A[0, 0] -> max(3); A[0, 1] -> max(2); A[1, 0] -> max(8); A[1, 1]
> -> max(6)}.
>
> I have two questions:
> 1. How can I get {max(8)} from the previous output? 8 is greater than
> others.

You could either do the original computation on [[] -> [A[] -> B[]]]
instead of on [A[] -> B[]], or you could perform
a second level bound computation
by calling isl_union_set_apply_union_pw_qpolynomial_fold
(as the first argument, you can take the domain of the second).

This is what the second looks like in iscc, with F the function above:

ub(F);
$0 := ({ A[i0, i1] -> max((3 - i1)) : i0 = 0 and 0 <= i1 <= 1; A[i0, i1] -> max((8 - 2 * i1)) : i0 = 1 and 0 <= i1 <= 1 }, False)
$0(dom $0);
$1 := ({ max(8) }, True)

> 2. Can I enumerate all elements in isl_union_pw_qpolynomial_fold? For
> example, can I get {A[0, 0] -> max(3); A[0, 1] -> max(2); A[1, 0] ->
> max(8); A[1, 1] -> max(6)} instead of { A[i0, i1] -> max((3 - i1)) : i0 =
> 0 and 0 <= i1 <= 1; A[i0, i1] -> max((8 - 2 * i1)) : i0 = 1 and 0 <= i1 <=
> 1 } since the function in max() is not easy to parsing.

You can iterate over the domain elements and then evaluate
the reduction over all those elements.
See isl_union_pw_qpolynomial_fold_at in iscc.c (in the barvinok repo)
for an example.

Of course, this only works if the domain has a finite number of elements.

skimo

[Kelvin Yang]

Hi Skimo,

I am confused about the output of isl_union_pw_qpolynomial_bound.
I pass the following isl_union_pw_qpolynomial to isl_union_pw_qpolynomial_bound:

isl_union_pw_qpolynomial:
{ [A[i0, i1] -> B[i2, i3, i4, i5]] -> 3 : i0 = 5 and i2 = 0 and i3 = 0 and i4 = 0 and 0 <= i1 <= 1 and 0 < i5 <= 2; [A[i0, i1] -> B[i2, i3, i4, i5]] -> ((5 + (-4 - 3 * i0) * floor((i0)/3) + 6 * floor((i0)/3)^2) + (1 + 3 * floor((i0)/3)) * floor((2 + i0)/3)) : i2 = 0 and i3 = 0 and i4 = 0 and 0 < i0 <= 4 and 0 <= i1 <= 1 and 0 < i5 <= 2; [A[i0, i1] -> B[i2, i3, i4, i5]] -> ((4 + (-2 + 2 * floor((i0)/3)) * floor((3 + i0)/6)) + -2 * floor((i0)/3) * floor((4 + i0)/6)) : i2 = 0 and i3 = 0 and i4 = 0 and 0 < i5 <= 2 and ((i0 = 0 and 0 <= i1 <= 2) or (i1 = 2 and 0 < i0 <= 4) or (i0 = 5 and i1 = 2)); [A[i0, i1] -> B[i2, i3, i4, i5]] -> ((((3 - 3 * floor((i0)/3)) + 3 * floor((2 + i0)/3)) + (-3 + 3 * floor((i0)/3)) * floor((3 + i0)/6)) + -3 * floor((i0)/3) * floor((4 + i0)/6)) : i2 = 0 and i3 = 0 and i4 = 0 and i5 = 0 and 0 < i0 <= 6 and 0 <= i1 <= 1 }

The output of  isl_union_pw_qpolynomial_bound:
{ A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 1 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 2 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 3 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 4 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 5 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 6 and 0 <= i1 <= 1; A[i0, i1] -> max(79/18) : i0 = 1 and i1 = 2; A[i0, i1] -> max(10/3) : i0 = 2 and i1 = 2; A[i0, i1] -> max((6 - 11/9 * i0 + 1/9 * i0^2)) : i1 = 2 and 3 <= i0 <= 4; A[i0, i1] -> max(2) : i0 = 5 and i1 = 2; A[i0, i1] -> max(4) : i0 = 0 and 0 <= i1 <= 2 }

To find the max number, I apply the isl_union_set_apply_union_pw_qpolynomial_fold as you mentioned before, and I get
{ max(23/3) }.

However, I think I don't have any fraction in isl_union_pw_qpolynomial. Did I miss something? I cannot understand why the max number isn't an integer.

Thank you!

Kelvin

Sven Verdoolaege 在 2023年2月15日 星期三清晨6:02:12 [UTC+8] 的信中寫道：

[Sven Verdoolaege]

Remember that isl_union_pw_qpolynomial_bound does not necessarily
compute a maximum. It computes an upper bound.
In this case, the bound is not tight.
If you know that the polynomial always evaluates to an integer,
it is safe to round down the upper bound value to an integer.

skimo

[Kelvin Yang]

Hi Skimo,

Thank you for the reply!

I know that my polynomial always evaluates to an integer.
Since it computes an upper bound if I round down the upper bound value to an integer, does that mean I can get the tight and least upper bound?
For example, In my previous example, I get { max(23/3) }, so that is {max(7)}. Does that mean I have at least one wrapped relation [A[...] -> B[...]] -> 7?

Another question is whether there is a function that can round down the value ({max(23/3)} is isl_union_pw_qpolynomial_fold).
Or do you think I should round it down manually?

Thank you.

Kelvin

Sven Verdoolaege 在 2023年3月17日 星期五凌晨12:53:24 [UTC+8] 的信中寫道：

[Sven Verdoolaege]

On Fri, Mar 17, 2023 at 05:52:17AM -0700, Kelvin Yang wrote:
> Hi Skimo,
>

> Thank you for the reply!
>
> I know that my polynomial always evaluates to an integer.
> Since it computes an upper bound if I round down the upper bound value to
> an integer, does that mean I can get the tight and least upper bound?

Not necessarily, no.
If the bound is not tight, there is no guarantee on the difference
between the maximum and the computed bound.
The only guarantee is that the result is indeed a bound.

> For example, In my previous example, I get { max(23/3) }, so that is
> {max(7)}. Does that mean I have at least one wrapped relation [A[...] ->
> B[...]] -> 7?

It looks like in your case, the actual maximum is 6.

> Another question is whether there is a function that can round down the
> value ({max(23/3)} is isl_union_pw_qpolynomial_fold).
> Or do you think I should round it down manually?

If you know that it's a constant (in particular, if you know
that there are no parameters), then you can simply evaluate
the function in its single domain element.
(In the case where the domain constains a single element,
isl_set_sample_point will give you that element.)
You can then round down the isl_val you obtain.

If you have a parametric expression, then there is no way
to round down the result. A quasi-polynomial is a polynomial
expression in quasi-affine expression, so you can have floors
inside the terms, but you can't represent a floor of a polynomial
expression.

skimo

[Kelvin Yang]

>   If the bound is not tight, there is no guarantee on the difference
between the maximum and the computed bound.

Is your "tight" here the same as the isl_bool *tight in isl_union_pw_qpolynomial_bound?
If I set the tight = 1, is there no difference between the maximum and the computed bound?
Getting the maximum or least upper bound is important for me instead of just an upper bound.

>   It looks like in your case, the actual maximum is 6.

The output of  isl_union_pw_qpolynomial_bound:
{ A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 1 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 2 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 3 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 4 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 5 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 6 and 0 <= i1 <= 1; A[i0, i1] -> max(79/18) : i0 = 1 and i1 = 2; A[i0, i1] -> max(10/3) : i0 = 2 and i1 = 2; A[i0, i1] -> max((6 - 11/9 * i0 + 1/9 * i0^2)) : i1 = 2 and 3 <= i0 <= 4; A[i0, i1] -> max(2) : i0 = 5 and i1 = 2; A[i0, i1] -> max(4) : i0 = 0 and 0 <= i1 <= 2 }

It seems that the {max(23/3)} is from i0=1 and then A[1, 0 or 1] -> max((25/3 - 2/3)) = max(23/3). So I get floor(23/3) = 7. Did you get six by other methods?

Recently, I found that in some cases,  isl_union_pw_qpolynomial_bound takes lots of time to solve. Is there a better method?

Thank you.

Kelvin

Sven Verdoolaege 在 2023年3月18日 星期六凌晨4:40:38 [UTC+8] 的信中寫道：

[Sven Verdoolaege]

On Mon, Mar 20, 2023 at 07:11:39AM -0700, Kelvin Yang wrote:
> > If the bound is not tight, there is no guarantee on the difference
> between the maximum and the computed bound.
>
> Is your "tight" here the same as the isl_bool *tight
> in isl_union_pw_qpolynomial_bound?

Yes.

> If I set the tight = 1, is there no difference between the maximum and the
> computed bound?

You mean, if you overwrite this output?
How could that have any effect?

> Getting the maximum or least upper bound is important for me instead of
> just an upper bound.

I'm not aware of any way of reliably obtaining that in general.
(Of course, if your domain consists of a finite number of point,
you could simply evaluate the polynomial in every point and
take the maximum.

> > It looks like in your case, the actual maximum is 6.
>
> The output of isl_union_pw_qpolynomial_bound:
> { A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 1 and 0 <= i1 <= 1; A[i0, i1]
> -> max((25/3 - 2/3 * i0)) : i0 = 2 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3
> - 2/3 * i0)) : i0 = 3 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0))
> : i0 = 4 and 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 5 and
> 0 <= i1 <= 1; A[i0, i1] -> max((25/3 - 2/3 * i0)) : i0 = 6 and 0 <= i1 <=
> 1; A[i0, i1] -> max(79/18) : i0 = 1 and i1 = 2; A[i0, i1] -> max(10/3) : i0
> = 2 and i1 = 2; A[i0, i1] -> max((6 - 11/9 * i0 + 1/9 * i0^2)) : i1 = 2 and
> 3 <= i0 <= 4; A[i0, i1] -> max(2) : i0 = 5 and i1 = 2; A[i0, i1] -> max(4)
> : i0 = 0 and 0 <= i1 <= 2 }
>
> It seems that the {max(23/3)} is from i0=1 and then A[1, 0 or 1] ->
> max((25/3 - 2/3)) = max(23/3). So I get floor(23/3) = 7. Did you get six by
> other methods?

If you split the domain along i0 mod 3, then it seems
the bounds are tight.

> Recently, I found that in some cases, isl_union_pw_qpolynomial_bound takes
> lots of time to solve. Is there a better method?

I don't know.

skimo

[Kelvin Yang]

Thank you very much. I understand what you meant.

Kelvin

Sven Verdoolaege 在 2023年3月21日 星期二凌晨3:56:38 [UTC+8] 的信中寫道：