  Recently, there has been increasing interest in using matrix-free methods to
solve linear programs due to their ability to attack extreme-scale problems.
Each iteration of these methods is a matrix-vector product, so they benefit
from a low memory footprint and are parallelized easily. Restarted primal-dual
hybrid gradient (PDHG) is a matrix-free method with good practical performance.
Prior analysis showed that it converges linearly on linear programs where the
linear convergence constant depends on the Hoffman constant of the KKT system.
  We refine this analysis of restarted PDHG for totally unimodular linear
programs. In particular, we show that restarted PDHG finds an
$\epsilon$-optimal solution in $O( H m_1^{2.5} \sqrt{\textbf{nnz}(A)} \log(H
m_2 /\epsilon) )$ matrix-vector multiplies where $m_1$ is the number of
constraints, $m_2$ the number of variables, $\textbf{nnz}(A)$ is the number of
nonzeros in the constraint matrix, $H$ is the largest absolute coefficient in
the right hand side or objective vector, and $\epsilon$ is the distance to
optimality of the point outputted by PDHG.
