A Galerkin method with two-dimensional Haar basis functions for the computation of the Karhunen–Loève expansion

Abstract

We study the numerical approximation of a homogeneous Fredholm integral equation of second kind associated with the Karhunen–Loève expansion of Gaussian random fields. We develop, validate, and discuss an algorithm based on the Galerkin method with two-dimensional Haar wavelets as basis functions. The shape functions are constructed from the orthogonal decomposition of tensor-product spaces of one-dimensional Haar functions, and a recursive algorithm is employed to compute the matrix of the discrete eigenvalue system without the explicit calculation of integrals, allowing the implementation of a fast and efficient algorithm that provides considerable reduction in CPU time, when compared with classical Galerkin methods. Numerical experiments confirm the convergence rate of the method and assess the approximation error and the sparsity of the eigenvalue system when the wavelet expansion is truncated. We illustrate the numerical solution of a diffusion problem with random input data with the present method. In this problem, accuracy was retained after dropping the coefficients below a threshold value that was numerically determined. A similar method with scaling functions rather than wavelet functions does not need a discrete wavelet transform and leads to eigenvalue systems with better conditioning but lower sparsity.

1 Introduction

A large class of random processes, stationary or non-stationary, can be expressed in terms of deterministic orthogonal functions and uncorrelated random variables through Karhunen–Loève (K–L) expansion (Karhunen 1946; Loève 1955). This representation is obtained from the eigenvalues and eigenfunctions of a homogeneous Fredholm integral equation of the second kind whose kernel is given by the covariance function of the random process. Once these eigenpairs are found, the K–L expansion is constructed, roughly speaking, from a linear combination of the eigenfunctions whose weights are independent and identically distributed random variables. This approach has been pioneered by Ghanem and Spanos (1991) and is widely used for modeling uncertainty in problems of elasticity, heat and mass transfer, fluid mechanics, and acoustics (Azevedo et al. 2012; Motamed et al. 2013; Zhang and Lu 2004).

The numerical solution of the Fredholm integral equation becomes more involving in two-dimensional domains. Several methods have been proposed in literature in this case, such as Nyström/collocation methods (Liang and Lin 2010; Xie and Lin 2009), finite element methods (Frauenfelder et al. 2005; Oliveira and Azevedo 2014), and wavelet Galerkin methods (Babolian et al. 2011; Derili et al. 2012).

The practical use of K–L expansion depends of an accurate and efficient computation of eigenpairs. In this sense, one promising technique that has been explored in the one-dimensional case is the Galerkin method with Haar wavelets using the pyramid algorithm (Mallat 1989) to compute the entries of the discrete eigenvalue problem. This method has been shown to be superior to Galerkin methods with polynomial and trigonometric basis functions (Phoon et al. 2002). In this study, we extend the work carried out in Phoon et al. (2002), Stefanou and Papadrakakis (2007) by constructing a 2D Haar wavelet basis for the computation of the eigenpairs of covariance functions with a two-dimensional domain. Rather than the tensor-product basis employed in Babolian et al. (2011), Derili et al. (2012), we consider the non-standard form (Beylkin et al. 1991, eq. (2.14)) (see also Proppe 2012), which is constructed from the orthogonal decomposition of the tensor-product space. Such a basis is suitable to the pyramid algorithm. Moreover, the non-standard form increases the sparsity of the matrix representation of the kernel (Beylkin et al. 1991, Figs. 2–3 and 9–10). In addition to the detailed extension from 1D to 2D, we compare the Galerkin methods with Haar wavelets and Haar scaling functions (the latter is equivalent to the piecewise-constant finite element method Azevedo and Oliveira 2012; Frauenfelder et al. 2005) in terms of stability and efficiency.

The paper is organized in the following way. In Sect. 2, we introduce the K–L expansion and review the one-dimensional Haar functions and the Galerkin method. In Sect. 3, we construct the two-dimensional Haar wavelet basis and the discrete wavelet transform of two-dimensional covariance kernels. In Sect. 4, we carry out several numerical tests to probe the accuracy and the efficiency of the method: we evaluate the approximation error of the eigenvalues as well as the eigenfunctions (by means of the ensemble variance of K–L expansion Stefanou and Papadrakakis 2007); we investigate the effect of neglecting matrix coefficients below a prescribed threshold value (Stefanou and Papadrakakis 2007) in the approximation error and sparsity of the eigenvalue system; we consider the five-spot problem on stationary and heterogeneous media, in which the approximate eigenpairs are employed in a truncated K–L expansion of the log hydraulic conductivity field; and we contrast the computational cost and numerical conditioning of the bases with Haar wavelets and Haar scaling functions.

The following notations will be employed throughout this work. The index i is used for eigenvalues and eigenfunctions, as in (1); the indices $k$ and $l$ are used for matrices and vectors, as in (10); the index $j$ is used for wavelet scaling and the indices $n$ and $m$ are used for wavelet translations, as in (12); and the index $s$ is used to identify elements of a direct sum, as in (15).

2 Preliminary concepts

Let us first describe the Fredholm eigenvalue problem in a general setting. Let D be a compact subset of $\mathbb {R}^d$, $d=1,2,3$. We consider the Hilbert space $L^2(D)$ of real-valued functions equipped with the usual inner product

$$\begin{aligned} \langle {u},{v} \rangle = \int _D u(\varvec{x})v(\varvec{x})\, \mathrm{d}\varvec{x}. \end{aligned}$$

Let $C:D\times D\rightarrow \mathbb {R}$ be a symmetric and nonnegative-definite covariance kernel, i.e., for any finite subset $\tilde{D}\subset D$ and for any function $u:\tilde{D}\rightarrow \mathbb {R}$,

$$\begin{aligned} \sum _{\varvec{x},\varvec{y}\in \tilde{D}}C(\varvec{x},\varvec{y})u(\varvec{x})u(\varvec{y})\ge 0. \end{aligned}$$

We have that C admits the spectral decomposition

$$\begin{aligned} C(\varvec{x},\varvec{y}) = \sum _{i= 1}^\infty \lambda _{i}u_{i}(\varvec{x})u_{i}(\varvec{y}), \end{aligned}$$

(1)

where the nonnegative, monotonically decreasing eigenvalues $\lambda _{i}$ and the orthonormal eigenfunctions $u_{i}$ ($i\ge 1$) are the solutions of the homogeneous Fredholm integral equation

$$\begin{aligned} \int _{D}C(\varvec{x},\varvec{y})u(\varvec{y})\,\mathrm{d}\varvec{y} = \lambda u(\varvec{x}), \quad \varvec{x} \in D. \end{aligned}$$

(2)

Furthermore, let $Y:D \times \Omega \rightarrow \mathbb {R}$ be a second-order random field with expectation

$$\begin{aligned} E\left[ {Y(\varvec{x};\omega )} \right] = \int _{\Omega }Y(\varvec{x},\omega )\, \mathrm{d}\mu \end{aligned}$$

and two-point covariance

$$\begin{aligned} {C(\varvec{x},\varvec{y}) = E\left[ {(Y(\varvec{x};\omega )-E\left[ {Y(\varvec{x};\omega )} \right] )(Y(\varvec{y};\omega )-E\left[ {Y(\varvec{y};\omega )} \right] )} \right] }, \end{aligned}$$

where $\Omega$ represents the set of outcomes and $\mu$ is a probability measure. If the covariance kernel $C(\varvec{x},\varvec{y})$ satisfies the above assumptions, then Y can be written as

$$\begin{aligned} Y(\varvec{x}; \omega ) = E\left[ {Y(\varvec{x}; \omega )} \right] + \sum _{i= 1}^\infty \sqrt{\lambda _{i}}u_{i}(\varvec{x}) \xi _{i}(\omega ), \end{aligned}$$

in that $\xi _{i}(\omega )$ are independent and identically distributed random variables (Loève 1978). This representation is known as the Karhunen–Loève (K–L) expansion. On the other hand, the truncated K–L expansion is given as

$$\begin{aligned} Y(\varvec{x}; \omega ) \approx Y_{M}(\varvec{x}; \varvec{\xi }(\omega ))= E\left[ {Y(\varvec{x}; \omega )} \right] + \sum _{i= 1}^{M} \sqrt{\lambda _{i}}u_{i}(\varvec{x}) \xi _{i}(\omega ), \end{aligned}$$

(3)

where $M$ is known as the stochastic dimension of the truncated field. Choosing a large value for M demands a higher computational effort to compute and store the eigenfunctions, whereas choosing a small value for M may lead to an inaccurate representation of the random field.

2.1 1D Haar functions

The Haar system of orthonormal functions is built from the scaling function $\phi (t)$ and the mother wavelet $\psi (t)$ defined as

$$\begin{aligned} \phi (t) = {\left\{ \begin{array}{ll} 1 \quad &{} 0 \le t< 1,\\ 0 &{}\text{ otherwise, } \end{array}\right. } \quad \psi (t) = {\left\{ \begin{array}{ll} 1 \quad &{} 0 \le t< 1/2,\\ -1 &{} 1/2 \le t < 1,\\ 0 &{}\text{ otherwise. } \end{array}\right. } \end{aligned}$$

These functions satisfy the refinement equations

$$\begin{aligned} \phi (x) = \phi (2x) + \phi (2x-1), \quad \psi (x) = \phi (2x) -\phi (2x-1). \end{aligned}$$

(4)

From $\phi$ and $\psi$ we define the functions $\phi _{j,n}(x)=2^{j/2}\phi (2^{j}x-n)$ and $\psi _{j,n}(x)=2^{j/2}\psi (2^{j}x-n)$, where the integers $j$ and $n$ denote the scaling and translation parameters, respectively. Using the refinement equations (4), we obtain

$$\begin{aligned} \begin{aligned} \phi _{j,n}(x)&=2^{-1/2}(\phi _{j+1,2n}(x) + \phi _{j+1,2n+1}(x)),\\ \psi _{j,n}(x)&=2^{-1/2}(\phi _{j+1,2n}(x) - \phi _{j+1,2n+1}(x)). \end{aligned} \end{aligned}$$

(5)

The vector spaces $V_j$ spanned by $\{\phi _{j,n}(t)\}_{n\in \mathbb {Z}}$ satisfy

$$\begin{aligned} \cdots \subset V_{-2}\subset V_{-1}\subset V_{0}\subset V_{1}\subset \cdots \subset V_{j}\subset V_{j+1}\subset \ldots , \end{aligned}$$

(6)

constituting a multi-resolution analysis, whereas the vector spaces $W_j$ spanned by $\{\psi _{j,n}(t)\}_{n\in \mathbb {Z}}$ serve as orthogonal complements between consecutive levels $j$ and $j+1$, i.e.,

$$\begin{aligned} V_{j+1} = V_{j} \oplus W_{j},\quad j\in \mathbb {Z}. \end{aligned}$$

(7)

In particular, the following orthogonality relations hold:

$$\begin{aligned} \langle {\phi _{j,n}},{\psi _{j,n}} \rangle = 0, \quad \langle {\phi _{j,n}},{\psi _{j,m}} \rangle =\langle {\psi _{j,n}},{\psi _{j,m}} \rangle = 0 \quad \forall \; n,m\in \mathbb {Z},\; n\ne m. \end{aligned}$$

2.2 Variational formulation and Galerkin approximation

Let us consider the variational formulation of the Fredholm integral equation (2): find $\lambda _{i}\in \mathbb {R}$ and $u_{i}(\varvec{x}) \in L^2(D)$ $(i= 1,2,\ldots )$ such that

$$\begin{aligned} \begin{aligned} a(u_{i},v)&=\lambda _{i}\,\langle {u_{i}},{v} \rangle \quad \forall \, v\in L^2(D),\\ a(u,v)&= \int _{D}\int _{D}C(\varvec{x},\varvec{y})u(\varvec{y})v(\varvec{x})\,\mathrm{d}\varvec{y}\,\mathrm{d}\varvec{x}. \end{aligned} \end{aligned}$$

(8)

Let $\mathcal {W}_h$ be a finite-dimensional subspace of $L^2(D)$ with $\text{ dim }\mathcal {W}_h=N$. The Galerkin approximation to (8) in $\mathcal {W}_h$ consists of finding $\lambda _{i}^h\in \mathbb {R}$ and $u_{i}^h \in \mathcal {W}_h$ $(1\le i\le N)$ such that

$$\begin{aligned} a(u_{i}^h,v_h) = \lambda _{i}^h\,\langle {u_{i}^h},{v_h} \rangle \quad \forall \, v_h \in \mathcal {W}_h. \end{aligned}$$

(9)

Given a basis $\{v_1,\ldots , v_{N}\}\subset L^2(D)$ for $\mathcal {W}_h$, let us write the approximate eigenfunction $u^h_{i}$ as follows:

$$\begin{aligned} u^h_{i}(x) = \sum _{k=1}^{N}u_{k,i}v_{k}(x),\quad 1\le i\le N. \end{aligned}$$

It follows from formulation (9) that $\varvec{u}_{i}=[u_{1,i},\ldots ,u_{N,i}]^T$ satisfies the generalized eigenvalue problem $\varvec{C}\varvec{u}_{i} = \lambda _{i}^h\varvec{W}\varvec{u}_{i}$, where the matrices $\varvec{C}$ and $\varvec{W}$ are defined by the coefficients

$$\begin{aligned} C_{k,l} = a(v_{l},v_{k}),\quad W_{k,l} = \langle {v_{l}},{v_{k}} \rangle ,\quad 1\le k,l\le N. \end{aligned}$$

(10)

If the basis functions $v_1,\ldots , v_{N}$ are orthonormal, the problem reduces to the standard eigenvalue problem $\varvec{C}\varvec{u}_{i} = \lambda _{i}^h\varvec{u}_{i}$.

Given $J>0$, we have from (6) and (7) the relation $V_{J} = V_0\oplus W_0\oplus W_1 \oplus \cdots \oplus W_{J-2} \oplus W_{J-1}$. If we restrict to a bounded domain, then spaces $V_j$ and $W_j$ become finite dimensional. In particular, for $D=[0,1]$ we have

$$\begin{aligned} V_0 = \text{ span }\{\phi _0\},\quad W_j= \text{ span }\{\psi _{j,n}\}_{n=0}^{2^{j}-1}. \end{aligned}$$

This motivates the choices $N=2^{J}$ and $\mathcal {W}_h=V_{J} = \text{ span }\{ v_1, v_2, \ldots , v_{N}\}$, where $v_1(x)=\phi _0(x)$ and $v_{k}(x) = \psi _{j, n}(x)$ for $k>1$, where $k= 2^{j} + n$, with $n= 0, 1, \ldots , 2^{j} - 1$ and $j= 0, 1, \ldots , J-1$. Taking into account that the truncated K–L expansion (3) requires at least M eigenpairs, we select $N\ge M$.

3 Two-dimensional Haar basis

Following Mallat (1989), we consider the 2D multi-resolution analysis $\cdots \subset V_{-1}\subset V_0 \subset V_{1} \subset \cdots$ formed by the tensor-product spaces

$$\begin{aligned} V_{j+1} = V_{j+1}^x \otimes V_{j+1}^y,\quad \left\{ \begin{array}{l} V^x_{j+1} = \text{ span }\{\phi _{j+1,n}(x)\}_{n\in \mathbb {Z}},\\ V^y_{j+1} = \text{ span }\{\phi _{j+1,n}(y)\}_{n\in \mathbb {Z}}, \end{array}\right. \end{aligned}$$

and the orthogonal decompositions of the spaces $V_{j+1}^x$ and $V_{j+1}^y$ given by (7):

$$\begin{aligned} V_{j+1} = V_{j+1}^x \otimes V_{j+1}^y = (V_j^x\oplus W_j^x) \otimes (V_j^y\oplus W_j^y)=V_j\oplus W_j, \end{aligned}$$

(11)

where $W_j$ is defined as

$$\begin{aligned} W_j= (V_j^x\otimes W_j^y)\oplus (W_j^x\otimes V_j^y)\oplus (W_j^x\otimes W_j^y). \end{aligned}$$

Taking into account that

$$\begin{aligned} V_j^x&= \text{ span }\{\phi _{j,n}(x)\}_{n\in \mathbb {Z}}, \quad W_j^x = \text{ span }\{\psi _{j,n}(x)\}_{n\in \mathbb {Z}},\nonumber \\ V_j^y&= \text{ span }\{\phi _{j,m}(y)\}_{m\in \mathbb {Z}},\quad W_j^y = \text{ span }\{\psi _{j,m}(y)\}_{m\in \mathbb {Z}}, \end{aligned}$$

we find

$$\begin{aligned} \left\{ \begin{array}{l} V_j^x\otimes W_j^y = \text{ span }\{\phi _{j,n}(x)\psi _{j,m}(y)\}_{n,m\in \mathbb {Z}},\\ W_j^x\otimes V_j^y = \text{ span }\{\psi _{j,n}(x)\phi _{j,m}(y)\}_{n,m\in \mathbb {Z}},\\ W_j^x\otimes W_j^y = \text{ span }\{\psi _{j,n}(x)\psi _{j,m}(y)\}_{n,m\in \mathbb {Z}}. \end{array}\right. \end{aligned}$$

Consequently, we obtain

$$\begin{aligned} W_{j+1} = \text{ span }\{\psi ^{(1)}_{j,n,m}(x,y),\psi ^{(2)}_{j,n,m}(x,y),\psi ^{(3)}_{j,n,m}(x,y)\}_{n,m\in \mathbb {Z}}, \end{aligned}$$

where

$$\begin{aligned} \left\{ \begin{array}{l} \psi ^{(1)}_{j,n,m}(x,y) = \phi _{j,n}(x)\psi _{j,m}(y),\\ \psi ^{(2)}_{j,n,m}(x,y) = \psi _{j,n}(x)\phi _{j,m}(y),\\ \psi ^{(3)}_{j,n,m}(x,y) = \psi _{j,n}(x)\psi _{j,m}(y).\\ \end{array}\right. \end{aligned}$$

(12)

By successively using (11), we find $V_{J} = V_0\oplus W_0\oplus W_1 \oplus \cdots \oplus W_{J-2} \oplus W_{J-1}$. Note that $V_0 = \text{ span }\{\psi ^{(0)}_{0,n,m}(x,y)\}_{n,m\in \mathbb {Z}}$, with

$$\begin{aligned} \psi ^{(0)}_{j,n,m}(x,y) =\phi _{j,n}(x)\phi _{j,m}(y). \end{aligned}$$

(13)

As in the 1D case, when we restrict ourselves to the domain $D=[0,1]\times [0,1]$, the space $V_{J}$ becomes finite dimensional. We choose

$$\begin{aligned} \mathcal {W}_h=V_{J} = \text{ span }\{ v_1, v_2, \ldots , v_{N}\},\quad N=2^{2J} \end{aligned}$$

(14)

and

$$\begin{aligned} v_1(x,y)= & {} \phi _{0,0}(x)\phi _{0,0}(y),\nonumber \\ v_{k}(x,y)= & {} \psi ^{(s)}_{j,n,m}(x,y), \quad 2\le k\le N, \end{aligned}$$

(15)

where the indices $0\le j\le J-1$, $0\le n,m\le 2^{j}-1$, and $s=1,2,3$ are related to the global index $k$ as follows:

$$\begin{aligned} k=2^{2j} + 3(2^{j}\,m+ n) + s\quad (k>1). \end{aligned}$$

(16)

Figure 1 illustrates the basis functions $v_{k}(x,y)$ for $2\le k\le 4$ and $5\le k\le 7$. These indices correspond to $j=0$ and $j=1$, respectively, when $n=m=0$ and $1\le s\le 3$. Note that the basis functions are ordered in such a way that the functions which share the same support are grouped together.

Fig. 1

Basis functions $v_{k}(x,y)=\psi ^{(s)}_{j,n,m}(x,y)$ for $2\le k\le 7$

From (5), (12), and (13), we find the following refinement equations for the 2D functions:

$$\begin{aligned} \psi ^{(0)}_{j,n,m}(x,y)= & {} \frac{1}{2} \big [\psi _{j+1,2n,2m}^{(0)}(x,y)+\psi _{j+1,2n,2m+1}^{(0)}(x,y)\nonumber \\&+ \psi _{j+1,2n+1,2m}^{(0)}(x,y)+\psi _{j+1,2n+1,2m+1}^{(0)}(x,y) \big ],\end{aligned}$$

(17)

$$\begin{aligned} \psi ^{(1)}_{j,n,m}(x,y)= & {} \frac{1}{2} \big [\psi _{j+1,2n,2m}^{(0)}(x,y)-\psi _{j+1,2n,2m+1}^{(0)}(x,y)\nonumber \\&+ \psi _{j+1,2n+1,2m}^{(0)}(x,y)-\psi _{j+1,2n+1,2m+1}^{(0)}(x,y) \big ],\end{aligned}$$

(18)

$$\begin{aligned} \psi ^{(2)}_{j,n,m}(x,y)= & {} \frac{1}{2} \big [\psi _{j+1,2n,2m}^{(0)}(x,y)+\psi _{j+1,2n,2m+1}^{(0)}(x,y)\nonumber \\&- \psi _{j+1,2n+1,2m}^{(0)}(x,y)-\psi _{j+1,2n+1,2m+1}^{(0)}(x,y) \big ],\end{aligned}$$

(19)

$$\begin{aligned} \psi ^{(3)}_{j,n,m}(x,y)= & {} \frac{1}{2} \big [\psi _{j+1,2n,2m}^{(0)}(x,y)-\psi _{j+1,2n,2m+1}^{(0)}(x,y)\nonumber \\&- \psi _{j+1,2n+1,2m}^{(0)}(x,y)+\psi _{j+1,2n+1,2m+1}^{(0)}(x,y)\big ]. \end{aligned}$$

(20)

3.1 Constructing the discrete eigenvalue system

To compute the entries $C_{k,l}$ defined in (10) of the discrete eigenvalue system, let us recast these entries in tensor form:

$$\begin{aligned} C^{s_{k},j_{k},n_{k},m_{k}}_{s_{l},j_{l},n_{l},m_{l}} = a\left( \psi ^{(s_{l})}_{j_{l},n_{l},m_{l}},\psi ^{(s_{k})}_{j_{k},n_{k},m_{k}}\right) . \end{aligned}$$

(21)

These coefficients are related to $C_{k,l}$ as follows:

$$\begin{aligned} C_{k,l} = \left\{ \begin{array}{ll} C^{0,0,0,0}_{0,0,0,0}, &{} k=l=1, \\ C^{s_{k},j_{k},n_{k},m_{k}}_{0,0,0,0}, &{} 2 \le k\le N, \; l=1, \\ C^{0,0,0,0}_{s_{l},j_{l},n_{l},m_{l}}, &{} k=1, \; 2 \le l\le N, \\ C^{s_{k},j_{k},n_{k},m_{k}}_{s_{l},j_{l},n_{l},m_{l}}, &{} 2 \le k,l\le N. \end{array} \right. \end{aligned}$$

(22)

The first step is to compute $C^{0,J,n_{k},m_{k}}_{0,J,n_{l},m_{l}}$ for $0\le n_{k},m_{k},n_{l},m_{l}<2^{J}$:

$$\begin{aligned} C^{0,J,n_{k},m_{k}}_{0,J,n_{l},m_{l}}= & {} \int _{D}\int _{D}C(x,y,s,t)\psi ^{(0)}_{J,n_{l},m_{l}}(x,y)\psi ^{(0)}_{J,n_{k},m_{k}}(s,t)\,\mathrm{d}{t}\,\mathrm{d}{s}\,\mathrm{d}{y}\,\mathrm{d}x\\= & {} 2^{2J}\int _{D_{l}}\int _{D_{k}}C(x,y,s,t)\,\mathrm{d}{t}\,\mathrm{d}{s}\,\mathrm{d}{y}\,\mathrm{d}x, \end{aligned}$$

where $D_{p}=[n_{p}2^{-J},(n_{p}+1)2^{-J}]\times [m_{p}2^{-J},(m_{p}+1)2^{-J}]$, $p=k,l$. We approximate the integral above by the rectangle rule:

$$\begin{aligned} C^{0,J,n_{k},m_{k}}_{0,J,n_{l},m_{l}} \approx 2^{-2J}C(\overline{x}_{J,n_{l}},\overline{x}_{J,m_{l}},\overline{x}_{J,n_{k}},\overline{x}_{J,m_{k}}),\quad \overline{x}_{J,p} = 2^{-J}\left( p+\frac{1}{2}\right) . \end{aligned}$$

(23)

Recalling that $V_0 = \text{ span }\{\psi ^{(0)}_{0,n,m}(x,y)\}_{n,m\in \mathbb {Z}}$, we have that the entries in (23) define the discrete eigenvalue system $\varvec{C}\varvec{u}_{i} = \lambda _{i}^h\varvec{u}_{i}$ corresponding to the Galerkin method with the space $\mathcal {W}_h = V_0$. In the following we describe a pyramid algorithm to recover the remaining coefficients without further numerical integration.

We start using the refinement equations (17)–(20) and the bilinearity of $a(\cdot ,\cdot )$ to compute, for each $0\le n_{l},m_{l}<2^{J}$, the coefficients $C^{s_{k},j_{k},n_{k},m_{k}}_{0,J,n_{l},m_{l}}$ for $0\le n_{k},m_{k}<2^{j_{k}}$, $0\le s_{k}\le 3$, and $j_{k}=J-1,\ldots ,0$. For instance, we have from (17 18 19) that

$$\begin{aligned} C^{0,J-1,n_{k},m_{k}}_{0,J,n_{l},m_{l}}= & {} \frac{1}{2}\big [ a(\psi ^{(0)}_{j_{l},n_{l},m_{l}},\psi _{J,2n_{k},2m_{k}}^{(0)}) + a(\psi ^{(0)}_{j_{l},n_{l},m_{l}},\psi _{J,2n_{k},2m_{k}+1}^{(0)}) \\&+ a(\psi ^{(0)}_{j_{l},n_{l},m_{l}},\psi _{J,2n_{k}+1,2m_{k}}^{(0)})+ a(\psi ^{(0)}_{j_{l},n_{l},m_{l}},\psi _{J,2n_{k}+1,2m_{k}+1}^{(0)})\big ]\\= & {} \frac{1}{2}\big [ C^{0,J,2n_{k},2m_{k}}_{0,J,n_{l},m_{l}} + C^{0,J,2n_{k},2m_{k}+1}_{0,J,n_{l},m_{l}} + C^{0,J,2n_{k}+1,2m_{k}}_{0,J,n_{l},m_{l}} \\&+ C^{0,J,2n_{k}+1,2m_{k}+1}_{0,J,n_{l},m_{l}} \big ]. \end{aligned}$$

Afterwards, we let $j_{l}$ vary from $J-1$ to 0 following the same procedure. Altogether, we have the following algorithm:

As pointed out in Beylkin et al. (1991), the complexity of this algorithm is $\mathcal {O}(N^2)$, $N=2^{2J}$. Once we obtained the coefficients $C_{k,l}$ in (22), we determine the eigenvalues $\lambda _{i}^h$ and eigenvectors $c_l^{(i)}$ in (9).

Remark 1

For implementation purposes, the coefficients in (21) can be written as matrices with the aid of global indices similarly to (16):

$$\begin{aligned} C^{0,J, n_{k},m_{k}}_{0,J,n_{l},m_{l}}= & {} \tilde{A}_{2^{J}m_{k}+n_{k}+1,2^{J}m_{l}+n_{l}+1}\\ C^{0, j_{k},n_{k},m_{k}}_{0,j_{l},n_{l},m_{l}}= & {} \tilde{B}_{(2^{2j_{k}}-1)/3+2^{j_{k}}m_{k}+n_{k}+1,(2^{2j_{l}}-1)/3+2^{j_{l}}m_{l}+n_{l}+1}\\ C^{s_{k},j_{k},n_{k},m_{k}}_{0,j_{l},n_{l},m_{l}}= & {} \tilde{C}_{2^{2j_{k}} + 3(2^{j_{k}}\,m_{k} + n_{k}) + s_{k},(2^{2j_{l}}-1)/3+2^{j_{l}}m_{l}+n_{l}+1}\\ C^{0,j_{k},n_{k},m_{k}}_{s_{l},j_{l},n_{l},m_{l}}= & {} \tilde{D}_{(2^{2j_{k}}-1)/3+2^{j_{k}}m_{k}+n_{k}+1,2^{2j_{l}} + 3(2^{j_{l}}\,m_{l} + n_{l}) + s_{l}}\\ C^{s_{k},j_{k},n_{k},m_{k}}_{s_{l},j_{l},n_{l},m_{l}}= & {} \tilde{E}_{2^{2j_{k}} + 3(2^{j_{k}}\,m_{k} + n_{k}) + s_{k},2^{2j_{l}} + 3(2^{j_{l}}\,m_{l} + n_{l}) + s_{l}}. \end{aligned}$$

Remark 2

Let us compare the computational effort of the above algorithm with the standard finite element method of degree p for (8). If we employed a mesh with $h\times h$ square elements $\Omega _e$, $h=2^{-J}$, we would have a total of $N=2^{2J}$ elements. Let us denote the i-th global shape function as $N_i(\varvec{x})$. The components of the system matrix $\varvec{C}$ in (10) may be computed as follows:

$$\begin{aligned} C_{kl}= & {} \sum _{e,e'=1}^{N}\int _{\Omega _e}\int _{\Omega _{e'}}C(\varvec{x},\varvec{y})N_{l}(\varvec{y})N_{k}(\varvec{x})\,\mathrm{d}\varvec{y}\,\mathrm{d}\varvec{x}\\= & {} \sum _{e,e'=1}^{N}\int _{\hat{\Omega }}\int _{\hat{\Omega }}C(\varvec{x}(\varvec{\xi }),\varvec{y}(\varvec{\xi }'))N_{l}(\varvec{y}(\varvec{\xi }'))N_{k}(\varvec{x}(\varvec{\xi }))J_{e}(\varvec{\xi })J_{e'}(\varvec{\xi '})\,\mathrm{d}\varvec{\xi }'\,\mathrm{d}\varvec{\xi }\\\approx & {} \sum _{e,e'=1}^{N}\sum _{j,j'=1}^{n_\mathrm{int}^2}w_jw_{j'}C(\varvec{x}(\varvec{\xi }_j),\varvec{y}(\varvec{\xi }_{j'}))N_{l}(\varvec{y}(\varvec{\xi }_{j'}))N_{k}(\varvec{x}(\varvec{\xi }_j))J_{e}(\varvec{\xi }_j)J_{e'}(\varvec{\xi _{j'}}),\\ \end{aligned}$$

where $J_e(\varvec{\xi })$ is the Jacobian determinant of the transformation from element $\Omega ^e$ to the reference element $\hat{\Omega }=[-1,1]\times [-1,1]$, $n_\mathrm{int}$ is the number of integration points in each spatial direction, and $\{\varvec{\xi }_j,w_j\}$ are the integration points and weights of the $n_\mathrm{int}\times n_\mathrm{int}$ product Gaussian quadrature in $\hat{\Omega }$.

In the assembly step of a standard finite element algorithm, we compute, for $k,l=1,\ldots ,(p+1)^2$, the elemental contributions

$$\begin{aligned} C_{kl}^{e,e'}= & {} \sum _{j,j'=1}^{n_\mathrm{int}^2}C_{kl}^{e,e'}(j,j'), \\ C_{kl}^{e,e'}(j,j')= & {} w_jw_{j'}C(\varvec{x}(\varvec{\xi }_j),\varvec{y}(\varvec{\xi }_{j'}))\hat{N}_{l}(\varvec{\xi }_{j'})\hat{N}_{k}(\varvec{\xi }_j)J_e(\varvec{\xi }_j)J_{e'}(\varvec{\xi _{j'}}), \end{aligned}$$

where $\hat{N}_{i}(\varvec{\xi })$ is the i-th local shape function in the reference element $\hat{\Omega }$. Note that the number of terms in the form $C_{kl}^{e,e'}(j,j')$ is $n_\mathrm{int}^4(p+1)^4N^2$. Although this procedure is also $\mathcal {O}(N^2)$, the dependence on $n_\mathrm{int}$ and on p renders its computational cost prohibitive, as illustrated in Table 1.

Table 1 CPU time (s) required to build matrix $\varvec{C}$ of eigenvalue system $\varvec{C}\varvec{u}_{i} = \lambda _{i}^h\varvec{W}\varvec{u}_{i}$ for the Galerkin method with Haar wavelets (Haar) and the standard finite element method (FEM) of degree $p=1$. We considered the exponential covariance function (24)

4 Numerical experiments

Let us proceed with the numerical validation of the proposed algorithm. The numerical experiments were carried out in a dual-core notebook with 8 Gb RAM and a 2.30 GHz Intel Core i5 processor. We consider the domain $D = [0,1]\times [0,1]$ and the exponential covariance function

$$\begin{aligned} C(\varvec{x}, \varvec{y}) = C(x_1,x_2; y_1, y_2) = \sigma ^2\exp \left( -\frac{|x_1-y_1|}{\eta } -\frac{|x_2-y_2|}{\eta }\right) , \end{aligned}$$

(24)

where the parameters $\eta$ and $\sigma ^2$ are the correlation scale and variance, respectively. The eigenvalues and eigenfunctions of this covariance function are, respectively, $\lambda _{i} = \lambda _{i_1}^{1\mathrm{D}}\lambda _{i_2}^{1\mathrm{D}}$ and $u_{i}(x_1,x_2) = u_{i_1}^{1\mathrm{D}}(x)u_{i_2}^{1\mathrm{D}}(x_2)$, where

$$\begin{aligned} \lambda _i^{1\mathrm{D}} = \frac{2\eta \sigma }{\eta ^2\gamma _i^2 + 1},\quad u_i^{1\mathrm{D}}(x) = \frac{\eta \gamma _i \cos (\gamma _ix) + \sin (\gamma _ix)}{\sqrt{(\eta ^2\gamma _i^2 + 1)L/2 + \eta }}. \end{aligned}$$

(25)

Fig. 2

Eigenvalues of the exponential covariance function (24) with variance $\sigma ^2=1$ and correlation length $\eta = 0.1$, 0.4 and 1

Index $i=i(i_1,i_2)$ is set to arrange the eigenvalues $\lambda _{i}$ in decreasing order. Moreover, parameters $\gamma _1,\gamma _2,\ldots$ satisfy $(\eta ^2\gamma ^2 - 1)\sin (\gamma ) = 2\eta \gamma \cos (\gamma )$. Since these eigenpairs are well known (see, e.g., Ghanem and Spanos 1991), the exponential kernel (24) is a common benchmark for Fredholm integral eigenvalue problems (Schwab and Todor 2006; Zhang and Lu 2004), although it is not suitable for representing stationary processes due to its non-differentiability at the origin (Spanos et al. 2007). As in Zhang and Lu (2004) we choose $\sigma =1$ and three different values of the correlation length ($\eta = 0.1,\ 0.4$ and 1). Figure 2 shows the eigenvalues $\lambda _n$, whose decay is faster as the correlation length $\eta$ increases.

The eigenvalue problem (2) with covariance kernel (24) is discretized with the Galerkin scheme (9) with refinement level $J$, i.e., with the finite-dimensional space (14), (15). Eigenvalues $\lambda ^{h}_{i}(J)$ are compared with exact solutions $\lambda _{i}$ in terms of relative error (see Fig. 3),

$$\begin{aligned} e_{J} = \frac{|\lambda _{i} -\lambda _{i}^{h}(J)|}{|\lambda _{i}|}, \end{aligned}$$

for each $\lambda _i$ ($i= 1,$ and 10). The error curves have a decay of order $\mathcal {O}(h^2)$, $h = 2^{-J}$, coinciding with the estimates obtained from Oliveira and Azevedo (2014, p. 50) for two-dimensional, piecewise-constant finite elements with reduced integration. A similar order of convergence has also been observed in the one-dimensional case by Phoon et al. (2002).

It is worth noting that the required computational effort dramatically increases in the two-dimensional case. At the refinement level J, the eigenvalue system has dimensions $N\times N$ ($N=2^{2J}$) and demands $\mathcal {O}(N^2)$ operations to be constructed. As J increases, memory soon becomes an issue, and strategies to render the system matrix sparse (as discussed in Sect. 4.2) become important.

Fig. 3

Relative errors of the 2D Haar approximation of the a first and b tenth eigenvalues of the exponential covariance function (24) with variance $\sigma ^2=1$ and correlation length $\eta = 0.1$, 0.4 and 1

Let us study the eigenfunction error as well. For simplicity, we consider the relative error of the first eigenfunction only (which is associated with an eigenvalue of multiplicity one). Following Spence (1978, 1979), we consider the infinity norm. Figure 4 shows a monotone decreasing of the error for all correlation lengths. The convergence rate was again $\mathcal {O}(h^2)$, $h = 2^{-J}$. Such a result is consistent with the experiments reported in Spence (1978, 1979) for Nyström method with the trapezoidal rule.

Fig. 4

Relative error of the 2D Haar approximation of the first eigenfunction of the exponential covariance function (24) with variance $\sigma ^2=1$ and correlation length $\eta = 0.1$, 0.4 and 1

4.1 Ensemble variance of K–L expansion

In our next experiment, similarly to the one presented by Stefanou and Papadrakakis (2007), we evaluate the Haar approximation of the ensemble variance of the truncated process $Y_{M}$,

$$\begin{aligned} Var(Y^{h}_{M}(\varvec{x})) = \sum _{i=1}^{M}\lambda _{i}^h(u_{i}^h(\varvec{x}))^2, \end{aligned}$$

(26)

with $M\le N,$ and admitting the variance target $\sigma ^2=1$. In Figs. 5, 6 and 7 we employ the refinement level $J= 5$ and display the ensemble variance profiles along the diagonal and the horizontal directions. The profiles along the vertical direction were identical to the horizontal profiles and are not shown here. As shown in Figs. 6 and 7, the variance of $Y^{h}_{M}$ converges faster to the reference variance in strongly correlated random fields, i.e., the number of terms needed in the K–L expansion to provide the correct variance decreases with the correlation length, consistently with the experiments in the one-dimensional case presented in Stefanou and Papadrakakis (2007). In fact, since eigenvalues decrease faster as the correlation length increases (Fig. 2), the final terms $\lambda _{i}^h(u_{i}^h(\varvec{x}))^2$ in sum (26) become less significant.

Fig. 5

Ensemble variance of K–L expansion as a function of the stochastic dimension $M= 2^{-j}N$ ($1\le j\le 5$ and $N=2^{10}$) for $\eta = 0.1$, along the following lines: a $(x_1 ,x_2 ) = (x,x)$ and b $(x_1 ,x_2 ) = (x,0.5)$

Fig. 6

Ensemble variance of K–L expansion as a function of the stochastic dimension $M= 2^{-j}N$ ($1\le j\le 5$ and $N=2^{10}$) for $\eta = 0.4$, along the following lines: a $(x_1 ,x_2 ) = (x,x)$ and b $(x_1 ,x_2 ) = (x,0.5)$

Fig. 7

Ensemble variance of K–L expansion as a function of the stochastic dimension $M= 2^{-j}N$ ($1\le j\le 5$ and $N=2^{10}$) for $\eta = 1$, along the following lines: a $(x_1 ,x_2 ) = (x,x)$ and b $(x_1 ,x_2 ) = (x,0.5)$

In analogy with Huang et al. (2001, Fig. 8), Fig. 8 compares the numerical ensemble variance $Y^{h}_{M}$ at the origin with the analytical ensemble variance $Y_{M}$, i.e.,

$$\begin{aligned} \mathrm{Var}(Y_{M}(\varvec{x})) = \sum _{i=1}^{M}\lambda _{i}(u_{i}(\varvec{x}))^2. \end{aligned}$$

(27)

It is interesting to note that $\mathrm{Var}(Y^{h}_{M}(\varvec{0}))$ approaches the target variance more rapidly than $\mathrm{Var}(Y_{M}(\varvec{0}))$. We also noted that the eigenvalues obtained by Haar basis are larger than those generated by analytical solution for each stochastic dimension $M$, as also reported in Phoon et al. (2002) for the one-dimensional case.

Fig. 8

Comparison of variance convergence between analytical and numerical truncated K–L expansions on exponential covariance model as a function of the stochastic dimension $M$ considering the following correlations length: a $\eta = 0.1$, b $\eta = 0.4$ and c $\eta = 1$

4.2 Sparsity of the matrix

The advantage of using a basis of wavelet functions rather than scaling functions (i.e., a basis derived from $V_0\otimes W_0\otimes \cdots \otimes W_{J-1}$ instead of $V_{J}$) is the flexibility to reduce the number of parameters in the representation of the covariance without necessarily loosing the fine scale details. Specifically, we can render the matrix $\varvec{C}$ sparse by dropping matrix coefficients below a threshold value $\epsilon$ (Beylkin et al. 1991; Stefanou and Papadrakakis 2007), leading to a truncated matrix $\varvec{C}_{\epsilon }$. We employ $J= 5$, as in the previous experiments and select $M= 2^{10}$.

Let us first investigate how the accuracy of the eigenfunctions is affected by truncation. Figure 9 shows the relative change $r_{\epsilon } = |\lambda _{i}^{h}(J) -\lambda _{i}^{h}(J,\epsilon )|/|\lambda ^{h}_{i}(J)|$ ($J=5$) of the first and tenth eigenvalues of the truncated matrix $\varvec{C}_{\epsilon }$ with respect to the eigenvalues of the full matrix $\varvec{C}$. In particular, the threshold value $\epsilon = 10^{-6}$ provides comparatively good approximations for these eigenvalues. For instance, the relative change of the tenth eigenvalue for $\eta =1$, namely $1.03\times 10^{-4}$, is 0.7% of the relative error $1.4\times 10^{-2}$ shown in Fig. 3b.

Fig. 9

Relative changes caused by truncation at the threshold value $\epsilon$: a $\lambda _1^h$ and b $\lambda _{10}^h$

Figure 10 presents the dependence of the ensemble variance (26) on the threshold value $\epsilon$ when $M= N/2$ $(N=2^{10})$ and $\eta = 0.1$. Again the threshold value $\epsilon =10^{-6}$ provides sufficient accuracy. Similarly to Stefanou and Papadrakakis (2007, Fig. 1), the higher value $\epsilon = 10^{-4}$ leads to numerical instability. Indeed, we observed that the matrix ceases to be positive definite for this threshold value.

Fig. 10

Ensemble variance of K–L expansion as a function of the threshold value $\epsilon$ for $\eta = 0.1$ and $M= 2^9$. Profiles along the following lines: a $(x_1 ,x_2 ) = (x,x)$ and b $(x_1 ,x_2 ) = (x,0.5)$

Now we consider the sparsity of the truncated matrix $\varvec{C}_{\epsilon }$. Figure 11 shows the number of nonzero elements in $\varvec{C}_{\epsilon }$ for bases with scaling functions and wavelets. The sensitivity of the matrix $\varvec{C}$ to the threshold value $\epsilon$ is higher in the wavelet basis, and the matrix of the scaling function basis becomes sparse only from $\epsilon = 10^{-4}$ onwards.

Fig. 11

Number of nonzero elements in the truncated matrix: a wavelet functions b scaling functions. The parameter nz denotes the number of nonzero entries

Figure 12 shows the sparsity pattern for both bases when $\epsilon = 10^{-6}$ and $\eta = 0.1$. In this case, the wavelet basis requires about half the storage of the basis of scaling functions. One can also notice the typical finger pattern for the wavelet basis (Beylkin et al. 1991).

Fig. 12

Sparsity pattern in the truncated matrix: a wavelet functions, b scaling functions

4.3 Example: quarter five-spot problem

We now present a steady-state diffusion problem in a randomly heterogeneous medium with the classical quarter of a five-spot arrangement. The boundary value problem governing this model is stated as:

$$\begin{aligned} \left\{ \begin{array}{ll} \varvec{q}(\varvec{x};\omega ) = -\kappa (\varvec{x};\omega )\nabla p(\varvec{x};\omega ), &{} (\varvec{x};\omega )\in D\times \Omega , \\ \nabla \cdot \varvec{q}(\varvec{x};\omega ) = f(\varvec{x}), &{} (\varvec{x};\omega )\in D\times \Omega ,\\ \varvec{q}(\varvec{x}; \omega )\cdot \varvec{n}(\varvec{x}) = 0, &{} (\varvec{x};\omega )\in \partial D\times \Omega . \end{array} \right. \end{aligned}$$

The log hydraulic conductivity $Y(\varvec{x}; \omega ) = \log (\kappa (\varvec{x}; \omega ))$ is a Gaussian field with mean zero and covariance function of exponential type (24) with variance $\sigma ^2=1$ and correlation length $\eta = 0.1,\ 0.4, 1 [L]$, where [L] is a consistent length unit (Zhang and Lu 2004). The domain $D=[0,L_1]\times [0, L_2]$, with $L_1=L_2=1 [L]$, has no-flow boundaries at the four sides. The source term consists of one injection well at the lower left corner and one pumping of source at the upper right corner, with strength $1 [L^3/T]$ (herein [T] is a consistent time unit) (Fig. 13).

Fig. 13

Quarter of a five-spot arrangement

The reference solution was computed by the Monte Carlo method with $N_r = 20{,}000$ samples generated from a Gaussian sequential simulation (for details see Zhang 2002, p. 190). For each realization, we employed bilinear finite elements in a mesh of $2^{J}\times 2^{J}$ elements, with $J=5$. The statistical moments of reference solution are computed from

$$\begin{aligned} \mu _{p}^\mathrm{ref}(\varvec{x}) \approx \frac{1}{N_r}\sum _{i=1}^{N_r}p^\mathrm{ref}(\varvec{x};\varvec{\xi }^{(i)}),\quad \sigma _{p}^{2,\mathrm{ref}}(\varvec{x}) \approx \frac{1}{N_r}\sum _{i=1}^{N_r}(p^\mathrm{ref}(\varvec{x};\varvec{\xi }^{(i)}) -\mu _{p}^\mathrm{ref}(\varvec{x}))^2. \end{aligned}$$

(28)

Afterwards, we compute the samples $p_{M}(\varvec{x};\varvec{\xi }^{(i)})$, $1\le i\le 5000$, in the case where the log-conductivity is given by the truncated K–L expansion $Y_{M}(\varvec{x};\varvec{\xi }^{(i)})$ in (3), and the eigenpairs of (2) are approximated with the Galerkin method with 2D Haar wavelet basis functions. We evaluate the mean $\mu _{p}(\varvec{x})$ and variance $\sigma _{p}^{2}(\varvec{x})$ of these samples as in (28). It is important to note that the Haar basis allows other methods for quantification of uncertainty, such as the quasi-Monte Carlo and sparse grid collocation methods (Azevedo and Oliveira 2012), but this is not the focus of study in this paper. Once these statistical moments are obtained, we graphically illustrate the quality of the approximation by plotting profiles along the diagonal line considering $M=2^{-5}N,2^{-1}N,\; N=2^{2J}$.

Figures 14, 15 and 16 show the mean and variance of the approximate hydraulic head with correlation lengths $\eta = 0.1,\ 0.4$, and 1[L] respectively. In all cases, the mean exhibits minimum and maximum values at the injection and production well, respectively, and the variance shows a singular peak in vicinity of the plateau away from them. In Fig. 14 we observed a slight discrepancy between stochastic dimensions, specially for $M=2^{-5}N$. This can be due to the correlation length which induces loss of regularity and accuracy of the numerical solution, because of the high variability of the media. However, the mean and variance exhibit good agreement with the reference solution when the correlation length increases (see Figs. 15, 16), except near the wells where strong gradients are observed.

The last experiment in this section consists of repeating the simulation in the case of shortest correlation length ($\eta =0.1 [L]$), but computing the truncated K–L expansion from the sparse covariance matrix associated to the threshold value $\epsilon =10^{-6}$. As expected, the statistical moments of this solution (Fig. 17) are qualitatively similar to the moments that were found with the full covariance matrix (Fig. 14).

Fig. 14

Profiles of statistical moments of the approximate hydraulic head for $M= 2^{-j}N$ ($j=0,1,5$ and $N=2^{10}$) and $\eta = 0.1[L]$ along the diagonal: a mean and b variance

Fig. 15

Profiles of statistical moments of the approximate hydraulic head for $M= 2^{-j}N$ ($j=0,1,5$ and $N=2^{10}$) and $\eta = 0.4[L]$ along the diagonal: a mean and b variance

Fig. 16

Profiles of statistical moments of the approximate hydraulic head for $M= 2^{-j}N$ ($j=0,1,5$ and $N=2^{10}$) and $\eta = 1[L]$ along the diagonal: a mean and b variance

Fig. 17

Profiles of statistical moments of the approximate hydraulic head for $M= 2^{-j}N$ ($j=0,1,5$ and $N=2^{10}$) and $\eta = 0.1[L]$ along the diagonal: a mean and b variance. For the approximation of the K–L expansion, we dropped covariance matrix coefficients below $\epsilon = 10^{-6}$

4.4 CPU time and condition number

We have seen in Sect. 3.1 that the $N\times N$ system matrix for the wavelet basis has an additional cost of $\mathcal {O}(N^2)$ with respect to the system matrix for the basis of scaling functions. On the other hand, Sect. 4.2 pointed out that the wavelet basis provides a sparser system, which not only requires less computer memory, but also is more rapidly processed in iterative solvers (see Beylkin et al. 1991). In this section we evaluate the trade-off between these aspects, taking into account total CPU time and conditioning.

Motivated by the results from the previous sections, we employ the threshold value $\epsilon = 10^{-6}$, which is also recommended elsewhere (Beylkin et al. 1991). In addition to the exponential covariance (24) with correlation length $\eta = 0.1$ and $\eta = 1$, we consider the sinc covariance defined in $[0,1]\times [0,1]$ by

$$\begin{aligned} C(\varvec{x}, \varvec{y}) = C(x_1,x_2; y_1, y_2) =\frac{\sin (2c|x_1-y_1|)}{\pi |x_1-y_1|}\cdot \frac{\sin (2c|x_2-y_2|)}{\pi |x_2-y_2|}, \end{aligned}$$

(29)

with $c=10$ and $c=30$.

Table 2 shows the CPU times (in seconds) $T_{\psi }$ and $T_{\phi }$ for building the matrices and finding the $M=2^{-1}N$ largest eigenpairs with the bases of wavelets and scaling functions, respectively. We employed Matlab’s built-in iterative eigenvalue solver eigs(). The efficiency of the wavelet basis becomes apparent at $J=7$, for which the total CPU time can reduce to nearly half the time spent with the basis of scaling functions. Similar results (not shown herein) were found with the exponential kernel and with the sinc kernel with $c = 30$.

Table 2 CPU time (s) of the Galerkin method with wavelet ($T_{\psi }$) and scaling function ($T_{\psi }$) bases required to generate the eigenpairs of the exponential and sinc covariance kernels

Table 3 Condition number of the eigenvalue system resulting from the Galerkin method with wavelet ($\kappa (\varvec{C}_{\phi })$) and scaling function ($\kappa (\varvec{C}_{\psi })$) bases for the exponential and sinc covariance kernels

In Table 3, we compute the condition numbers relative to the wavelet basis ($\kappa (\varvec{C}_{\psi })$) and scale basis ($\kappa (\varvec{C}_{\phi })$). As noted in Stefanou et al. (2005) for both separable and Gaussian exponential covariances, matrix truncation deteriorates the conditioning of the eigensystem. An increase in the threshold value $\epsilon$ makes the conditioning worse, as seen in Sect. 4.2. We further notice that the basis with scaling functions is generally robust under truncation.

5 Conclusions

In this paper, we studied a Galerkin method with bidimensional Haar wavelets to obtain approximate solutions to the truncated K–L expansion.

Many aspects related to the wavelet Galerkin approximation in the one-dimensional case (Stefanou and Papadrakakis 2007; Phoon et al. 2002) have also been observed in two dimensions, specially the strong dependence of the errors on the correlation length. However, the variation of the ensemble variance of the truncated K–L expansion cannot be completely described only in one space dimension (see Fig. 10).

From our numerical experiments with the truncated covariance matrix, we noticed that dropping the coefficients below the threshold value $\epsilon =10^{-6}$ preserved the accuracy of the method, indicating that this threshold value is sufficient to obtain statistical moments with sufficient accuracy.

Our experiments on CPU time and conditioning suggest that the basis with Haar wavelets becomes more efficient, but less stable than the basis with Haar scaling functions for higher refinement levels ($J\ge 6$). Taking into account that bases with scaling functions are also more flexible to handle general meshes and non-rectangular domains (Azevedo and Oliveira 2012; Frauenfelder et al. 2005), scaling functions seem to be a more appropriate choice for multi-dimensional integral equations than wavelet functions.