Moshe’s answer points out that one gets a quadratic algorithm for the word problem for subgroups of $GL_N(\mathbb{Z})$. I thought I would expand a comment on his answer into an answer, since I’m not aware of such a result strictly in the literature (even though it is relatively trivial, the estimate depends on recent advances).

Firstly, as you can find from the reference 3-Manifold Groups cited in Moshe’s answer, a compact orientable 3-manifold $M$ admitting a non-positively curved metric (which includes compact irreducible manifolds with non-empty boundary) admits a faithful representation of its fundamental group into $GL_N(\mathbb{Z})$ for some $N$ depending on $M$. This follows from results of Yi Liu in the graph manifold case and Przytycki-Wise in the “mixed manifold” case (see Cor. 1.2), where there is a hyperbolic piece of the JSJ decomposition (such irreducible manifolds always admit non-positively curved metric by a result of Bernhard Leeb). The remaining graph manifold cases may have linear fundamental group, but there are certain restrictions.

In any case, one can show that finitely-generated subgroups of $GL_N(\mathbb{Z})$ have word problem which is $O(n\log^2 n)$ in the length of the word $n$. Suppose that we are given $k$ $N\times N$ matrices $A_1,\ldots, A_k \in GL_N(\mathbb{Z})$ which generate the group $G<GL_N(\mathbb{Z})$ as a semigroup (so if we are initially given generators, we can add throw in their inverses to get a semigroup generating set). The word problem then asks whether the product $A_{i_1} A_{i_2}\cdots A_{i_n} = I$ for a sequence $i_1, \ldots, i_n,$ where $i_j \in \{1,\ldots,k\}$.

If the entries of the matrices $A, B \in GL_N(\mathbb{Z})$ are integers represented by at most $a$ and $b$ bits respectively, then the product $AB$ will have entries with at most $a+b+N$ bits, since each entry is the sum of $N$ integers with at most $a+b$ bits. Assuming $b$ is bounded, then we can compute the product in time $O(a)$, where the constant depends on $b$ and $N$. So to multiply $n$ matrices whose entries have size $b$, this takes at most time $O(n^2)$. This gives the $O(n^2)$ estimate in Moshe’s answer.

Note that due to recent advances, multiplication of numbers of size $a$ takes time at most $a\log a$, although sub-$a^2$ algorithms have been known for a while. So multiplying matrices whose entries use at most $a$ bits takes time $O(a\log a)$, where the constant depends on $N$.

A more efficient procedure in theory to multiply $n$ things is to divide and conquer. For clarity, let’s consider the worst case where $n=2^m$. First compute the products $A= A_{i_1}\cdots A_{i_{2^{m-1}}}$ and $B=A_{i_{2^{m-1}+1}}\cdots A_{i_n}$. These matrices have entries of size (number of bits) $C n/2=C2^{m-1}$ for some constant $C$ depending on $\{A_1,\ldots,A_k\}$. Computing $AB =A_{i_1}\cdots A_{i_n}$ takes time $O(n/2 \log(n/2))=O(2^{m-1} (m-1)) $. By induction, computing these products in terms of 4 products of length $2^{m-2}$ takes time $O(2^{m-2} (m-2))$, but there are two matrices, so time $O(2^{m-1}(m-2))$. At the $i$th step, we multiply $2^i$ matrices of size $O(2^{m-i})$, which takes time $2^{i-1}\cdot O(2^{m-i}(m-i))=O(2^{m-1}(m-i))$. Thus, we get total time $O(2^{m-1} ((m-1)+(m-2)+\cdots + 1))=O(2^{m-1} m^2)= O(n\log^2 n)$.

For the general case, we multiply $A=A_{i_1}\cdots A_{i_{\lceil n/2\rceil}}$ and $B=A_{i_{\lceil n/2\rceil +1}}\cdots A_{i_n}$. We get a similar estimate, but our computation tree may be shorter since some of the branches terminate in the identity. In any case, at the $i$th step we multiply at most $2^i$ matrices of size at most $\approx n/2^i$, and hence we get a similar time bound of $O(n\log^2n)$. Maybe another way to think about it is that we can assume that $A_1=I$, so to compute $A_{i_1}\cdots A_{i_n}$, we append $2^{\lceil\log_2 n\rceil-n}$ copies of $A_1$ and use the procedure described in the previous paragraph. But $2^{\lceil\log_2 n\rceil}\leq 2n$, so this still takes time $O(n\log^2n)$.

Moshe’s answer points out that one gets a quadratic algorithm for the word problem for subgroups of $GL_N(\mathbb{Z})$. I thought I would expand a comment on his answer into an answer, since I’m not aware of such a result strictly in the literature (even though it is relatively trivial, the estimate depends on recent advances).

Firstly, as you can find from the reference 3-Manifold Groups cited in Moshe’s answer, a compact orientable 3-manifold $M$ admitting a non-positively curved metric (which includes compact irreducible manifolds with non-empty boundary) admits a faithful representation of its fundamental group into $GL_N(\mathbb{Z})$ for some $N$ depending on $M$. This follows from results of Yi Liu in the graph manifold case and Przytycki-Wise in the “mixed manifold” case (see Cor. 1.2), where there is a hyperbolic piece of the JSJ decomposition (such irreducible manifolds always admit non-positively curved metric by a result of Bernhard Leeb). The remaining graph manifold cases may have linear fundamental group, but there are certain restrictions.

In any case, one can show that finitely-generated subgroups of $GL_N(\mathbb{Z})$ have word problem which is $O(n\log^2 n)$ in the length of the word $n$. Suppose that we are given $k$ $N\times N$ matrices $A_1,\ldots, A_k \in GL_N(\mathbb{Z})$ which generate the group $G<GL_N(\mathbb{Z})$ as a semigroup (so if we are initially given generators, we can throw in their inverses to get a semigroup generating set). The word problem then asks whether the product $A_{i_1} A_{i_2}\cdots A_{i_n} = I$ for a sequence $i_1, \ldots, i_n,$ where $i_j \in \{1,\ldots,k\}$.

If the entries of the matrices $A, B \in GL_N(\mathbb{Z})$ are integers represented by at most $a$ and $b$ bits respectively, then the product $AB$ will have entries with at most $a+b+N$ bits, since each entry is the sum of $N$ integers with at most $a+b$ bits. Assuming $b$ is bounded, then we can compute the product in time $O(a)$, where the constant depends on $b$ and $N$. So to multiply $n$ matrices whose entries have size $b$, this takes at most time $O(n^2)$. This gives the $O(n^2)$ estimate in Moshe’s answer.

Note that due to recent advances, multiplication of numbers of size $a$ takes time at most $a\log a$, although sub-$a^2$ algorithms have been known for a while. So multiplying matrices whose entries use at most $a$ bits takes time $O(a\log a)$, where the constant depends on $N$.

A more efficient procedure in theory to multiply $n$ things is to divide and conquer. For clarity, let’s consider the worst case where $n=2^m$. First compute the products $A= A_{i_1}\cdots A_{i_{2^{m-1}}}$ and $B=A_{i_{2^{m-1}+1}}\cdots A_{i_n}$. These matrices have entries of size (number of bits) $C n/2=C2^{m-1}$ for some constant $C$ depending on $\{A_1,\ldots,A_k\}$. Computing $AB =A_{i_1}\cdots A_{i_n}$ takes time $O(n/2 \log(n/2))=O(2^{m-1} (m-1)) $. By induction, computing these products in terms of 4 products of length $2^{m-2}$ takes time $O(2^{m-2} (m-2))$, but there are two matrices, so time $O(2^{m-1}(m-2))$. At the $i$th step, we multiply $2^{i-1}$ pairs of matrices of size $O(2^{m-i})$, which takes time $2^{i-1}\cdot O(2^{m-i}(m-i))=O(2^{m-1}(m-i))$. Thus, we get total time $O(2^{m-1} ((m-1)+(m-2)+\cdots + 1))=O(2^{m-1} m^2)= O(n\log^2 n)$.

For the general case, we multiply $A=A_{i_1}\cdots A_{i_{\lceil n/2\rceil}}$ and $B=A_{i_{\lceil n/2\rceil +1}}\cdots A_{i_n}$. We get a similar estimate, but our computation tree may be shorter since some of the branches terminate in the identity. In any case, at the $i$th step we multiply at most $2^{i-1}$ pairs of matrices of size at most $\approx n/2^i$, and hence we get a similar time bound of $O(n\log^2n)$. Maybe another way to think about it is that we can assume that $A_1=I$, so to compute $A_{i_1}\cdots A_{i_n}$, we append $2^{\lceil\log_2 n\rceil-n}$ copies of $A_1$ and use the procedure described in the previous paragraph. But $2^{\lceil\log_2 n\rceil}\leq 2n$, so this still takes time $O(n\log^2n)$.