Debian Codegraph @

doc/4ti2_manual_advanced.tex

raw ◀ ▶
Source reconstructed at patch state 0 of 1 — not the installed (fully patched) source.
1 Debian patch touch this file
1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 %
3 % 4ti2 User Guide, Advanced guide
4 %
5 % $Id$
6 %
7 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8
9 \chapter{Advanced guide}
10
11 In this part, we deal with several more advanced problem
12 specifications in \FourTiTwo{}.
13
14 First we introduce \emph{affine systems} and their encodings. In
15 fact, affine systems are the basic objects used in \FourTiTwo{},
16 since every linear system is transformed into an affine system.
17 However, in the integer situation, it is not always possible to
18 transform an affine system back into a linear system without adding
19 variables or modulo constraints.
20
21 %% Next, we demonstrate how one can exploit bounds on integer variables
22 %% to truncate the solution set.
23
24 %% Again, we use a few sample problems to demonstrate how to use
25 %% \FourTiTwo{}. After working through this part, you should know about
26 %% how to run the following functions on affine systems:
27 %% \begin{itemize}
28 %% \item \File{qsolve}, \File{rays}, \File{circuits}
29 %% \item \File{zsolve}, \File{hilbert}, \File{graver}
30 %% \item \File{markov}, \File{groebner}, \File{normalform}, \File{minimize}
31 %% \end{itemize}
32
33
34 \section{Affine systems and their encodings}
35
36 %% In \FourTiTwo, the definition of an \emph{affine system} is slightly
37 %% different for the continuous and for the integer situation. In fact,
38 %% the definition for the integer case is simply the integer analogue
39 %% to the definition for the continuous case.
40
41 %% \subsection{Continuous affine systems}
42
43 %% Let $a+\Lattice_{\R}$ be a linear affine space given by the vector
44 %% $a$ and by generators for the linear space $\Lattice_{\R}$. We wish
45 %% to find a finite sign-compatible description for the set of all
46 %% vectors $x\in a+\Lattice_{\R}$.
47
48 %% \subsection{Integer affine systems}
49
50 Let $a+\Lattice_{\Z}$ be an ``integer linear affine space'' given by
51 the vector $a\in\Z^n$ and by generators for the lattice
52 $\Lattice_{\Z}\subseteq\Z^n$. We wish to find a finite
53 sign-compatible description for the set of all (integer) vectors
54 $x\in a+\Lattice_{\Z}$.
55
56 %% \subsection{Specifying an affine system in \FourTiTwo{}}
57
58 % Currently, only homogeneous affine systems can be solved in
59 % \FourTiTwo{} over $\R$ and over $\Z$ using the functions
60 % \File{qsolve} and \File{zsolve}, respectively. In order to call
61 % these functions,
62 %% One needs to specify an affine system to
63 %% \FourTiTwo.
64
65 As an example, let consider the linear space $\Lattice_{\R}$ and the
66 lattice $\Lattice_{\Z}$ both spanned by the two vectors $(1,-2,1,0)$
67 and $(2,-3,-0,1)$. Moreover, consider the sign-constraints
68 $(1,2,2,0)$. Thus, we are looking for a finite explicit
69 sign-compatible description for all $x$ that can be written as
70 \[
71 x=\left(
72 \begin{array}{rr}
73 1 & 2\\
74 -2 & -3\\
75 1 & 0\\
76 0 & 1\\
77 \end{array}
78 \right)\lambda,
79 \]
80 with $\lambda\in\R^2$ and $\lambda\in\Z^2$, respectively.
81
82 In order to solve this affine system using %% \File{qsolve} or
83 \File{zsolve}, we create the following input files to encode the
84 affine system:
85 \begin{center}
86 \begin{tabular}{|l|l|}
87 \hline
88 \text{ affine.lat } & \text{ affine.sign }\\
89 \hline
90 $\begin{array}{rrrrrr}& 2 & 4 & & &\\& 1 & -1 & 1 & 0 &\\& 2 & -3 & 0 & 1 &\\ \end{array}$ &
91 $\begin{array}{rrrrrr}& 1 & 4 & & &\\& 1 & 2 & 2 & 0 &\\ \\ \\\end{array}$\\
92 \hline
93 \end{tabular}
94 \end{center}
95 and then call
96 %% \begin{center}
97 %% {\tt ./qsolve affine}
98 %% \end{center}
99 %% %%%%%%%%%%%%%%%%% This doesn't work in 4ti2 1.6.2
100 %% and
101 \begin{center}
102 {\tt ./zsolve affine}
103 \end{center}
104 %% In the continuous case, this creates the files \File{affine.qhom}
105 %% and \File{affine.qfree}, and in the integer case
106 This creates the
107 files \File{affine.zhom} and \File{affine.zinhom}. %% and \File{affine.zfree}.
108
109 %% In contrast to calling %% \File{qsolve} and
110 %% \File{zsolve} on a linear
111 %% system, these calls create only two files, since at the moment only
112 %% homogeneous affine systems (with $a=0$) are supported by
113 %% \FourTiTwo{}.
114
115
116
117 %%% Local Variables:
118 %%% mode: latex
119 %%% TeX-master: "4ti2_manual"
120 %%% End: