  We consider fast algorithms for monotone submodular maximization subject to a
matroid constraint. We assume that the matroid is given as input in an explicit
form, and the goal is to obtain the best possible running times for important
matroids. We develop a new algorithm for a \emph{general matroid constraint}
with a $1 - 1/e - \epsilon$ approximation that achieves a fast running time
provided we have a fast data structure for maintaining a maximum weight base in
the matroid through a sequence of decrease weight operations. We construct such
data structures for graphic matroids and partition matroids, and we obtain the
\emph{first algorithms} for these classes of matroids that achieve a
nearly-optimal, $1 - 1/e - \epsilon$ approximation, using a nearly-linear
number of function evaluations and arithmetic operations.
