Iterative Numerical Integration

Question

I am aware that this question has been asked before, (e.g. Iterative integration algorthm), however the answers are a bit dissatisfying. When using an iterative scheme, typically a few desiderata are required, so my question is the following:

Q: What are examples of iterative integration schemes that satisfy the following desiderata?

1. Constant memory - the memory required by the scheme should not increase with the number of iterations done, or at most increase linearly
2. Constant compute - each iteration should take approximately the same amount of time to carry out, or at most increase linearly (and not exponentially like with the divide&conquer approach)
3. Efficacy & Interpretability - the iteration scheme should be constructed in such a way, that each iterate tries to optimally solve a subproblem. (example: in GMRES we have $x_m = \operatorname{argmin}\limits_{y\in \mathcal{K}_m} \| b-Ay \|_2.$)
4. Stopping Criteria: There should be simple stopping criteria that allow us to make quantitative claims, e.g. something along the lines: "if $f$ is Lipschitz cont. with constant $L$, and $|I_{k+1}(f, a, b]) - \int_a^b f(x) dx|\le \epsilon$, then $|I_k(f, a, b))-I^*(f, a, b)|\le g(\epsilon, L, b-a)$"

Answer 1

A "global" adaptive quadrature scheme is an example of what you want.

Fix: A quadrature scheme $Q(f;I)$ with error estimator $\varepsilon(f;I)$ for the value of $\int_I f$ (e.g., a Newton-Cotes formula), a method $m(I)$ of coming up with a point inside an interval $I$.

Initial data: Start with $[a,b]$ with no subdivisions and calculate $Q(f;[a,b]),\varepsilon(f;[a,b])$, $Q_0=Q(f;[a,b])$, $\epsilon_0=\varepsilon(f;[a,b])$.

Iteration step: Locate $(I,Q,\varepsilon)$ with largest $\varepsilon$, say $I=[s,t]$, and create a point $m\in(s,t)$. Replace $([s,t],Q(f;[s,t]),\varepsilon(f;[s,t]))$ by $([s,m],Q(f;[s,m]),\varepsilon(f;[s,m]))$ and $([m,t],Q(f;[m,t]),\varepsilon(f;[m,t]))$ in our list. Update $Q_{new}=Q_{old}-Q(f;[s,t])+Q(f;[s,m])+Q(f;[m,t])$ and total error estimate $\epsilon$ similarly.

Because the scheme $Q$ is fixed, it takes an additional $O(1)$ memory and computation (ignore limitation of fixed-precision arithmetics), except for the sorting of intervals according to error estimate which takes $O(\log n)$ for binary insertion into a sorted list. If your quadrature scheme $Q(f;I)$ is reasonable, then it is exact on some space of integrable functions on $I$, so each iterate solves the problem on piecewise blah where your intervals define the pieces (and hopefully we have uniform convergence of piecewise blah approximations of $f$ to $f$ itself). Finally, you have a bound of the error $\epsilon$ and can make claims about, e.g., how many iterations it will take (deterministic or probabilistic) based on $Q,f,m$.