  We introduce an algorithm, the Orthogonal Operator Polynomial Expansion
(OOPEX), to approximately compute expectation values in energy eigenstates at
finite energy density of non-integrable quantum many-body systems with
polynomial effort, whereas exact diagonalization (ED) of the Hamiltonian $H$ is
exponentially hard. The OOPEX relies on the eigenstate thermalization
hypothesis, which conjectures that eigenstate expectation values of physical
observables in such systems vary smoothly with the eigenstate energy (and other
macroscopic conserved quantities, if any), and computes them through a series
generated by repeated multiplications, rather than diagonalization, of $H$ and
whose successive terms oscillate faster with the energy. The hypothesis
guarantees that only the first few terms of this series contribute appreciably.
We further show that the OOPEX, in a sense, is the most optimum algorithm based
on series expansions of $H$ as it avoids computing the many-body density of
states which plagues other similar algorithms. Then, we argue non-rigorously
that working in the Fock space of operators, rather than that of states as is
usually done, yields convergent results with computational resources that scale
polynomially with $N$. We demonstrate the polynomial scaling by applying the
OOPEX to the non-integrable Ising chain and comparing with ED and
high-temperature expansion (HTX) results. The OOPEX provides access to much
larger $N$ than ED and HTX do, which facilitates overcoming finite-size effects
that plague the other methods to extract correlation lengths in chaotic
eigenstates. In addition, access to large systems allows testing a recent
conjecture that the Renyi entropy of chaotic eigenstates has positive curvature
if the Renyi index $>1$, and we find encouraging supporting evidence.
