Locating a near-largest eigenvalue in the exact-query model

For a diagonalizable complex $n \times n$ matrix $A$ accessed only through
exact products $v \mapsto Av$, with a supplied bound $K \ge 1$ on the
condition number of an eigenvector matrix and positive spectral radius $\rho$,
a randomized algorithm is given that uses
$O(\varepsilon^{-2}[1 + \log(nK)])$ queries and,
with probability at least $0.997$, returns $z$ such that some eigenvalue $\mu$
satisfies $|\mu| \ge (1 - \varepsilon)\rho$ and
$|z - \mu| \le \varepsilon\rho$, for every $0 < \varepsilon < 1/2$. A
starting vector $u$ drawn from a fine uniform grid gives, with that
probability, two-sided bounds on $\|p(A)u\|_2$ by $\max_\lambda |p(\lambda)|$
for all polynomials $p$ at once. Without further queries, the algorithm
approximates $\rho$ by $r \approx \|A^m u\|_2^{1/m}$ and returns the point $z$
of a finite net of the circle of radius $r$ that maximises
$\|(A + zI)^m u\|_2$. Intermediate work is finite exact arithmetic;
floating-point stability is not addressed.