From 921da6c39336b474fcf0e21cfe21e7570d062aac Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Thu, 26 Apr 2007 15:44:35 +0200
Subject: [PATCH] doc: document left_inverse

---
 doc/implementation.tex | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++
 util.c                 |  4 +++
 2 files changed, 78 insertions(+)

diff --git a/doc/implementation.tex b/doc/implementation.tex
index 458da8a..8bf7f4c 100644
--- a/doc/implementation.tex
+++ b/doc/implementation.tex
@@ -1079,3 +1079,77 @@ Lattice:
  )
 \end{verbatim}
 \end{example}
+
+\subsection{Left inverse of an affine embedding}
+
+We often map a polytope onto a lower dimensional space to remove possible
+equalities in the polytope.  These maps are typically represented
+by the inverse, mapping the coordinates $\vec x'$ of the lower-dimensional
+space to the coordinates $\vec x$ of (an affine subspace of) the original space,
+i.e.,
+$$
+\begin{bmatrix}
+\vec x \\ 1
+\end{bmatrix}
+=
+\begin{bmatrix}
+T & \vec v \\ \vec 0^\T & 1
+\end{bmatrix}
+\begin{bmatrix}
+\vec x' \\ 1
+\end{bmatrix}
+,
+$$
+where, as usual in \PolyLib/, we work with homogeneous coordinates.
+To obtain the transformation that maps the coordinates of the original
+space to the coordinates of the lower dimensional space,
+we need to compute the \ai{left inverse} of the above \ai{affine embedding},
+i.e., an $A$, $\vec b$ and $d$ such that
+$$
+d
+\begin{bmatrix}
+\vec x' \\ 1
+\end{bmatrix}
+=
+\begin{bmatrix}
+A & \vec b \\ \vec 0^\T & d
+\end{bmatrix}
+\begin{bmatrix}
+\vec x \\ 1
+\end{bmatrix}
+$$
+
+To compute this left inverse, we first compute the
+(right) \indac{HNF} of T,
+$$
+\begin{bmatrix}
+U_1 \\ U_2
+\end{bmatrix}
+T
+=
+\begin{bmatrix}
+H \\ 0
+\end{bmatrix}
+.
+$$
+The left inverse is then simply
+$$
+\begin{bmatrix}
+d H^{-1}U_1 & -d H^{-1} \vec v \\ \vec 0^\T & d
+\end{bmatrix}
+.
+$$
+We often also want a decription of the affine subspace that is the range
+of the affine embedding and this is given by
+$$
+\begin{bmatrix}
+U_2 & - U_2 \vec v \\ \vec 0^T & 1
+\end{bmatrix}
+\begin{bmatrix}
+\vec x \\ 1
+\end{bmatrix}
+=
+\vec 0
+.
+$$
+This computation is implemented in \ai[\tt]{left\_inverse}.
diff --git a/util.c b/util.c
index 933daaf..a073a2c 100644
--- a/util.c
+++ b/util.c
@@ -1556,6 +1556,10 @@ Matrix *compress_variables(Matrix *Equalities, unsigned nparam)
     return T;
 }
 
+/* Computes the left inverse of an affine embedding M and, if Eq is not NULL,
+ * the equalities that define the affine subspace onto which M maps
+ * its argument.
+ */
 Matrix *left_inverse(Matrix *M, Matrix **Eq)
 {
     int i, ok;
-- 
2.11.4.GIT