Is there a way to find an efficient set of relations for presenting the subgroup generated by two matrices in $SL(2, q)$? Given two elements $a, b \in SL(2, \mathbb{F}_q)$, is there a way to find an efficient presentation $$\langle x, y \mid \text{relations}\rangle$$ of the subgroup $\langle a, b \rangle$?
My intention is taking two random matrices, computing the group law for the subgroup generated by them, and studying a particular recurrence relation using that group law.
 A: Yes there is algorithm for this due to John Cannon. The original reference is
CANNON, J.J. (1973): Construction of defining relators for finite groups, Discrete Math. 5, pp. 105–129.
You can also read about this and related algorithms in Chapter 6 of "Handbook of Computational Group Theory" by Holt, Eick, and O'Brien.
If you want an presentation on your own given generators, then it will only work for moderately small groups - perhaps up to about order $10^7$. You can compute presentations for much larger groups if you allow the algorithm to introduce new generators.
It is available in Magma as the command $\texttt{FPGroup}$ and also in $\textsf{GAP}$, although I am less familiar with $\textsf{GAP}$.
I just tried $\texttt{FPGroup}$ on ${\rm SL}(2,127)$ of order just over $2$ million and it took about 40 seconds to compute a presentation on two given generators with 5 relators and total relator length $70$.
The presentations computed in this way are not typically very nice in that the relators look like random strings of generators, but they are reasonably efficient in terms of relator length.
The algorithm works by attemtping coset enumeration over the trivial subgroup using the relators found so far. If this does not seem to be completing then you interrupt the process, introduce a new relator, and then resume the coset enumeration from where you left off. To find the new relator, you find the first missing entry in the coset table, use the group to work out what the entry should be, and then find the corresponding relator that will define that entry. A typical criterion for interrupting is when the total number of cosets that you have defined exceeds the actual number by $10\%$.
With a larger group, you could choose a subgroup $H$ of order about $\sqrt{|G|}$ (or for even larger groups, a chain of subsgroups with roughly equal indices), introduce generators of $H$ if necessary as new generators expressed as words in the original generators, and then comoute presentations first of $H$, and then of $G$, using coset enumeration over $H$.
Afterwards you could if eliminate the new generators to get a presentation on the original generators, but that would usually result in very long relators. Alternatively you can compromise by regarding the relators as straight line programs in the original generators, which can be helpful for example if you are trying to verfiy that a map defined on the group is a homomorphism.
I don't believe that the complexity has been analysed formally, but I would guess that it is between linear and quadratic in $|G|$. There is an obvious quadratic algorithm using the group multiplication table.
You can use the chain of subgroups idea using a stabilizer chain on a permutation group with base and strong generating set to get a presentation on the strong generators. This is polynomial in the degree of the permutation group.
