Computation of Atomic Fibers of Z-Linear Maps

Abstract

For given matrix $A\in {\mathbb{Z}}^{d\times n}$, the set $P_b=\{z:Az=b,z\in {\mathbb{Z}}_{+}^n\}$ describes the preimage or fiber of $b\in {\mathbb{Z}}^d$ under the $\mathbb{Z}$-linear map $f_A:{\mathbb{Z}}_{+}^n\to {\mathbb{Z}}^d$, $x\mapsto Ax$. The fiber $P_b$ is called atomic, if $P_b=P_{b_1}+P_{b_2}$ implies $b=b_1$ or $b=b_2$. In this paper we present a novel algorithm to compute such atomic fibers. An algorithmic solution to appearing subproblems, computational examples and applications are included as well.

27 pages