Karhunen-Loeve approximation of random fields by generalized fast multipole methods

KL approximation of a possibly instationary random field a(omega,x) is an element of L-2(Omega, dP; L-infinity (D)) subject to prescribed meanfield E-a(x) = integral(Omega)a(omega,x) dP(omega) and covariance V-a(x,x') = integral(Omega)(a(omega, x) - E-a(a(omega,x') - E-a(x')) dP(omega) in a polyhedral domain D subset of R-d is analyzed. We show how for stationary covariances V-a(x, x') = g(a)(vertical bar x - x'vertical bar) with g(a)(Z) analytic outside of z = 0, an M-term approximate KL-expansion a(M)(omega, x) of a(omega, x) can be computed in log-linear complexity. The approach applies in arbitrary domains D and for nonseparable covariances C-a. 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 a(M)(x, omega) of a(x, omega) has accuracy O(exp(-bM(1/d))) if g(a) is analytic at z = 0 and accuracy O(M-k/d) if g(a) is C-k at zero. It is obtained in O(MN(logN)(b)) operations where N = O(h(-d)). (c) 2006 Elsevier Inc. All rights reserved.