Sketch-and-Track: Training-Free Online Basis Updates for Nonlinear Porous Media Flow

Simulating water moving through unsaturated soil means solving the Richards equation, a nonlinear diffusion equation whose permeability depends on the evolving pressure. On realistic heterogeneous rock or soil, practitioners use multiscale methods. These methods solve small local problems to build a handful of custom "basis functions" per coarse block and then solve a much smaller coarse problem. The nonlinearity breaks this bargain. Every nonlinear iteration changes the permeability, so the local bases must in principle be rebuilt online, and the offline savings are lost. The current fix trains a neural network to predict the updated bases. That works, but it needs thousands of fine-scale training solves per neighborhood before it can run once.

We propose a different route that needs no training. The route rests on a fact established repeatedly in the multiscale literature: the space of local solutions is intrinsically low-dimensional. Two consequences follow. A few solves with random boundary data are enough to probe that space. And because the permeability changes only a little between nonlinear iterations, the space drifts slowly. We therefore track the local basis across iterations. A few random probes per block measure how far the true local solution space has moved away from the current basis. Blocks that have not moved are left alone. Blocks that have moved receive a cheap correction built from the probe residuals. The result is an online update whose cost scales with the local intrinsic dimension and with how much the solution changes, not with the size of the snapshot space or a training set.

Core Claim

In Picard-linearized, generalized multiscale finite element (GMsFEM) simulation of the Richards equation, the online basis update can be replaced by randomized subspace tracking. This update is warm-started from the previous iteration's basis and gated by a sketch-based estimate of drift. We claim it matches the accuracy of full online GMsFEM. We also claim that, once offline data generation is counted, its end-to-end cost is lower than that of learned basis predictors, and that it keeps this advantage for any number of simulations below a break-even count we will measure.

The mechanism is simple enough to state in one equation. Let $V_\omega$ be the current orthonormal local basis on coarse neighborhood $\omega$. We draw $r$ random boundary conditions on an oversampled region $\omega^+$ and solve the local problems with the current permeability $\kappa(u^m)$, where $u^m$ is the pressure head at Picard iterate $m$. Collecting the restricted solutions as columns of $Y_\omega$, we compute

$$ \eta_\omega = \frac{\| (I - V_\omega V_\omega^{\top}) Y_\omega \|_F}{\| Y_\omega \|_F}. $$

This quantity estimates the fraction of the current local solution range that the old basis misses, with $r$ controlling the variance of the estimate. If $\eta_\omega$ is below a tolerance tied to the current Picard residual, the block keeps its basis. Otherwise we orthogonalize the residual columns, append them to $V_\omega$, and solve the local spectral problem only on this small augmented space to re-truncate. We then reuse the probes, so the drift test and the correction cost the same $r$ local solves.

Relation to Prior Work

Two papers motivate the approach by showing that random probing captures local solution spaces. Randomized Oversampling for Generalized Multiscale Finite Element Methods imposes random boundary conditions on oversampled regions to sketch the snapshot space offline for linear high-contrast problems. It reports errors "very similar" to the full snapshot method using 13.46% of the snapshots. Random Sampling and Efficient Algorithms for Multiscale PDEs ties this to fast decay of the Kolmogorov N-width, which measures how well the best $k$-dimensional subspace can approximate the solution set. It shows that local ranks are independent of the oscillation scale. Both papers apply probing once, to a fixed linear operator. We apply it repeatedly, to a sequence of slowly changing nonlinear operators, and we reuse the previous basis instead of starting from scratch.

Manifold Learning and Nonlinear Homogenization shows that nonlinear local solution sets are low-dimensional manifolds. It exploits them through an offline dictionary with nearest-neighbor tangent-space interpolation inside Schwarz iterations. That offline dictionary needs dense sampling of boundary data. We avoid building a dictionary by probing only the local linearization actually visited by the Picard iteration, which is the tangent space that paper approximates from neighbors. We also stay inside a Galerkin coarse solve.

The direct competitors are the learned predictors. Prediction of discretization of online GMsFEM using deep learning for Richards equation trains feedforward networks on $5000 \times 81$ pairs per neighborhood to predict online bases. It reports 0.023 s per predicted basis versus 0.425744 s for standard GMsFEM, a roughly 2× total speedup, and errors often below 8% in the time-dependent case. That paper also constrains the design space: its predictions become unreliable with fewer than four offline modes.

Locally Subspace-Informed Neural Operators for Efficient Multiscale PDE Solving predicts bases with a neural operator trained on a subspace-alignment loss. It reports errors of 1–3%, a 60–100× speedup in basis generation, and 200–400 training samples. It was tested on the steady-state Richards equation, not the transient case. A Randomized GMsFEM with Data-Driven Predictors for Parametric Flow Problems in Multiscale Heterogeneous Media regresses POD-compressed bases on low-dimensional parameters. It reports a 5–8× online speedup (0.133 s vs 0.882 s) but has trouble with energy error at high contrast.

All three amortize an offline training cost over many simulations and assume the test permeability looks like the training permeability. Our method makes neither assumption. It costs more per online update than a network forward pass, so the honest question is where the break-even lies. Answering that question is the central experiment.

Research Program

We will build the tracker on a standard continuous-Galerkin GMsFEM for the Richards equation with Haverkamp conductivity. This matches the setting of Prediction of numerical homogenization using deep learning for the Richards equation and its online-GMsFEM successor, so their numbers are comparable.

The analysis has three parts. The first bounds the change in the local solution operator between Picard iterates in terms of the change in $\kappa(u)$ on $\omega^+$. This shows that the drift $\eta_\omega$ shrinks as Picard converges, which is why most blocks should stop updating after the first few iterations. The second combines standard randomized norm-estimation arguments with the spectral decay results cited above to give a probabilistic bound on the error of the gated basis in terms of $r$ and the tolerance. The third derives an inexact-Picard rule that sets the tolerance proportional to the nonlinear residual. With this rule, basis error never dominates late-iteration error, and effort is not wasted early.

Beyond the core Picard case, we will extend tracking across time steps in the transient problem, warm-starting each time step from the converged basis of the previous one. Wetting fronts move through only a few blocks per step, so the gate should concentrate work near the front. We will instrument every run to log per-block $\eta_\omega$, update counts, and total local fine solves. This makes the method's cost fully auditable against the baselines.

Baselines

The naive reference is frozen-basis GMsFEM. Bases are computed once from the initial or a representative permeability and never updated, and only the coarse system sees the nonlinearity. It costs nothing online, and if it is accurate enough, the whole problem of online updates does not matter. We run it with the same number of modes per block as our method, and with twice as many.

The accuracy reference is full online GMsFEM. At every Picard iteration it rebuilds snapshot spaces and solves local spectral problems, on the same grid, contrast, and tolerance. We must match its $L^2$ and $H^1$ errors to within a stated margin, which we set at one percentage point, while using far fewer local solves.

The strongest existing competitor for cost is the deep-network online-basis predictor of Prediction of discretization of online GMsFEM using deep learning for Richards equation. It reports relative $L^2$/$H^1$ errors "often below 8%" for the time-dependent problem, a total runtime reduction of about 2×, and a per-basis time of 0.023 s. A second strong competitor is GMsFEM-NO from Locally Subspace-Informed Neural Operators for Efficient Multiscale PDE Solving, which reports 1–3% error relative to ground-truth GMsFEM with 200–400 training samples. Both will be retrained by us on our exact Karhunen-Loève permeability distribution, using their published training-set sizes. They get the same hyperparameter search budget in GPU-hours that we give to tuning $r$ and the tolerance. They are charged for data generation and training in the end-to-end cost.

Beating them means one of two things. The first is lower error at equal end-to-end wall-clock for any number of simulations up to a reported break-even count. The second is clear accuracy advantages when the test permeability is shifted away from the training distribution, for example with a different correlation length or contrast. On in-distribution, many-query workloads, we expect the learned predictors to win eventually, and we will report exactly when.

Two ablations isolate the key ingredients. Cold-start randomized probing redraws a fresh randomized basis every iteration, with no warm start and no gate; it isolates the value of tracking. Gated full recomputation uses our drift indicator but rebuilds flagged blocks with full snapshot GMsFEM; it isolates the value of randomized correction versus the value of simply skipping blocks.

Why not just…?

Why not just freeze the offline basis and let the coarse solve handle the nonlinearity? This is a real threat when the conductivity varies mildly. If the frozen-basis baseline stays within a point of full online GMsFEM on our benchmarks, the problem we target is small and we will say so. The Spiridonov et al. study argues otherwise, since it exists precisely because online updates were needed for accuracy. Our drift logs will show directly whether and where $\eta_\omega$ is large under a frozen basis, which settles the question per regime.

Why not just train a network to predict the updated bases? When the same permeability distribution is simulated thousands of times, a network forward pass at 0.023 s is hard to beat. But the reported training data of $5000 \times 81$ fine solves per neighborhood is a fixed cost that our method never pays. The learned models also give no warning when the input permeability leaves the training distribution. Our break-even and distribution-shift experiments are designed to map where each approach wins, not to claim universal superiority.

Why not just recompute bases only where permeability changed a lot, using a cheap heuristic like the change in $\kappa$? A heuristic based on permeability change measures the input, not the local solution space. High-contrast channels can amplify small permeability changes into large basis changes, or wash large changes out. The gated-full-recomputation ablation, run with a heuristic based on the change in $\kappa$ in place of $\eta_\omega$, tests exactly this. If the heuristic matches our indicator, the randomized drift test is unnecessary, and we would keep only the warm-started correction.

Proposed Experiments

The benchmark is the Karhunen-Loève stochastic-permeability Richards setup used in the Stepanov–Spiridonov–Mai papers, in steady and time-dependent form, on 2D grids. We then add the high-contrast channel-and-inclusion fields with contrast $10^4$ used in Randomized Oversampling for Generalized Multiscale Finite Element Methods and the parametric GMsFEM study. We run a 3D case at $50^3$, following the grids of GMsFEM-NO. Metrics are relative $L^2$ and $H^1$ errors against the fine-scale Picard solution, total local fine solves, online wall-clock, and end-to-end wall-clock including all offline generation and training.

Three checks decide the outcome. The first is the accuracy-per-solve curve: error versus cumulative local fine solves for full online GMsFEM, cold-start probing, and our tracker. The tracker should reach full-GMsFEM accuracy with a small fraction of the solves, and that fraction should fall as Picard converges. The second is the amortization curve: end-to-end cost against number of simulations for our tracker and the two learned predictors, yielding an explicit break-even count. The third is a distribution-shift test, in which the learned predictors are trained on one correlation length and contrast and evaluated on another. Our method needs no retraining, and the drift indicator should flag the blocks that need work. If the tracker fails the first check, or its break-even count is only a handful of simulations with no shift advantage, the idea should be abandoned in favor of learned predictors.