I have a certain class of objects, which can be thought of either as modules over a ring $R[x]$ or as functors, and I am looking for algorithms to decompose these objects into indecomposable summands. Here are a few different versions of the problem.
Version 1
Suppose that $R$ is a PID and $M$ is a graded module over the polynomial ring $R[x]$. Concretely, we have
- $M = \bigoplus_i M_i$
- multiplication with $r \in R$ maps elements of $M_i$ to elements of $M_i$
- multiplication with $x$ maps elements of $M_i$ to $M_{i+1}$
for all $i$. Suppose, in addition, that
- there exists a finite $m$ such that $M_i = 0$ for $i \notin \{1, \ldots, m\}$
- each submodule $M_i$ is a free, finitely generated module over $R$.
Question What algorithms exist to obtain a Krull-Schmidt decomposition of $M$? What is their time complexity? Even a special case would be interesting. For example, suppose that $R$ is the ring of integers.
Version 2
Suppose that $M$ is a persistence module valued in the category of free, finitely-generated modules over a PID $R$. That is, $f$ is a functor from the poset category of the totally ordered set $\{0 \le 1 \le \cdots \le m\}$ into the category of free, finitely generated modules over $R$. What algorithms exist to decompose $M$ as the direct sum of indecomposable submodules?
Version 3
As a special case of the preceding two problems, is there an algorithm that can determine the truth value of the following statement: $M$ is a direct sum of interval submodules, meaning submodules which are isomorphic modules of form $0 \to \cdots 0 \to R \xrightarrow{id} \cdots \xrightarrow{id} R \to 0 \to \cdots \to 0$
Details
For the purposes of formalizing this problem, we can assume the input $M$ has any form that's compatible with a modern programing language. For example, we can represent $M$ as a sequence of matrices $A_0, A_1, \ldots, A_m$ such that $A_i$ represents either the map $M_i \to M_{i+1}$ given by multiplication with $x$, i.e. $a \mapsto x \cdot a$ or, equivalently, the homomorphism $M(i \le i+1)$.