  We consider fast algorithms for monotone submodular maximization with a
general matroid constraint. We present a randomized $(1 - 1/e -
\epsilon)$-approximation algorithm that requires $\tilde{O}_{\epsilon}(\sqrt{r}
n)$ independence oracle and value oracle queries, where $n$ is the number of
elements in the matroid and $r \leq n$ is the rank of the matroid. This
improves upon the previously best algorithm by Buchbinder-Feldman-Schwartz
[Mathematics of Operations Research 2017] that requires
$\tilde{O}_{\epsilon}(r^2 + \sqrt{r}n)$ queries.
  Our algorithm is based on continuous relaxation, as with other submodular
maximization algorithms in the literature. To achieve subquadratic query
complexity, we develop a new rounding algorithm, which is our main technical
contribution. The rounding algorithm takes as input a point represented as a
convex combination of $t$ bases of a matroid and rounds it to an integral
solution. Our rounding algorithm requires $\tilde{O}(r^{3/2} t)$ independence
oracle queries, while the previously best rounding algorithm by
Chekuri-Vondr\'{a}k-Zenklusen [FOCS 2010] requires $O(r^2 t)$ independence
oracle queries. A key idea in our rounding algorithm is to use a directed cycle
of arbitrary length in an auxiliary graph, while the algorithm of
Chekuri-Vondr\'{a}k-Zenklusen focused on directed cycles of length two.
