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 (EDIT : the length of a linear combination $\sum_{i=1}^r \lambda_i g_i$ is the number of nonzero $\lambda_i$'s). 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})$.