  Fast algorithms for submodular maximization problems have a vast potential
use in applicative settings, such as machine learning, social networks, and
economics. Though fast algorithms were known for some special cases, only
recently Badanidiyuru and Vondr\'{a}k (2014) were the first to explicitly look
for such algorithms in the general case of maximizing a monotone submodular
function subject to a matroid independence constraint. The algorithm of
Badanidiyuru and Vondr\'{a}k matches the best possible approximation guarantee,
while trying to reduce the number of value oracle queries the algorithm
performs.
  Our main result is a new algorithm for this general case which establishes a
surprising tradeoff between two seemingly unrelated quantities: the number of
value oracle queries and the number of matroid independence queries performed
by the algorithm. Specifically, one can decrease the former by increasing the
latter and vice versa, while maintaining the best possible approximation
guarantee. Such a tradeoff is very useful since various applications might
incur significantly different costs in querying the value and matroid
independence oracles. Furthermore, in case the rank of the matroid is $O(n^c)$,
where $n$ is the size of the ground set and $c$ is an absolute constant smaller
than $1$, the total number of oracle queries our algorithm uses can be made to
have a smaller magnitude compared to that needed by Badanidiyuru and
Vondr\'{a}k. We also provide even faster algorithms for the well studied
special cases of a cardinality constraint and a partition matroid independence
constraint, both of which capture many real-world applications and have been
widely studied both theorically and in practice.
