I want to compute the determinant of a polynomial $n \times n$ matrix where each entry is a univariate polynomial of degree at most $1$. I calculated it naively and was quickly reminded of how fast $n!$ grows. I know there are faster methods for scalar matrices like the LU decomposition but I'm not sure if they can be generalised to polynomial matrices. I have seen here a way around the problem which computes $n$ scalar determinants but it is a little too involved for me, is there anything simpler but still practical?
Since I am computing the Alexander polynomial of a knot, my matrix is the Alexander matrix.
You can simplify a presentation of the fundamental group of the knot complement first before calculating a presentation matrix for the Alexander module (the Alexander polynomial is purely a property of the fundamental group after all). It looks like I posted some Mathematica code snippets here that might be useful (though you should not consider it to be well-tested code).
One of the main issues with working with the Alexander module is that the ring $\mathbb{Z}[t^{\pm 1}]$ is not a principal ideal domain. However, you can pass to $\mathbb{Q}[t^{\pm 1}]$ and compute determinants (potentially using the theorem that the Alexander polynomial evaluated at $t=1$ is $1$ to find the right scaling factor for the result, depending on how you go about calculating things). This is a PID, so you can compute Smith Normal Form, and from there the determinant is easy.
Likewise, another approach is that you can pass to the field $\mathbb{Q}(t)$ of rational functions and do Gaussian elimination to compute the determinant. This is an $O(n^3)$ algorithm (ignoring complexity from the degrees of the polynomials), and there is no need to use the $O(n!)$ algorithm when you are working over a field.
In KnotFolio I do some fundamental group simplifications then do a half-hearted attempt at computing something like a Smith Normal Form (which doesn't always exist over $\mathbb{Z}[t^{\pm 1}]$) before doing cofactor expansions. Part of this is that I wanted to see the Alexander module presentation matrix in a reasonably simplified form, since it's interesting to know when the Alexander polynomial factorizes even though the presentation matrix isn't block diagonal. This is an algebraic property you lose when you work even over just $\mathbb{Q}[t^{\pm 1}]$.