IntegerPointDecomposition - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


PolyhedralSets[ZPolyhedralSets]

  

IntegerPointDecomposition

  

decompose the integer points in a (parametric) ZPolyhedralSet

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

Calling Sequence

IntegerPointDecomposition(zpoly,output=value)

Parameters

zpoly

-

ZPolyhedralSet

value

-

(optional) either latticeformat (default) or omegatestformat

Description

• 

IntegerPointDecomposition(zpoly) decomposes zpoly into pairwise disjoint Z-Polyhedral sets with additional algebraic properties that an arbitrary Z-polyhedron is unlikely to have. Those algebraic properties are specified in Definition 2 of the first reference listed below. They imply that such a Z-polyhedron, say zp, is consistent (that is, has at least one point) and is specializable. This latter property means that if x is the variable of lowest rank in zp and v is a possible value for x (that is, there exists at least one point of zp with v as x-coordinate) then all the points of zp with v as x-coordinate are given by specializing at x=v the system of linear inequalities defining zp.

• 

The output option selects the return format. It can be given as:

– 

output=latticeformat (the default). With this option, the Z-polyhedral sets constructed can use arbitrary lattices.

– 

output=omegatestformat. With this option, Maple replaces the use of a lattice in each Z-polyhedron by using auxiliary variables, as in the Omega Test method of William Pugh; see the fourth reference below.

• 

The algorithm behind IntegerPointDecomposition is described in the first two papers listed below and is inspired by the other three references.

• 

Advanced problems can be found in the help page of ZPolyhedralSets. Those problems are taken from the literature (the fifth reference below) and illustrate the kind of applications that the command IntegerPointDecomposition can support. More elementary examples are shown below as well as in the help page of ZPolyhedralSet.

Examples

withPolyhedralSets:

withZPolyhedralSets:

ineqs016+2y+z,072+4x+4y+3z,02yz,024+4x+4y3z,04x+4y+3z,0484x+4y3z,0484x4y+3z,082y+z,024+4x4y+3z,0242yz,024+4x4y3z,0964x4y3z

ineqs016+2y+z,072+4x+4y+3z,02yz,024+4x+4y3z,04x+4y+3z,0484x+4y3z,0484x4y+3z,082y+z,024+4x4y+3z,0242yz,024+4x4y3z,0964x4y3z

(1)

LLatticeMatrix1,0,2,0,1,1,0,0,2,Vector0,0,1

LLattice1020−11002,001

(2)

varsx,y,z

varsx,y,z

(3)

zpsZPolyhedralSetineqs,vars,':-lattice'=L

zpsRelations:02yz016+2y+z082y+z0242yz04x+4y+3z072+4x+4y+3z024+4x4y+3z024+4x+4y3z024+4x4y3z0484x4y+3z0484x+4y3z0964x4y3zVariables:x,y,zParameters:ParameterConstraints:Lattice:ZSpan1020−11002,,,001

(4)

resIntegerPointDecompositionzps

resRelations:z9z−72yz−162y+z02yz82y+z244x4y3z−724x4y+3z−244x+4y3z−244x+4y+3z244x4y3z04x4y+3z484x+4y3z484x+4y+3z96Variables:x,y,zParameters:ParameterConstraints:Lattice:ZSpan100010002,,,001,Relations:x=9y=6z=11Variables:x,y,zParameters:ParameterConstraints:Lattice:ZSpan001002,,,901,Relations:x=9y=6z=5Variables:x,y,zParameters:ParameterConstraints:Lattice:ZSpan001002,,,901

(5)

You can also choose output format as omegatestformat instead.

ttIntegerPointDecompositionres1,output=omegatestformat

ttz=2_Z3+1,2_Z38,2_Z3−6,2y2_Z3−15,2y+2_Z3−1,2y2_Z39,2y+2_Z323,4x4y6_Z3−69,4x4y+6_Z3−27,4x+4y6_Z3−21,4x+4y+6_Z321,4x4y6_Z33,4x4y+6_Z345,4x+4y6_Z351,4x+4y+6_Z393,z,_Z3,x,y

(6)

res_omegatestformatIntegerPointDecompositionzps,output=omegatestformat

res_omegatestformatz=2_Z3+1,2_Z38,2_Z3−6,2y2_Z3−15,2y+2_Z3−1,2y2_Z39,2y+2_Z323,4x4y6_Z3−69,4x4y+6_Z3−27,4x+4y6_Z3−21,4x+4y+6_Z321,4x4y6_Z33,4x4y+6_Z345,4x+4y6_Z351,4x+4y+6_Z393,z,_Z3,x,y,y=6,x=9,z=5,y,x,z,,y=6,x=9,z=11,y,x,z,

(7)

References

  

Rui-Juan Jing and Marc Moreno Maza. "Computing the Integer Points of a Polyhedron, I: Algorithm." Proceedings of CASC 2017: 225-241, Springer.

  

Rui-Juan Jing and Marc Moreno Maza. "Computing the Integer Points of a Polyhedron, II: Complexity Estimates." Proceedings of CASC 2017: 242-256, Springer.

  

Rachid Seghir, Vincent Loechner, and Benoı̂t Meister. "Integer affine transformations of parametric Z-polytopes and applications to loop nest optimization." Proceedings of TACO, Vol. 9(2):8:1–8:27, 2012.

  

William Pugh. "The omega test: a fast and practical integer programming algorithm for dependence analysis." Proceedings Supercomputing ’91, pp 4–13. ACM, 1991.

  

William Pugh. "Counting solutions to presburger formulas: How and why." Proceedings of PLDI, pp 121–134. ACM, 1994.

Compatibility

• 

The PolyhedralSets:-ZPolyhedralSets:-IntegerPointDecomposition command was introduced in Maple 2023.

• 

For more information on Maple 2023 changes, see Updates in Maple 2023.

See Also

ZPolyhedralSets:-IsEmpty

ZPolyhedralSets:-IsIntegerPointOf

ZPolyhedralSets:-SamplePoint

ZPolyhedralSets:-EnumerateIntegerPoints

ZPolyhedralSets:-IsContained

ZPolyhedralSets:-ZPolyhedralSet

ZPolyhedralSets

PolyhedralSets