Symbolic Solvers over Regions

Adam Strzebonski

Wolfram Research, Inc.

Symbolic computation over regions

Equation and inequality solving

• Reduce
• Solve
• FindInstance
• Resolve

Optimization

• Minimize
• Maximize
• MinValue
• MaxValue
• ArgMin
• ArgMax

Integrate

Assumptions

Equation and inequality solving

Solve equations and inequalities in a 4D ball.

Reduce[(x^2)==y z&&(y^2)==z t&&(z^2)==t x&&{x,y,z,t}∈Ball[{0,0,0,0},1],{x,y,z,t}]

Equation and inequality solving

Find integer points in a cone.

R=Cone[{{1,2,3},{4,5,6}},3];
pts=Solve[{x,y,z}∈R,{x,y,z},Integers]

Graphics3D[{{Green,Opacity[0.5],R},{Red,Point[{x,y,z}/.pts]}}]

Equation and inequality solving

Find a point in the intersection of regions.

(Subscript[R, 1])=Cylinder[{{0,0,0},{1,2,3}},4];
(Subscript[R, 2])=Cone[{{3,3,3},{2,2,2}},3];
(Subscript[R, 3])=Line[{{3,4,5},{-3,-5,-7}}];
Graphics3D[{{Green,Opacity[0.5],(Subscript[R, 1])},{Blue,Opacity[0.5],(Subscript[R, 2])},{Red,(Subscript[R, 3])}}]

FindInstance[{x,y,z}∈RegionIntersection[(Subscript[R, 1]),(Subscript[R, 2]),(Subscript[R, 3])],{x,y,z}]

Equation and inequality solving

Compute a projection of the union of regions.

(Subscript[R, 1])=Cylinder[{{0,0,0},{1,2,3}},4];
(Subscript[R, 2])=Cone[{{3,3,3},{2,2,2}},3];
(Subscript[R, 3])=Line[{{3,4,5},{-3,-5,-7}}];
form=Resolve[(Subscript[∃, z]){x,y,z}∈RegionUnion[(Subscript[R, 1]),(Subscript[R, 2]),(Subscript[R, 3])]]

Region`SemialgebraicRegionPlot[ImplicitRegion[form,{x,y}],{{-7,7},{-7,7}}]

Equation and inequality solving

Find a circle passing through three points.

pts={{0,0},{1,2},{3,4}};
sol=Solve[pts∈Circle[{a,b},r],{a,b,r}]

Graphics[{Circle[{a,b},r]/.sol,{Red,PointSize[Large],Point[pts]}}]

Equation and inequality solving

Solving equations and inequalities over a region requires finding an implicit description of the region. For ParametricRegion and TransformedRegion this requires quantifier elimination.

R=ParametricRegion[{{(u^2),u v,(v^2)},(u^2)+(v^2)≤1},{u,v}];
(Subscript[red, 1])=Reduce[(x^2)+(y^2)+(z^2)==(1/4)&&{x,y,z}∈R,{x,y,z}]

This is equivalent to the following quantifier elimination problem.

(Subscript[red, 2])=Reduce[(x^2)+(y^2)+(z^2)==(1/4)&&(Subscript[∃, {u,v},(u^2)+(v^2)≤1])(x==(u^2)&&y==u v&&z==(v^2)),{x,y,z},Reals]

Resolve[(Subscript[∀, {x,y,z}])((Subscript[red, 1])⧦(Subscript[red, 2])),Reals]

Optimization

Maximize a function over a 4D ball.

Maximize[{x y z t,{x,y,z,t}∈Ball[{0,0,0,0},1]},{x,y,z,t}]

Optimization

Find a minimum radius disk containing the given 4 points.

SeedRandom[42];
pts=RandomInteger[{-10,10},{4,2}];
{min,pt}=Minimize[{r,pts∈Disk[{a,b},r]},{r,a,b}]

Graphics[{{Green,Disk[{a,b},r]/.pt},{Red,PointSize[Large],Point[pts]}}]

Optimization

When constraints involve a single ParametricRegion or TransformedRegion quantifier elimination is not required.

R=ParametricRegion[{{Cos[t],Sin[3 t]},0≤t<2 π},{t}];
MaxValue[{(x^2)+(y^2),{x,y}∈R},{x,y}]//Timing

Region`SemialgebraicRegionPlot[R,{{-2,2},{-2,2}}]

Implicit representation of R was not computed. Solving the problem for the second time isn’t faster.

MaxValue[{(x^2)+(y^2),{x,y}∈R},{x,y}]//Timing

If two parametric regions are involved quantifier elimination is necessary.

S=ParametricRegion[{{Cos[t],Sin[2 t]},0≤t<2 π},{t}];
MaxValue[{(x^2)+(y^2),{x,y}∈RegionIntersection[R,S]},{x,y}]//Timing

Implicit representation of R⋂S was computed and cached. Solving the problem for the second time is much faster.

MaxValue[{(x^2)+(y^2),{x,y}∈RegionIntersection[R,S]},{x,y}]//Timing

Integration

Integrate a function over a 5D ellipsoid.

Integrate[(x^2)+(y^2)+(z^2)+(t^2)+(u^2),{x,y,z,t,u}∈Ellipsoid[{0,0,0,0,0},{1,2,3,4,5}]]

Integration

Integration over a region of dimension d is performed wrt. the d-dimensional Lebesgue measure.

Integrate[1,{x,y}∈Circle[]]

R=Simplex[IdentityMatrix[5]];
Integrate[x+y+z+u+v,{x,y,z,u,v}∈R]

Integration

Integrate over an implicit region.

R=ImplicitRegion[(x^4)+(y^4)+(z^4)≤1,{x,y,z}];
Integrate[x y-(z^2),{x,y,z}∈R]

Integration

Integrate over a parametric region. We may avoid quantifier elimination if we can show that the parametrization is one-to-one.

R=ParametricRegion[{{2 u+(u^3)+v,u+(u^3)+v},(u^2)+(v^2)≤1},{u,v}];
Integrate[(x^2)+(y^2),{x,y}∈R]

Region`SemialgebraicRegionPlot[R,{{-4,4},{-4,4}}]