doc/implementation.tex

   1 \section{Implementation details}
   2
   3 \subsection{The integer points in the fundamental parallelepiped of a simple cone}
   4
   5 This section is based on \shortciteN[Lemma 5.1]{Barvinok1992volume} and
   6 \shortciteN{Koeppe2006experiments}.
   7
   8 \sindex{simple}{cone}
   9 \sindex{open}{facet}
  10 \sindex{open}{ray}
  11 \sindex{explicit}{representation}
  12 In this section we will deal exclusively with \ai{simple cone}s,
  13 i.e. $d$-dimensional cones with $d$ extremal rays and $d$ facets.
  14 \index{open facet}%
  15 Some of the facets of these cones may be open.
  16 Since we will mostly be dealing with cones in their
  17 \ai{explicit representation}, we will have occasion to speak of
  18 ``\ai{open ray}s'', by which we will mean that the facet not
  19 containing the ray is open.  (There is only one such facet because the cone
  20 is simple.)
  21
  22 \sindex{fundamental}{parallelepiped}
  23 \begin{definition}[Fundamental parallelepiped]
  24 Let $K = \vec v + \poshull \lb\, \vec u_i \,\rb$ be
  25 a closed (shifted) cone, then the \defindex{fundamental parallelepiped} $\Pi$
  26 of $K$ is
  27 $$
  28 \Pi = \vec v +
  29 \lb\, \sum_i \alpha_i \vec u_i \mid 0 \leq \alpha_i < 1 \,\rb
  30 .
  31 $$
  32 If some of the rays $\vec u_i$ of $K$ are open, then the constraints on
  33 the corresponding coefficient $\alpha_i$ are such that $0 < \alpha_i \le 1$.
  34 \end{definition}
  35
  36 \begin{lemma}[Integer points in the fundamental parallelepiped of a simple cone]
  37 Let $K = \vec v + \poshull \lb\, \vec u_i \,\rb$ be a closed simple cone
  38 and let $A$ be the matrix with the generators $\vec u_i$ of $K$
  39 as rows.
  40 Furthermore let $V A W^{-1} = S = \diag \vec s$ be the \indac{SNF} of $A$.
  41 Then the integer points in the fundamental parallelepiped of $K$ are given
  42 by
  43 \begin{eqnarray}
  44 \label{eq:parallelepiped}
  45 \vec w^\T & = & \vec v^\T + \fractional{(\vec k^\T W - \vec v^\T) A^{-1}} A
  46 \\
  47 \nonumber
  48 & = &
  49 \vec v^T +
  50 \sum_{i=1}^d
  51     \fractional{\sps{\sum_{j=1}^d k_j \vec w^T_j - \vec v^\T}{\vec u^*_i}} \vec u_i,
  52 \end{eqnarray}
  53 where $\vec u^*_i$ are the columns of $A^{-1}$ and $k_j \in \ZZ$ ranges
  54 over $0 \le k_j < s_j$.
  55 \end{lemma}
  56
  57 \begin{proof}
  58 Since $0 \le \fractional{x} < 1$, it is clear that each such $\vec w$
  59 lies inside the fundamental parallelepiped.
  60 Furthermore,
  61 \begin{eqnarray*}
  62 \vec w^\T & = & \vec v^\T + \fractional{(\vec k^\T W - \vec v^\T) A^{-1}} A
  63 \\
  64 & = &
  65 \vec v^T +
  66 \left(
  67 (\vec k^\T W - \vec v^\T) A^{-1} - \floor{(\vec k^\T W - \vec v^\T) A^{-1}}
  68 \right) A
  69 \\
  70 & = &
  71 \underbrace{\vec k^\T W\mathstrut}_{\in \ZZ^{1\times d}}
  72 +
  73 \underbrace{\floor{(\vec k^\T W - \vec v^\T) A^{-1}}}_{\in \ZZ^{1\times d}}
  74 \underbrace{A\mathstrut}_{\in \ZZ^{d\times d}} \in \ZZ^{1\times d}.
  75 \end{eqnarray*}
  76 Finally, if two such $\vec w$ are equal, i.e., $\vec w_1 = \vec w_2$,
  77 then
  78 \begin{eqnarray*}
  79 \vec 0^\T = \vec w_1^\T - \vec w_2^\T
  80 & = & \vec k_1^\T W - \vec k_2^\T W + \vec p^\T A
  81 \\
  82 & = & \left(\vec k_1^\T - \vec k_2^\T \right) W + \vec p^\T V^{-1} S W,
  83 \end{eqnarray*}
  84 with $\vec p \in \ZZ^d$,
  85 or $\vec k_1 \equiv \vec k_2 \mod \vec s$, i.e., $\vec k_1 = \vec k_2$.
  86 Since $\det S = \det A$, we obtain all points in the fundamental parallelepiped
  87 by taking all $\vec k \in \ZZ^d$ satisfying $0 \le k_j < s_j$.
  88 \end{proof}
  89
  90 If the cone $K$ is not closed then the coefficients of the open rays
  91 should be in $(0,1]$ rather than in $[0,1)$.
  92 In (\ref{eq:parallelepiped}),
  93 we therefore need to replace the fractional part $\fractional{x} = x - \floor{x}$
  94 by $\cractional{x} = x - \ceil{x-1}$ for the open rays.
  95
  96 \begin{figure}
  97 \intercol=1.2cm
  98 \begin{xy}
  99 <\intercol,0pt>:<0pt,\intercol>::
 100 \POS@i@={(0,-3),(0,0),(4,2),(4,-3)},{0*[grey]\xypolyline{*}}
 101 \POS@i@={(0,-3),(0,0),(4,2)},{0*[|(2)]\xypolyline{}}
 102 \POS(-1,0)\ar(4.5,0)
 103 \POS(0,-3)\ar(0,3)
 104 \POS(0,0)\ar@[|(3)](0,-1)
 105 \POS(0,0)\ar@[|(3)](2,1)
 106 \POS(0,-1)\ar@{--}@[|(2)](2,0)
 107 \POS(2,1)\ar@{--}@[|(2)](2,0)
 108 \POS(0,0)*{\bullet}
 109 \POS(1,0)*{\bullet}
 110 \end{xy}
 111 \caption{The integer points in the fundamental parallelepiped of $K$}
 112 \label{f:parallelepiped}
 113 \end{figure}
 114
 115 \begin{example}
 116 Let $K$ be the cone
 117 $$
 118 K = \sm{0 \\ 0} + \poshull \lb\, \sm{2 \\ 1}, \sm{0 \\ -1} \,\rb
 119 ,
 120 $$
 121 shown in Figure~\ref{f:parallelepiped}.
 122 Then
 123 $$
 124 A = \sm{2 & 1\\0 & -1} \qquad A^{-1} = \sm{1/2 & 1/2 \\ 0 & -1 }
 125 $$
 126 and
 127 $$
 128 \sm{1 & 0 \\ 1 & 1 } \sm{2 & 1\\0 & -1} = \sm{1 & 0 \\ 0 & 2} \sm{2 & 1 \\ 1 & 0}.
 129 $$
 130 We have $\det A = \det S = 2$ and
 131 $\vec k_1^\T = \sm{0 & 0}$ and $\vec k_2^\T = \sm{0 & 1}$.
 132 Therefore,
 133 $$
 134 \vec w_1^\T = \fractional{\sm{0 & 0} \sm{2 & 1 \\ 1 & 0} \sm{1/2 & 1/2 \\ 0 & -1 }}
 135 \sm{2 & 1\\0 & -1} = \sm{0 & 0}
 136 $$
 137 and
 138 \begin{eqnarray*}
 139 \vec w_2^\T & = &
 140 \fractional{\sm{0 & 1} \sm{2 & 1 \\ 1 & 0} \sm{1/2 & 1/2 \\ 0 & -1 }}
 141 \sm{2 & 1\\0 & -1}
 142 \\
 143 & = &
 144 \sm{1/2 & 1/2} \sm{2 & 1\\0 & -1} = \sm{1 & 0}.
 145 \end{eqnarray*}
 146 \end{example}