Let $ M$ be a finitely generated abelian group. Assume we are given a presentation of $ M$ , that is \begin{equation*} M = \frac{\bigoplus_{i=1}^r \mathbf{Z}g_i}{\sum_{j=1}^s \mathbf{Z} r_j} \end{equation*} where the $ g_i$ are the generators and the $ r_j$ are the relations.

Let $ x$ be an element of $ M$ , given as a linear combination of the generators. I want to express $ x$ as a linear combination of the generators of the shortest length. Is there an efficient algorithm to do this?

If that helps, I know that $ M$ is torsion free and that $ x$ generates the kernel of a family of linear operators on $ M$ (given explicitly in terms of the generators).

My motivation for asking comes from the theory of modular symbols. If $ M$ denotes the space of modular symbols of weight 2 on $ \Gamma_0(N)$ and $ x_E^\pm$ is the modular symbol associated to an elliptic curve $ E/\mathbf{Q}$ of conductor $ N$ , I want to express $ x_E^\pm$ as a short linear combination of the Manin symbols $ \{g_i 0, g_i \infty\}$ with $ g_i \in \Gamma_0(N) \backslash \mathrm{SL}_2(\mathbf{Z})$ .