Karhunen–Loève approximation of random fields by generalized fast multipole methods

KL approximation of a possibly instationary random field a(ω, x) ∈ L2(Ω, dP; L∞(D  )) subject to prescribed meanfield Ea(x)=∫Ωa(ω,x)dP(ω) and covariance Va(x,x′)=∫Ω(a(ω,x)-Ea(x))(a(ω,x′)-Ea(x′))dP(ω) in a polyhedral domain D⊂RdD⊂Rd is analyzed. We show how for stationary covariances Va(x, x′) = ga(|x − x′|) with ga(z) analytic outside of z = 0, an M-term approximate KL-expansion aM(ω, x) of a(ω, x) can be computed in log-linear complexity. The approach applies in arbitrary domains D and for nonseparable covariances Ca. It involves Galerkin approximation of the KL eigenvalue problem by discontinuous finite elements of degree p ⩾ 0 on a quasiuniform, possibly unstructured mesh of width h in D, plus a generalized fast multipole accelerated Krylov-Eigensolver. The approximate KL-expansion aM(x, ω) of a(x, ω) has accuracy O(exp(−bM1/d)) if ga is analytic at z = 0 and accuracy O(M−k/d) if ga is Ck at zero. It is obtained in O(MN(log N)b) operations where N = O(h−d).