  The study of persistence relies heavily on the result that any
finitely-indexed persistence module of finite-dimensional vector spaces admits
an interval decomposition -- that is, a decomposition as a direct sum of
interval modules.
  This result fails if we replace vector spaces with modules over more general
coefficient rings. For example, not every persistence module of
finitely-generated free abelian groups admits an interval decomposition.
Nevertheless, many interesting examples of persistence modules of abelian
groups have been found to decompose into intervals, empirically.
  Due to the prevalence of these modules in applied and theoretical settings,
it is important to understand the conditions under which interval decomposition
is possible. We provide a necessary and sufficient condition, and a
polynomial-time algorithm to either (a) compute an interval decomposition of a
persistence module of freely- and finitely-generated modules over PIDs, or (b)
certify that no such decomposition exists. This complements earlier work, which
characterizes filtered topological spaces whose persistence diagrams are
independent of the choice of coefficient field.
