  In the field of topological data analysis, persistence modules are used to
express geometrical features of data sets. The matching distance
$d_\mathcal{M}$ measures the difference between $2$-parameter persistence
modules by taking the maximum bottleneck distance between $1$-parameter slices
of the modules. The previous best algorithm to compute $d_\mathcal{M}$ exactly
runs in $O(n^{8+\omega})$ time using $O(n^4)$ space, where $n$ is the number of
generators and relations of the modules and $\omega$ is the matrix
multiplication constant. We improve significantly on this by describing an
algorithm with expected running time $O(n^5 \log^3 n)$ and using $O(n^2)$
space. We first solve the decision problem $d_\mathcal{M}\leq \lambda$ for a
constant $\lambda$ in $O(n^5\log n)$ time by traversing a line arrangement in
the dual plane, where each point represents a slice. Then we lift the line
arrangement to a plane arrangement in $\mathbb{R}^3$ whose vertices represent
possible values for $d_\mathcal{M}$, and use a randomized incremental method to
search through the vertices and find $d_\mathcal{M}$. The expected running time
of this algorithm is $O((n^4+T(n))\log^2 n)$, where $T(n)$ is an upper bound
for the complexity of deciding if $d_\mathcal{M}\leq \lambda$. Moreover, we
show how to compute the matching distance using only linear space, to the price
of a much worse time complexity.
