Computation of Atomic Fibers of Z-Linear Maps

Abstract

For given matrix $A\in {\mathbb{Z}}^{d\times n}$, the set $P_{A,b}^I=\{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_{A,b}^I$ is called atomic, if $P_{A,b}^I=P_{A,b_1}^I+P_{A,b_2}^I$ 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, application to integer programming, and computational examples are included as well.