text:
# Contents of /trunk/doc/user/finley.tex

Revision 1700 - (show annotations)
Thu Aug 14 03:35:46 2008 UTC (10 years, 5 months ago) by lgraham
File MIME type: application/x-tex
File size: 19577 byte(s)

 1 % 2 % $Id$ 3 % 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 5 % 6 % Copyright 2003-2007 by ACceSS MNRF 7 % Copyright 2007 by University of Queensland 8 % 9 10 % Primary Business: Queensland, Australia 11 % Licensed under the Open Software License version 3.0 12 13 % 14 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 15 % 16 17 \chapter{ The Module \finley} 18 \label{CHAPTER ON FINLEY} 19 20 \begin{figure} 21 \centerline{\includegraphics[width=\figwidth]{figures/FinleyMesh.eps}} 22 \caption{Subdivision of an Ellipse into triangles order 1 (\finleyelement{Tri3})} 23 \label{FINLEY FIG 0} 24 \end{figure} 25 26 \begin{figure} 27 \centerline{\includegraphics[width=\figwidth]{figures/FinleyContact.eps}} 28 \caption{Mesh around a contact region (\finleyelement{Rec4})} 29 \label{FINLEY FIG 01} 30 \end{figure} 31 32 \declaremodule{extension}{finley} \modulesynopsis{Solving linear, steady partial differential equations using 33 finite elements} 34 35 {\it finley} is a library of C functions solving linear, steady partial differential equations 36 \index{partial differential equations} (PDEs) or systems of PDEs using isoparametrical finite 37 elements \index{FEM!isoparametrical}. 38 It supports unstructured, 1D, 2D and 3D meshes. The module \finley provides an access to the 39 library through the \LinearPDE class of \escript supporting its full functionality. {\it finley} 40 is parallelized using the OpenMP \index{OpenMP} paradigm. 41 42 \section{Formulation} 43 44 For a single PDE with a solution with a single component the linear PDE is defined in the 45 following form: 46 \begin{equation}\label{FINLEY.SINGLE.1} 47 \begin{array}{cl} & 48 \displaystyle{ 49 \int\hackscore{\Omega} 50 A\hackscore{jl} \cdot v\hackscore{,j}u\hackscore{,l}+ B\hackscore{j} \cdot v\hackscore{,j} u+ C\hackscore{l} \cdot v u\hackscore{,l}+D \cdot vu \; d\Omega } \\ 51 + & \displaystyle{\int\hackscore{\Gamma} d \cdot vu \; d{\Gamma} } 52 + \displaystyle{\int\hackscore{\Gamma^{contact}} d^{contact} \cdot [v][u] \; d{\Gamma} } \\ 53 = & \displaystyle{\int\hackscore{\Omega} X\hackscore{j} \cdot v\hackscore{,j}+ Y \cdot v \; d\Omega }\\ 54 + & \displaystyle{\int\hackscore{\Gamma} y \cdot v \; d{\Gamma}} + 55 \displaystyle{\int\hackscore{\Gamma^{contact}} y^{contact}\cdot [v] \; d{\Gamma}} \\ 56 \end{array} 57 \end{equation} 58 59 \section{Meshes} 60 To understand the usage of \finley one needs to have an understanding of how the finite element meshes 61 \index{FEM!mesh} are defined. \fig{FINLEY FIG 0} shows an example of the 62 subdivision of an ellipse into so called elements \index{FEM!elements} \index{element}. 63 In this case, triangles have been used but other forms of subdivisions 64 can be constructed, e.g. into quadrilaterals or, in the three dimensional case, into tetrahedrons 65 and hexahedrons. The idea of the finite element method is to approximate the solution by a function 66 which is a polynomial of a certain order and is continuous across it boundary to neighbor elements. 67 In the example of \fig{FINLEY FIG 0} a linear polynomial is used on each triangle. As one can see, the triangulation 68 is quite a poor approximation of the ellipse. It can be improved by introducing a midpoint on each element edge then 69 positioning those nodes located on an edge expected to describe the boundary, onto the boundary. 70 In this case the triangle gets a curved edge which requires a parametrization of the triangle using a 71 quadratic polynomial. For this case, the solution is also approximated by a piecewise quadratic polynomial 72 (which explains the name isoparametrical elements), see \Ref{Zienc,NumHand} for more details. 73 74 The union of all elements defines the domain of the PDE. 75 Each element is defined by the nodes used to describe its shape. In \fig{FINLEY FIG 0} the element, 76 which has type \finleyelement{Tri3}, 77 with element reference number $19$ \index{element!reference number} is defined by the nodes 78 with reference numbers $9$, $11$ and $0$ \index{node!reference number}. Notice that the order is counterclockwise. 79 The coefficients of the PDE are evaluated at integration nodes with each individual element. 80 For quadrilateral elements a Gauss quadrature scheme is used. In the case of triangular elements a 81 modified form is applied. The boundary of the domain is also subdivided into elements. \index{element!face} In \fig{FINLEY FIG 0} 82 line elements with two nodes are used. The elements are also defined by their describing nodes, e.g. 83 the face element reference number $20$ which has type \finleyelement{Line2} is defined by the nodes 84 with the reference numbers $11$ and $0$. Again the order is crucial, if moving from the first 85 to second node the domain has to lie on the left hand side (in the case of a two dimension surface element 86 the domain has to lie on the left hand side when moving counterclockwise). If the gradient on the 87 surface of the domain is to be calculated rich face elements face to be used. Rich elements on a face 88 are identical to interior elements but with a modified order of nodes such that the 'first' face of the element aligns 89 with the surface of the domain. In \fig{FINLEY FIG 0} 90 elements of the type \finleyelement{Tri3Face} are used. 91 The face element reference number $20$ as a rich face element is defined by the nodes 92 with reference numbers $11$, $0$ and $9$. Notice that the face element $20$ is identical to the 93 interior element $19$ except that, in this case, the order of the node is different to align the first 94 edge of the triangle (which is the edge starting with the first node) with the boundary of the domain. 95 96 Be aware that face elements and elements in the interior of the domain must match, i.e. a face element must be the face 97 of an interior element or, in case of a rich face element, it must be identical to an interior element. 98 If no face elements are specified 99 \finley implicitly assumes homogeneous natural boundary conditions \index{natural boundary conditions!homogeneous}, 100 i.e. \var{d}=$0$ and \var{y}=$0$, on the entire boundary of the domain. For 101 inhomogeneous natural boundary conditions \index{natural boundary conditions!inhomogeneous}, 102 the boundary must be described by face elements. 103 104 If discontinuities of the PDE solution are considered contact elements 105 \index{element!contact}\index{contact conditions} are introduced to describe the contact region $\Gamma^{contact}$ 106 even if $d^{contact}$ and $y^{contact}$ are zero. \fig{FINLEY FIG 01} shows a simple example of a mesh 107 of rectangular elements around a contact region $\Gamma^{contact}$ \index{element!contact}. 108 The contact region is described by the 109 elements $4$, $3$ and $6$. Their element type is \finleyelement{Line2_Contact}. 110 The nodes $9$, $12$, $6$, $5$ define contact element $4$, where the coordinates of nodes $12$ and $5$ and 111 nodes $4$ and $6$ are identical with the idea that nodes $12$ and $9$ are located above and 112 nodes $5$ and $6$ below the contact region. 113 Again, the order of the nodes within an element is crucial. There is also the option of using rich elements 114 if the gradient is to be calculated on the contact region. Similarly to the rich face elements 115 these are constructed from two interior elements by reordering the nodes such that 116 the 'first' face of the element above and the 'first' face of the element below the 117 contact regions line up. The rich version of element 118 $4$ is of type \finleyelement{Rec4Face_Contact} and is defined by the nodes $9$, $12$, $16$, $18$, $6$, $5$, $0$ and 119 $2$. 120 121 \tab{FINLEY TAB 1} shows the interior element types and the corresponding element types to be used 122 on the face and contacts. \fig{FINLEY.FIG:1}, \fig{FINLEY.FIG:2} and \fig{FINLEY.FIG:4} show the ordering of 123 the nodes within an element. 124 125 \begin{table} 126 \begin{tablev}{l|llll}{textrm}{interior}{face}{rich face}{contact}{rich contact} 127 \linev{\finleyelement{Line2}}{\finleyelement{Point1}}{\finleyelement{Line2Face}}{\finleyelement{Point1_Contact}}{\finleyelement{Line2Face_Contact}} 128 \linev{\finleyelement{Line3}}{\finleyelement{Point1}}{\finleyelement{Line3Face}}{\finleyelement{Point1_Contact}}{\finleyelement{Line3Face_Contact}} 129 \linev{\finleyelement{Tri3}}{\finleyelement{Line2}}{\finleyelement{Tri3Face}}{\finleyelement{Line2_Contact}}{\finleyelement{Tri3Face_Contact}} 130 \linev{\finleyelement{Tri6}}{\finleyelement{Line3}}{\finleyelement{Tri6Face}}{\finleyelement{Line3_Contact}}{\finleyelement{Tri6Face_Contact}} 131 \linev{\finleyelement{Rec4}}{\finleyelement{Line2}}{\finleyelement{Rec4Face}}{\finleyelement{Line2_Contact}}{\finleyelement{Rec4Face_Contact}} 132 \linev{\finleyelement{Rec8}}{\finleyelement{Line3}}{\finleyelement{Rec8Face}}{\finleyelement{Line3_Contact}}{\finleyelement{Rec8Face_Contact}} 133 \linev{\finleyelement{Rec9}}{\finleyelement{Line3}}{\finleyelement{Rec9Face}}{\finleyelement{Line3_Contact}}{\finleyelement{Rec9Face_Contact}} 134 \linev{\finleyelement{Tet4}}{\finleyelement{Tri6}}{\finleyelement{Tet4Face}}{\finleyelement{Tri6_Contact}}{\finleyelement{Tet4Face_Contact}} 135 \linev{\finleyelement{Tet10}}{\finleyelement{Tri9}}{\finleyelement{Tet10Face}}{\finleyelement{Tri9_Contact}}{\finleyelement{Tet10Face_Contact}} 136 \linev{\finleyelement{Hex8}}{\finleyelement{Rec4}}{\finleyelement{Hex8Face}}{\finleyelement{Rec4_Contact}}{\finleyelement{Hex8Face_Contact}} 137 \linev{\finleyelement{Hex20}}{\finleyelement{Rec8}}{\finleyelement{Hex20Face}}{\finleyelement{Rec8_Contact}}{\finleyelement{Hex20Face_Contact}} 138 \end{tablev} 139 \caption{Finley elements and corresponding elements to be used on domain faces and contacts. 140 The rich types have to be used if the gradient of function is to be calculated on faces and contacts, respectively.} 141 \label{FINLEY TAB 1} 142 \end{table} 143 144 The native \finley file format is defined as follows. 145 Each node \var{i} has \var{dim} spatial coordinates \var{Node[i]}, a reference number 146 \var{Node_ref[i]}, a degree of freedom \var{Node_DOF[i]} and tag \var{Node_tag[i]}. 147 In most cases \var{Node_DOF[i]}=\var{Node_ref[i]} however, for periodic boundary conditions, 148 \var{Node_DOF[i]} is chosen differently, see example below. The tag can be used to mark nodes sharing 149 the same properties. Element \var{i} is defined by the \var{Element_numNodes} nodes \var{Element_Nodes[i]} 150 which is a list of node reference numbers. The order is crucial. 151 It has a reference number \var{Element_ref[i]} and a tag \var{Element_tag[i]}. The tag 152 can be used to mark elements sharing the same properties. For instance elements above 153 a contact region are marked with $2$ and elements below a contact region are marked with $1$. 154 \var{Element_Type} and \var{Element_Num} give the element type and the number of elements in the mesh. 155 Analogue notations are used for face and contact elements. The following Python script 156 prints the mesh definition in the \finley file format: 157 \begin{python} 158 print "%s\n"%mesh_name 159 # node coordinates: 160 print "%dD-nodes %d\n"%(dim,numNodes) 161 for i in range(numNodes): 162 print "%d %d %d"%(Node_ref[i],Node_DOF[i],Node_tag[i]) 163 for j in range(dim): print " %e"%Node[i][j] 164 print "\n" 165 # interior elements 166 print "%s %d\n"%(Element_Type,Element_Num) 167 for i in range(Element_Num): 168 print "%d %d"%(Element_ref[i],Element_tag[i]) 169 for j in range(Element_numNodes): print " %d"%Element_Nodes[i][j] 170 print "\n" 171 # face elements 172 print "%s %d\n"%(FaceElement_Type,FaceElement_Num) 173 for i in range(FaceElement_Num): 174 print "%d %d"%(FaceElement_ref[i],FaceElement_tag[i]) 175 for j in range(FaceElement_numNodes): print " %d"%FaceElement_Nodes[i][j] 176 print "\n" 177 # contact elements 178 print "%s %d\n"%(ContactElement_Type,ContactElement_Num) 179 for i in range(ContactElement_Num): 180 print "%d %d"%(ContactElement_ref[i],ContactElement_tag[i]) 181 for j in range(ContactElement_numNodes): print " %d"%ContactElement_Nodes[i][j] 182 print "\n" 183 # point sources (not supported yet) 184 write("Point1 0",face_element_type,numFaceElements) 185 \end{python} 186 187 The following example of a mesh file defines the mesh shown in \fig{FINLEY FIG 01}: 188 \begin{verbatim} 189 Example 1 190 2D Nodes 16 191 0 0 0 0. 0. 192 2 2 0 0.33 0. 193 3 3 0 0.66 0. 194 7 4 0 1. 0. 195 5 5 0 0. 0.5 196 6 6 0 0.33 0.5 197 8 8 0 0.66 0.5 198 10 10 0 1.0 0.5 199 12 12 0 0. 0.5 200 9 9 0 0.33 0.5 201 13 13 0 0.66 0.5 202 15 15 0 1.0 0.5 203 16 16 0 0. 1.0 204 18 18 0 0.33 1.0 205 19 19 0 0.66 1.0 206 20 20 0 1.0 1.0 207 Rec4 6 208 0 1 0 2 6 5 209 1 1 2 3 8 6 210 2 1 3 7 10 8 211 5 2 12 9 18 16 212 7 2 13 19 18 9 213 10 2 20 19 13 15 214 Line2 0 215 Line2_Contact 3 216 4 0 9 12 6 5 217 3 0 13 9 8 6 218 6 0 15 13 10 8 219 Point1 0 220 \end{verbatim} 221 Notice that the order in which the nodes and elements are given is arbitrary. 222 In the case that rich contact elements are used the contact element section gets 223 the form 224 \begin{verbatim} 225 Rec4Face_Contact 3 226 4 0 9 12 16 18 6 5 0 2 227 3 0 13 9 18 19 8 6 2 3 228 6 0 15 13 19 20 10 8 3 7 229 \end{verbatim} 230 Periodic boundary condition \index{boundary conditions!periodic} can be introduced by altering \var{Node_DOF}. 231 It allows identification of nodes even if they have different physical locations. For instance, to 232 enforce periodic boundary conditions at the face $x_0=0$ and $x_0=1$ one identifies 233 the degrees of freedom for nodes $0$, $5$, $12$ and $16$ with the degrees of freedom for 234 $7$, $10$, $15$ and $20$, respectively. The node section of the \finley mesh gets now the form: 235 \begin{verbatim} 236 2D Nodes 16 237 0 0 0 0. 0. 238 2 2 0 0.33 0. 239 3 3 0 0.66 0. 240 7 0 0 1. 0. 241 5 5 0 0. 0.5 242 6 6 0 0.33 0.5 243 8 8 0 0.66 0.5 244 10 5 0 1.0 0.5 245 12 12 0 0. 0.5 246 9 9 0 0.33 0.5 247 13 13 0 0.66 0.5 248 15 12 0 1.0 0.5 249 16 16 0 0. 1.0 250 18 18 0 0.33 1.0 251 19 19 0 0.66 1.0 252 20 16 0 1.0 1.0 253 \end{verbatim} 254 255 256 \include{finleyelements} 257 258 \subsection{Linear Solvers in \LinearPDE} 259 Currently \finley supports the linear solvers \PCG, \GMRES, \PRESTWENTY and \BiCGStab. 260 For \GMRES the options \var{truncation} and \var{restart} of the \method{getSolution} can be 261 used to control the truncation and restart during iteration. Default values are 262 \var{truncation}=5 and \var{restart}=20. 263 The default solver is \BiCGStab but if the symmetry flag is set \PCG is the default solver. 264 \finley supports the solver options \var{iter_max} which specifies the maximum number of iterations steps, 265 \var{verbose}=\True or \False and \var{preconditioner}=\constant{JACOBI} or \constant {ILU0}. 266 In some installations \finley supports the \Direct solver and the 267 solver options \var{reordering}=\constant{util.NO_REORDERING}, 268 \constant{util.MINIMUM_FILL_IN} or \constant{util.NESTED_DISSECTION} (default is \constant{util.NO_REORDERING}), 269 \var{drop_tolerance} specifying the threshold for values to be dropped in the 270 incomplete elimination process (default is 0.01) and \var{drop_storage} specifying the maximum increase 271 in storage allowed in the 272 incomplete elimination process (default is 1.20). 273 274 \subsection{Functions} 275 \begin{funcdesc}{Mesh}{fileName,integrationOrder=-1} 276 creates a \Domain object form the FEM mesh defined in 277 file \var{fileName}. The file must be given the \finley file format. 278 If \var{integrationOrder} is positive, a numerical integration scheme 279 chosen which is accurate on each element up to a polynomial of 280 degree \var{integrationOrder} \index{integration order}. Otherwise 281 an appropriate integration order is chosen independently. 282 \end{funcdesc} 283 284 \begin{funcdesc}{Rectangle}{n0,n1,order=1,l0=1.,l1=1., integrationOrder=-1, \\ 285 periodic0=\False,periodic1=\False,useElementsOnFace=\False,optimize=\False} 286 Generates a \Domain object representing a two dimensional rectangle between 287 $(0,0)$ and $(l0,l1)$ with orthogonal edges. The rectangle is filled with 288 \var{n0} elements along the $x_0$-axis and 289 \var{n1} elements along the $x_1$-axis. 290 For \var{order}=1 and \var{order}=2 291 \finleyelement{Rec4} and 292 \finleyelement{Rec8} are used, respectively. 293 In the case of \var{useElementsOnFace}=\False, 294 \finleyelement{Line2} and 295 \finleyelement{Line3} are used to subdivide the edges of the rectangle, respectively. 296 In the case of \var{useElementsOnFace}=\True (this option should be used if gradients 297 are calculated on domain faces), 298 \finleyelement{Rec4Face} and 299 \finleyelement{Rec8Face} are used on the edges, respectively. 300 If \var{integrationOrder} is positive, a numerical integration scheme 301 chosen which is accurate on each element up to a polynomial of 302 degree \var{integrationOrder} \index{integration order}. Otherwise 303 an appropriate integration order is chosen independently. If 304 \var{periodic0}=\True, periodic boundary conditions \index{periodic boundary conditions} 305 along the $x_0$-directions are enforced. That means when for any solution of a PDE solved by \finley 306 the value on the line $x_0=0$ will be identical to the values on $x_0=\var{l0}$. 307 Correspondingly, 308 \var{periodic1}=\False sets periodic boundary conditions 309 in $x_1$-direction. 310 If \var{optimize}=\True mesh node relabeling will be attempted to reduce the computation and also ParMETIS will be used to improve the mesh partition if running on multiple CPUs with MPI. 311 \end{funcdesc} 312 313 \begin{funcdesc}{Brick}{n0,n1,n2,order=1,l0=1.,l1=1.,l2=1., integrationOrder=-1, \\ 314 periodic0=\False,periodic1=\False,periodic2=\False,useElementsOnFace=\False,optimize=\False} 315 Generates a \Domain object representing a three dimensional brick between 316 $(0,0,0)$ and $(l0,l1,l2)$ with orthogonal faces. The brick is filled with 317 \var{n0} elements along the $x_0$-axis, 318 \var{n1} elements along the $x_1$-axis and 319 \var{n2} elements along the $x_2$-axis. 320 For \var{order}=1 and \var{order}=2 321 \finleyelement{Hex8} and 322 \finleyelement{Hex20} are used, respectively. 323 In the case of \var{useElementsOnFace}=\False, 324 \finleyelement{Rec4} and 325 \finleyelement{Rec8} are used to subdivide the faces of the brick, respectively. 326 In the case of \var{useElementsOnFace}=\True (this option should be used if gradients 327 are calculated on domain faces), 328 \finleyelement{Hex8Face} and 329 \finleyelement{Hex20Face} are used on the brick faces, respectively. 330 If \var{integrationOrder} is positive, a numerical integration scheme 331 chosen which is accurate on each element up to a polynomial of 332 degree \var{integrationOrder} \index{integration order}. Otherwise 333 an appropriate integration order is chosen independently. If 334 \var{periodic0}=\True, periodic boundary conditions \index{periodic boundary conditions} 335 along the $x_0$-directions are enforced. That means when for any solution of a PDE solved by \finley 336 the value on the plane $x_0=0$ will be identical to the values on $x_0=\var{l0}$. Correspondingly, 337 \var{periodic1}=\False and \var{periodic2}=\False sets periodic boundary conditions 338 in $x_1$-direction and $x_2$-direction, respectively. 339 If \var{optimize}=\True mesh node relabeling will be attempted to reduce the computation and also ParMETIS will be used to improve the mesh partition if running on multiple CPUs with MPI. 340 \end{funcdesc} 341 342 \begin{funcdesc}{GlueFaces}{meshList,safetyFactor=0.2,tolerance=1.e-13} 343 Generates a new \Domain object from the list \var{meshList} of \finley meshes. 344 Nodes in face elements whose difference of coordinates is less then \var{tolerance} times the 345 diameter of the domain are merged. The corresponding face elements are removed from the mesh. 346 347 TODO: explain \var{safetyFactor} and show an example. 348 \end{funcdesc} 349 350 \begin{funcdesc}{JoinFaces}{meshList,safetyFactor=0.2,tolerance=1.e-13} 351 Generates a new \Domain object from the list \var{meshList} of \finley meshes. 352 Face elements whose nodes coordinates have difference is less then \var{tolerance} times the 353 diameter of the domain are combined to form a contact element \index{element!contact} 354 The corresponding face elements are removed from the mesh. 355 356 TODO: explain \var{safetyFactor} and show an example. 357 \end{funcdesc}

## Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision


text:
Finding unique topological ordering wrt to another vertex ordering

Given a directed acyclic graph with $n$ nodes labeled from $1$ to $n$, what is an efficient way to produce the unique topological ordering with lower labeled nodes prioritized over higher labeled?

In other words: in the ordering the node labeled $1$ appears as early as possible, and if there are many such orders, among them choose the order(s) where the node labeled $2$ appears as early as possible, and so on producing the unique order in the end.

I tried to apply Kahn's algorithm. Instead of picking nodes arbitrary, choose ancestors of node $1$ from nodes with in-degree zero. Among those, choose ancestors of node 2, and so on. However, I don't know whether this idea can be efficiently implemented.

Choosing the lowest labeled node does not work: a counterexample is the DAG with the nodes 1, 2, 3 and 4, and edges 3 -> 1, 2 -> 4 and 4 -> 1. If we choose the lowest-numbered node, we get the ordering (2,3,1,4) but the ordering we look for is (3,1,2,4).

• What are the constraints on your running time? Does this algorithm have to run in $O(|V|+|E|)$? – Discrete lizard Apr 24 '18 at 17:49
• @Discretelizard Not necessarily in $O(|V|+|E|)$. A logarithmic factor is allowed for example but anything quadratic is too slow. – eLibrarian Apr 24 '18 at 18:11

format: plain


text:
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01dj52w719w
 Title: Optimal evasive strategies for groups of interacting agents with motion constraints Authors: Scott, William Lewis Advisors: Leonard, Naomi E Contributors: Mechanical and Aerospace Engineering Department Keywords: Differential gamesMinimum-time optimal controlMulti-agent systemsPursuit and evasion Subjects: Mechanical engineeringRobotics Issue Date: 2017 Publisher: Princeton, NJ : Princeton University Abstract: In this thesis we examine systems of pursuit and evasion with multiple evaders from several perspectives. Through the analysis of mathematical models and the study of field experiments we seek to understand how constraints on individual motion and sensing abilities affect outcomes on the level of the group and the individual. We present a nonlinear model of pursuit and evasion on the plane for a single pursuer and two evaders. Control laws are defined so that each evader trades off between evasion and herding. We analyze the system dynamics in terms of relative shape variables and derive conditions on the control parameters and initial conditions that determine whether capture occurs. We consider a system where evaders have heterogeneous limits on speed, turning rate, and lateral acceleration, versus a single pursuer with limited speed but no turning constraints. Optimal strategies are derived for the one-on-one differential game, and these form the basis of strategies for the multiple-evader system. Explicit analytic expressions for open-loop and state-feedback forms of optimal controls are derived in a related minimum-time problem for a single agent with the evader's motion constraints. For the multiple evader system, we propose a pursuer strategy of optimal target selection which leads to capture in bounded time and we prove how any evader not initially targeted can avoid capture with a "reactive evasion" strategy. We consider optimal strategies for agents with radius-limited sensing capabilities. In the case that evader turning rate is unbounded, we prove conditions for evader capture avoidance through a local strategy of "risk reduction," which we show leads to group aggregation. We present some preliminary results from a field experiment conducted at the Ol Pejeta Conservancy in Laikipia, Kenya in July 2014 to study evasive behaviors in herds of plains zebra under pursuit by an artificial predator, the robo-lion.'' Through manual tracking of video from an overhead camera we extract quantitative trajectory data for each zebra in the herd and for the robo-lion. The observed zebra behaviors of efficient evasion and group alignment serve to motivate our modeling efforts. URI: http://arks.princeton.edu/ark:/88435/dsp01dj52w719w Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Mechanical and Aerospace Engineering


text:
# How do you solve 144= -12(x+5)?

Mar 13, 2018

$x = - 17$

#### Explanation:

Divide both sides by $- 12$ and solve.
$144 = - 12 \left(x + 5\right)$
$- 12 = x + 5$
$- 17 = x$

$x = - 17$


text:
# Is every element in a set also an element of the powerset?

From my understanding of powersets, a powerset contains all the possible subsets of a set. So if we want the power set of {1} then the powerset of {1} is {{}, {1}}.

I was speaking to my tutor who was sure that if 1 is an element of the original set {1} (which is true) then that 1 is also an element of the power set {{}, {1}}. I was sure that it isn't an element, but the set containing that element is.

Can someone confirm or deny my suspicions?

• I think you are right and your tutor is wrong. – Tunococ Jun 21 '13 at 11:32
• The elements of $\{\{\},\{1\}\}$ are $\{\}$ and $\{1\}$. Apparently, $1$ is not among them. – azimut Jun 21 '13 at 12:08
• You need a new tutor. – PyRulez Jun 21 '13 at 15:04

However, there are sets $S$ and elements $e ∈ S$ for which $e$ is also in the powerset. Take $S = \{1,\{1\}\}$ and $e = \{1\}$. On the other side, in this example $e' = 1$ is not in the powerset of $S$, since $\mathcal{P}(S) = \{∅,\{1\},\{\{1\}\},S\}$, and none of the listed elements is $1$.
Another thing: There are sets $S$ with the property $S ⊂ \mathcal{P}(S)$, i.e. that every element of $S$ is indeed an element of the power set of $S$. Take for example $S = ∅$, $S = \{∅\}$ or $S = \{∅,\{∅\}\}$. I’m sure these sets have a name, but I don’t know it. Edit: As Andres mentioned in a comment, these sets are called transitive sets.
It is also common to define $0 := ∅$ and inductively any natural number $n+1$ as $n+1 := n ∪ \{n\}$, e.g. $1 = \{0\} = \{∅\}$ and $2 = \{0,1\} = \{∅,\{∅\}\}$ and so forth. Using this definition, it is certainly true that: $$0 ∈ 1 ∈ 2 ∈ 3 ∈ 4 ∈ …\quad \text{and} \quad 0 ⊂ 1 ⊂ 2 ⊂ 3 ⊂ 4 ⊂ …$$ such that “$∈$” essentially becomes “$<$”, whereas “$⊂$” becomes “$≤$”. So since any element of a so-defined natural number $n$ is also a subset of $n$, these natural numbers are indeed very prominent examples of sets whose elements are also members in their power sets, i.e. of transitive sets.
• The name you are looking for in the second paragraph is transitive. A set $A$ is called transitive if every element of $A$ is also a subset of $A$, that is, if whenever $y\in A$, then $y\subset A$, so $y\in\mathcal P(A)$. (The reason for the name "transitive" is perhaps explained by noticing that the condition is saying that whenever $x\in y\in A$, then $x\in A$.) – Andrés E. Caicedo Jun 21 '13 at 13:33


text:
# Doesn't matter what it means!

Algebra Level 3

Define $$/x/$$ as the $$\textbf{anti-modulus}$$ of $$x$$,behaving exactly opposite from that of $$\text{modulus}$$ of x.[for example, if we take $$x={5,-5}$$ then, l5l=l-5l=5, but $$/5/=/-5/=-5$$. Also, I0I=$$/0/$$=0].

Also define $$\text{Mil(y)={8 million+(3 million times y)}}$$.

What is the divisibility status of $$\text{Mil(sum of roots of the equation}$$ $$(/x/)^{2}-4x+3=0$$) by $$16?$$

×


text:
# zbMATH — the first resource for mathematics

## Chen, Xianghong

Compute Distance To:
 Author ID: chen.xianghong Published as: Chen, X.; Chen, Xianghong External Links: MGP · ORCID
 Documents Indexed: 17 Publications since 2009

#### Co-Authors

 2 single-authored 3 Fan, Dashan 1 Seeger, Andreas 1 Wang, Lifeng 1 Zhang, Juan
all top 5

#### Serials

 1 Canadian Journal of Mathematics 1 Mathematische Zeitschrift 1 Proceedings of the American Mathematical Society 1 Transactions of the American Mathematical Society 1 Revista Matemática Iberoamericana 1 The Journal of Fourier Analysis and Applications

#### Fields

 5 Harmonic analysis on Euclidean spaces (42-XX) 2 Abstract harmonic analysis (43-XX) 1 Special functions (33-XX) 1 Sequences, series, summability (40-XX)

#### Citations contained in zbMATH

8 Publications have been cited 24 times in 20 Documents Cited by Year
Convolution powers of salem measures with applications. Zbl 1375.42002
Chen, Xianghong; Seeger, Andreas
2017
A Fourier restriction theorem based on convolution powers. Zbl 1335.42004
Chen, Xianghong
2014
Sets of Salem type and sharpness of the $$L^2$$-Fourier restriction theorem. Zbl 1336.42003
Chen, Xianghong
2016
Sparse envelope model: efficient estimation and response variable selection in multivariate linear regression. Zbl 07072139
Su, Z.; Zhu, G.; Chen, X.; Yang, Y.
2016
Structure evolution at early stage of boundary-layer transition: simulation and experiment. Zbl 07193492
Jiang, X. Y.; Lee, C. B.; Chen, X.; Smith, C. R.; Linden, P. F.
2020
On almost everywhere divergence of Bochner-Riesz means on compact Lie groups. Zbl 1395.43004
Chen, Xianghong; Fan, Dashan
2018
Multistage scenario-based interval-stochastic programming for planning water resources allocation. Zbl 1418.90183
Li, Y. P.; Huang, G. H.; Chen, X.
2009
Restriction of the Fourier transform to some oscillating curves. Zbl 1412.42031
Chen, Xianghong; Fan, Dashan; Wang, Lifeng
2018
Structure evolution at early stage of boundary-layer transition: simulation and experiment. Zbl 07193492
Jiang, X. Y.; Lee, C. B.; Chen, X.; Smith, C. R.; Linden, P. F.
2020
On almost everywhere divergence of Bochner-Riesz means on compact Lie groups. Zbl 1395.43004
Chen, Xianghong; Fan, Dashan
2018
Restriction of the Fourier transform to some oscillating curves. Zbl 1412.42031
Chen, Xianghong; Fan, Dashan; Wang, Lifeng
2018
Convolution powers of salem measures with applications. Zbl 1375.42002
Chen, Xianghong; Seeger, Andreas
2017
Sets of Salem type and sharpness of the $$L^2$$-Fourier restriction theorem. Zbl 1336.42003
Chen, Xianghong
2016
Sparse envelope model: efficient estimation and response variable selection in multivariate linear regression. Zbl 07072139
Su, Z.; Zhu, G.; Chen, X.; Yang, Y.
2016
A Fourier restriction theorem based on convolution powers. Zbl 1335.42004
Chen, Xianghong
2014
Multistage scenario-based interval-stochastic programming for planning water resources allocation. Zbl 1418.90183
Li, Y. P.; Huang, G. H.; Chen, X.
2009
all top 5

#### Cited by 34 Authors

 4 Hambrook, Kyle 2 Chen, Changhao 2 Chen, Xianghong 2 Fan, Dashan 2 Łaba, Izabella 2 Lee, Chang-Boon 2 Linden, Paul F. 2 Shmerkin, Pablo S. 2 Smith, C. Ray 2 Su, Zhihua 2 Suomala, Ville 1 An, Baiguo 1 Chen, Jiecheng 1 Chen, Jiwei 1 Chen, Tuo 1 Ding, Shanshan 1 Dyatlov, Semyon 1 Fraser, Robert 1 Gu, Dingwei 1 Ham, Seheon 1 Huang, Guihua 1 Huang, Guo He 1 Jiang, Xiaoyue 1 Jiang, Xingyu 1 Jin, Long 1 Ko, Hyerim 1 Lee, Sanghyuk 1 Wang, Xiuquan 1 Yang, Yi 1 Zhang, Beibei 1 Zhang, Juan 1 Zhao, Fayou 1 Zhou, Yali 1 Zhu, Guangyu
all top 5

#### Cited in 18 Serials

 2 Journal of Fluid Mechanics 1 Communications in Mathematical Physics 1 Advances in Mathematics 1 The Annals of Statistics 1 Bulletin of the London Mathematical Society 1 Information Sciences 1 Memoirs of the American Mathematical Society 1 Transactions of the American Mathematical Society 1 Statistics & Probability Letters 1 Revista Matemática Iberoamericana 1 Geometric and Functional Analysis. GAFA 1 Proceedings of the Royal Society of Edinburgh. Section A. Mathematics 1 Finite Fields and their Applications 1 The Journal of Fourier Analysis and Applications 1 Annales Academiae Scientiarum Fennicae. Mathematica 1 Stochastic Environmental Research and Risk Assessment 1 Journal of the Australian Mathematical Society 1 Electronic Journal of Statistics
all top 5

#### Cited in 15 Fields

 10 Harmonic analysis on Euclidean spaces (42-XX) 7 Measure and integration (28-XX) 4 Abstract harmonic analysis (43-XX) 3 Statistics (62-XX) 2 Number theory (11-XX) 2 Probability theory and stochastic processes (60-XX) 2 Fluid mechanics (76-XX) 2 Operations research, mathematical programming (90-XX) 1 Combinatorics (05-XX) 1 Special functions (33-XX) 1 Partial differential equations (35-XX) 1 Sequences, series, summability (40-XX) 1 Convex and discrete geometry (52-XX) 1 Quantum theory (81-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX)


text:
# Simple C++ SDL2 Wrapper for small game

I'm in the process of creating a simple SDL2 wrapper for a breakout clone. The real learning objectives for this project are:

Learn how to manage resources properly via wrappers Learn more about SDL2 I'm building these wrapper as I step through Lazy Foo's tutorial and wanted to get some feedback on how I'm doing, and what other things I could be doing.

Here's my SDL_Surface wrapper so far:

// Surface.h
#pragma once
#include <iostream>
#include <SDL.h>
#include <string>
#include "Window.h"

namespace SDL2 {
class Surface
{
private:
SDL_Surface* ScreenSurface = nullptr;
bool IsWindowSurface = false;
std::string ImagePath = "";

public:
// This function creates a Surface object associated with a Window (gets cleaned when Window is destroyed)
Surface(SDL2::Window& window);
Surface(std::string path);
// Move constructor
Surface(Surface&& source);
// Disable copy constructor
Surface(const Surface& source) = delete;
~Surface();
// Disable copy by assignment
Surface& operator=(const Surface& source) = delete;
// Move assignment
Surface& operator=(Surface&& source);
void FillRect();
void Update(SDL2::Window& window);
// TODO: Add more parameters at future SDL2 tutorial
void BlitSurface(SDL2::Surface& destination);
};
}

// Surface.cpp
#include "Surface.h"

SDL2::Surface::Surface(SDL2::Window& window) :
ScreenSurface{ SDL_GetWindowSurface(window.GetSDLWindow()) },
IsWindowSurface{ true }
{
}

SDL2::Surface::Surface(std::string path) :
ImagePath{ path },
IsWindowSurface{ false }
{
}

SDL2::Surface::Surface(Surface && source) :
ScreenSurface{ source.ScreenSurface },
IsWindowSurface{ source.IsWindowSurface },
ImagePath{ source.ImagePath }
{
source.ScreenSurface = nullptr;
source.IsWindowSurface = false;
source.ImagePath = "";
}

SDL2::Surface::~Surface()
{
// If surface is not associated with Window, need free the surface with SDL2 call
if (!IsWindowSurface) {
SDL_FreeSurface(ScreenSurface);
}
}

SDL2::Surface & SDL2::Surface::operator=(Surface && source)
{
if (&source == this)
return *this;

// If surface is not associated with Window, need free the surface with SDL2 call
if (!IsWindowSurface) {
SDL_FreeSurface(ScreenSurface);
}

ScreenSurface = source.ScreenSurface;
IsWindowSurface = source.ScreenSurface;
ImagePath = source.ImagePath;

// Return source to stable state
source.ScreenSurface = nullptr;
source.IsWindowSurface = false;
source.ImagePath = "";

return *this;

}

// TODO: Define SDL_Rect parameter and Color parameter (make wrappers for these)
void SDL2::Surface::FillRect()
{
SDL_FillRect(ScreenSurface, NULL, SDL_MapRGB(ScreenSurface->format, 0x00, 0x00, 0xFF));
}

void SDL2::Surface::Update(SDL2::Window& window)
{
SDL_UpdateWindowSurface(window.GetSDLWindow());
}

// This function is called after a non-window surface is created.  Check on this return value for success/fail.
{
// Load image from path

if (!ScreenSurface) {
std::cout << "Unable to load image " << ImagePath << " SDL Error: " << SDL_GetError() << '\n';
return false;
}
return true;
}

// The source Surface is this.  This function applies the image to the destination surface (though not updated on the screen)
void SDL2::Surface::BlitSurface(SDL2::Surface & destination)
{
// Args: Source, FUTURE, Destination, FUTURE
SDL_BlitSurface(this->ScreenSurface, NULL, destination.ScreenSurface, NULL);
}

Any pointers would be much appreciated!

• Which tutorial are you referring to? – Mast Aug 20 '18 at 5:30
• Right now just Lessons 1 and 2 here: lazyfoo.net/tutorials/SDL – Joe Aug 20 '18 at 5:54

Wrapping SDL_Surface like this to get automatic cleanup in the destructor is a good idea. However, the current implementation makes a few assumptions that aren't necessarily correct.

## Surface Creation

There are lots of ways to get hold of a surface. Getting it from a Window, loading from a file, manually creating it with SDL_CreateSurface, or using something like SDL_TTF to render a font.

The Surface class shouldn't care about how the surface is created. It only needs to accept a surface, and know whether that surface should be cleaned up on destruction, e.g.:

Surface(SDL_Surface* surface, bool freeOnDestruction);

should replace the current Window and string constructors. The LoadBMP function could be made a free function that takes a string and returns a Surface.

## Window

The dependency of Surface on Window seems backwards. Since an SDL_Window owns an SDL_Surface of its own, it would make more sense for the dependency to be the other way around. Thus the Window class could have a GetSurface() function, returning a Surface, and the Update() function would make more sense as UpdateSurface() in the Window class (it doesn't make sense for non-window surfaces anyway).

## Interface and Error Checking

BlitSurface is confusing because you have to remember whether to call source.BlitSurface or dest.BlitSurface. As member functions it might be better to have both a BlitFrom(source) and BlitTo(dest), that both call a single Blit function.

It might be better to use free functions instead:

void FillSurface(Surface& surface, Color const& color); // fill entire surface!
void FillSurface(Surface& surface, Rect const& rect, Color const& color); // fill a rect on the surface
void BlitSurface(Surface& source, Surface const& dest); // blit whole surfaces
// TODO: rect versions...

SDL_BlitSurface has some conditions you should check before and after (it doesn't work on locked / null surfaces, it returns an error code on failure). These should be handled and output a message / throw an error / terminate the program.

It would make sense to have a GetSDLSurface() function in the Surface class (similar to the GetSDLWindow() function). We can check (assert / throw / print message) that the surface pointer is non-null in this function before returning it. If the Blit and Fill functions are free functions, and not members, they can't access the private member directly and must use this function. This means they will automatically do the non-null error check when using the surface.

## Using the Standard Library

The C++ Standard Library already contains a class to manage an object's lifetime like this: std::unique_ptr.

Instead of checking whether we have to free the surface in copy / move constructors, we can wrap it in a unique_ptr with a custom deleter. We can then use the default move constructor and move operators:

#include <iostream>
#include <functional>
#include <memory>
#include <cassert>

// placeholder for testing...
struct SDL_Surface
{
SDL_Surface() { std::cout << "constructor" << std::endl; }
~SDL_Surface() { std::cout << "destructor" << std::endl; }
};

// placeholder for testing...
void SDL_FreeSurface(SDL_Surface* surface)
{
delete surface;
}

class Surface
{
public:

Surface(SDL_Surface* sdlSurface, bool freeOnDestruction);

Surface(Surface&&) = default;
Surface& operator=(Surface&&) = default;

Surface(Surface const&) = delete;
Surface& operator=(Surface const&) = delete;

SDL_Surface* GetSDLSurface() const; // Blit / Fill etc. should use this to get the SDL_Surface.

private:

using SDLSurfacePtrDeleterT = std::function<void(SDL_Surface*)>;
using SDLSurfacePtrT = std::unique_ptr<SDL_Surface, SDLSurfacePtrDeleterT>;
SDLSurfacePtrT m_sdlSurfacePtr;
};

Surface::Surface(SDL_Surface* sdlSurface, bool freeOnDestruction)
{
assert(sdlSurface != nullptr); // no null surfaces!
// (means we don't have to check the inner pointer every time we e.g. blit).

auto deleter = freeOnDestruction ?
SDLSurfacePtrDeleterT([] (SDL_Surface* surface) { SDL_FreeSurface(surface); }) :
SDLSurfacePtrDeleterT([] (SDL_Surface*) { });

m_sdlSurfacePtr = SDLSurfacePtrT(sdlSurface, deleter);
}

SDL_Surface* Surface::GetSDLSurface() const
{
assert(m_sdlSurfacePtr != nullptr); // check this surface hasn't been moved from
// (if the m_sdlSurfacePtr is valid, the inner surface should be valid (or at least non-null) due to the assert in the constructor).

return m_sdlSurfacePtr.get();
}

int main()
{
std::cout << "Construct + Destruct:" << std::endl;

{
auto sdlSurface = new SDL_Surface();
auto surface = Surface(sdlSurface, true);
// should get destructor call...
}

std::cout << "Construct + Leak:" << std::endl;

{
auto sdlSurface = new SDL_Surface();
auto surface = Surface(sdlSurface, false);
// will not get destructor call...
}

std::cout << "Construct + Move + Destruct:" << std::endl;

{
auto sdlSurface = new SDL_Surface();
auto surface = Surface(sdlSurface, true);
auto surface2 = std::move(surface);
// should get destructor call...
}
}

• Thanks for such a thorough response! When you say "The LoadBMP function could be made a free function that takes a string and returns a Surface", what do you mean by a "free function"?? – Joe Aug 20 '18 at 18:39
• By "free function" I just mean a non-member function (i.e. not part of the Surface class). So Surface LoadBMP(std::string const& path);. – user673679 Aug 20 '18 at 19:12
#pragma once

Be aware that you are giving up portability here as this is, while common, a non-standard compiler extension. For nearly all applications, as long as you use implementations that support it, neither physically nor logically copy files around, and the filesystem doesn't trigger a false-positive, then #pragma once is fine. Otherwise, stick with standard include guards and give some effort to differentiate the guard name.

#include <iostream>
#include <SDL.h>
#include <string>
#include "Window.h"

Headers should not be dependent upon other headers being included first. One way to ensure this is to include your headers before any other headers.

Latent usage errors can be avoided by ensuring that the .h file of a component parses by itself – without externally-provided declarations or definitions... Including the .h file as the very first line of the .c file ensures that no critical piece of information intrinsic to the physical interface of the component is missing from the .h file (or, if there is, that you will find out about it as soon as you try to compile the .c file).

That is to say, your includes should be in the following order:

1. Prototype/Interface. (surface.h)
2. Project/Private headers (window.h)
3. Headers from non-standard, non-system libraries (QT, Eigen, etc...)
4. Standard C++ headers (vector, string, cstdint, etc...)
5. System headers (windows.h, dirent.h, etc...)

As you move down the list, libraries are more stable and more widely used (and therefore tested). Further ordering each subgroup, say lexicographically by path/name, makes it easier for maintainers to quickly find an include when the include list becomes long.

Do not #include <iostream> in header files. Many C++ implementations transparently inject a static constructor into every translation unit that includes <iostream>, even if the client never uses the <iostream> facilities.

        bool IsWindowSurface = false;
std::string ImagePath = "";

Whenever you have a boolean tied to the existence of some other value, use an optional type (Boost, Mnmlstc, Folly, C++17).

Does your surface really need to know where it was created from?

        Surface(std::string path);

Copying a std::string may be expensive. Pass this input parameter by reference to const.

SDL2::Surface::Surface(std::string path) :
ImagePath{ path },
IsWindowSurface{ false } {}

If you want to treat the parameter as a sink argument, then std::move(path) into ImagePath.

bool SDL2::Surface::LoadBMP() {
// Load image from path

What happens here if the surface already exists? If the surface was a window surface copy, then you leak the old surface and the ScreenSurface will point to null because ImagePath is empty. If the source was a previous BMP, then the old surface still leaks and ScreenSurface points to clean version of the BMP.

Rather than wrapping every function into RAII objects, use std::unique_ptr to manage the lifetimes object types. As long as you don't construct your std::unique_ptr with an instance of a destructor that can't be optimized away, then std::unique_ptr is practically free.

With all of your resources, you've likely noticed a pattern where you create the resource and check the handle to ensure it was created. We can create a generic helper for creating these resource types.

template<typename Result, typename Creator, typename... Arguments>
auto make_resource(Creator c, Arguments&&... args)
{
auto r = c(std::forward<Arguments>(args)...);
if (!r) { throw std::system_error(errno, std::generic_category()); }
return Result(r);
}

Now we need a way to hand std::unique_ptr a deleter without incurring a cost. We can wrap it in a constant value and return a deleter function whenever std::unique_ptr requests it.

template <typename T, std::decay_t<T> t>
struct constant_t {
constexpr operator T() noexcept const { return t; }
}

Using the two above helpers, we can churn out resources. First we define the pointer type.

using surface_ptr = std::unique_ptr<
SDL_Surface, constant_t<decltype(SDL_FreeSurface), SDL_FreeSurface>>;

Then the factory functions.

inline auto make_surface(const char* filename) {
}

inline auto make_surface(SDL_Window* ptr) {
return make_resource<surface_ptr>(SDL_GetWindowSurface, ptr);
}

inline auto make_surface(
std::uint32_t flags, int width, int height, int depth,
return make_resource<surface_ptr>(
SDL_CreateRGBSurface, flags, width, height, depth,
}

Then you can use this surface_ptr with the existing SDL library.

void meow() {
auto w = make_window("Purr", SDL_WINDOW_POS_UNDEFINED, SDL_WINDOW_POS_UNDEFINED,
640, 480, 0));
auto s = make_surface(w.get());
SDL_FillRect(s.get(), NULL, SDL_MapRGB(s->format, 255, 0, 0));
SDL_UpdateWindowSurface(w.get());
}

Note - The constant_t helper above was needed for C++11 as there was a defect with std::integral_constant not being evaluated as a constexpr expression. With C++14, you can do the following

template <typename T, std::decay_t<T> t>
using constant_t = std::integral_t<T, t>;

using surface_ptr = std::unique_ptr<SDL_Surface, constant_t<decltype(SDL_FreeSurface)*, SDL_FreeSurface>>;

With C++17 allowing non-type template arguments with auto, the verbosity can be eliminated.

template <auto t>
using constant_t = std::integral_constant<std::decay_t<decltype(t)>, t>;

using surface_ptr = std::unique_ptr<SDL_Surface, constant_t<SDL_FreeSurface>>;