Read-back: Def_SmaleNinth_Khachiyan

Seven definitions in the namespace SmaleNinth. All are total functions of natural-number parameters $n, U$ (and, for the two "system" definitions, of an integer matrix or vector); every occurrence of $n$, $U$, a factorial, or an integer entry below denotes its cast into the real numbers. None of these definitions refer to the imported polyhedron, ellipsoid, ellipsoidBall, or any other definition from the dependency files; they are standalone arithmetic and matrix constructions.

khachiyanEps

For natural numbers $n, U$, the real number

$$\varepsilon(n,U) \;=\; \frac{1}{\,2\,(n+1)\,(n+1)!\;U^{\,n+1}\,},$$

where $(n+1)!$ is the factorial of the natural number $n+1$ and $U^{n+1}$ is the real power of the cast of $U$. Edge cases. If $U = 0$ the denominator is $0$ (since $n+1 \ge 1$ forces $U^{n+1}=0$), and division by zero in the reals yields the junk value $\varepsilon(n,0) = 0$ — not a positive perturbation. For $U \ge 1$ the value is a genuine positive rational; e.g. $\varepsilon(0,U) = 1/(2U)$. There is no hypothesis anywhere in the definition requiring $U \ge 1$ or $n \ge 1$.

khachiyanBox

For natural numbers $n, U$, the real number

$$M(n,U) \;=\; n!\;U^{\,n} + 1.$$

Edge cases. For $n = 0$ the convention $U^0 = 1$ (which holds in the code even when $U = 0$) gives $M(0,U) = 2$. For $U = 0$ and $n \ge 1$, $M(n,0) = 1$. The value is always $\ge 1$.

khachiyanSystemA

Given natural numbers $m, n$ (implicit, read off from the matrix's shape) and an integer matrix $A \in \mathbb{Z}^{m \times n}$ (indexed by $\{0,\dots,m-1\} \times \{0,\dots,n-1\}$), this is the real matrix

$$\widehat{A} \;\in\; \mathbb{R}^{(m+n+n) \times n},$$

whose rows are indexed by $i \in \{0, \dots, m+2n-1\}$ and whose entry in row $i$, column $j$ is defined by a three-way case split on the numeric value of $i$:

• if $i < m$ (first block, $m$ rows): $\widehat{A}_{ij} = A_{ij}$, the real cast of the corresponding integer entry (row $i$ of $A$ itself);
• else if $i < m+n$ (second block, $n$ rows): $\widehat{A}_{ij} = 1$ if $j = i \mathbin{\dot-} m$ and $0$ otherwise, where $\mathbin{\dot-}$ is truncated natural subtraction; since this branch only fires when $m \le i < m+n$, the subtraction is genuine and $i \mathbin{\dot-} m$ ranges over $\{0,\dots,n-1\}$, so this block is the $n \times n$ identity matrix $I_n$;
• else (third block, the remaining $n$ rows, $m+n \le i < m+2n$): $\widehat{A}_{ij} = -1$ if $j = i \mathbin{\dot-} m \mathbin{\dot-} n$ and $0$ otherwise; again the subtraction is genuine on this branch and $i \mathbin{\dot-} m \mathbin{\dot-} n$ ranges over $\{0,\dots,n-1\}$, so this block is $-I_n$.

In block form:

$$\widehat{A} \;=\; \begin{pmatrix} A \\ I_n \\ -I_n \end{pmatrix}.$$

The column-index comparison $j = i \mathbin{\dot-} m$ is a comparison of the underlying natural numbers. Edge cases. If $n = 0$ the matrix has no columns and only the first block's index range is inhabited ($\widehat{A}$ is an $m \times 0$ empty matrix); if $m = 0$ the first branch never fires and $\widehat{A} = \binom{I_n}{-I_n}$. The truncated subtraction never produces an out-of-range junk value because each branch's guard ensures the subtrahend does not exceed $i$.

khachiyanSystemb

Given a natural number $m$ (implicit, read off from the vector) and explicit natural numbers $n, U$, and an integer vector $b \in \mathbb{Z}^m$, this is the real vector $\widehat{b} \in \mathbb{R}^{m+n+n}$ with

$$\widehat{b}_i \;=\; \begin{cases} b_i - \varepsilon(n,U) & \text{if } i < m \quad (\text{cast of the integer } b_i, \text{ minus \texttt{khachiyanEps}}),\\[2pt] -\,M(n,U) & \text{otherwise (all } 2n \text{ remaining rows}), \end{cases}$$

where $\varepsilon$ is khachiyanEps and $M$ is khachiyanBox. Note that $n$ and $U$ are free explicit arguments: nothing in the definition ties $n$ to the column count of any matrix or ties $U$ to a bound on the entries of $b$ (or of any $A$) — the caller may pass any values, and coherence with khachiyanSystemA (which produces $m+n+n$ rows for its own implicit $n$) is only by matching indices at the use site. Edge cases. With $U = 0$ the perturbation is the junk value $\varepsilon(n,0)=0$, so the first block is just the cast of $b$; with $n = 0$ the second case is never reached.

khachiyanVolLB

For natural numbers $n, U$, the real number

$$v(n,U) \;=\; \left(\frac{\varepsilon(n,U)}{\,n\,U\,}\right)^{\!n},$$

with $\varepsilon$ = khachiyanEps and the product $nU$ formed from the real casts. Edge cases. For $n = 0$ the zeroth power gives $v(0,U) = 1$ regardless of the (division-by-zero) base — even though the base is then $\varepsilon/0 = 0$ (junk). For $n \ge 1$ and $U = 0$, both $\varepsilon = 0$ and the denominator $nU = 0$, so the base is $0/0 = 0$ and $v(n,0) = 0$. For $n \ge 1$, $U \ge 1$ the value is a genuine positive number.

khachiyanRadius

For natural numbers $n, U$, the real number

$$r(n,U) \;=\; (n+1)\,M(n,U),$$

with $M$ = khachiyanBox. Always $\ge 1$; e.g. $r(0,U) = 2$ and $r(n,0) = n+1$.

khachiyanIterations

For natural numbers $n, U$, the natural number

$$t^\ast(n,U) \;=\; \left\lceil\, 2\,(n+1)\cdot \log\!\left( \frac{\bigl(2\,r(n,U)\bigr)^{n}}{\,v(n,U)/2\,} \right) \right\rceil_{\!\mathbb{N}},$$

where $r$ = khachiyanRadius, $v$ = khachiyanVolLB, $\log$ is the real natural logarithm as a total function (with the junk convention $\log x = 0$ for $x \le 0$), and $\lceil\cdot\rceil_{\mathbb{N}}$ is the ceiling into the natural numbers, which sends every non-positive real to $0$. The exponent $n$ in $(2r)^n$ is a natural power of a real. Edge cases. For $n = 0$: $(2r)^0 = 1$, $v = 1$, so $t^\ast(0,U) = \lceil 2\log 2\rceil_{\mathbb{N}} = 2$ for every $U$. For $n \ge 1$ and $U = 0$: $v = 0$, so the argument of $\log$ is $(2r)^n / 0 = 0$ (division-by-zero junk), $\log 0 = 0$, and $t^\ast(n,0) = 0$ — a zero iteration budget. Nothing in the definition guards against these degenerate parameter choices; the definition itself asserts no property of the number it produces (in particular no claim that it bounds any algorithm's iterations — that would be the content of theorems stated elsewhere).