  For a complete lattice $L$ and a relational structure
$\mathfrak{X}=(X,(R_i)_I)$, we introduce the convolution algebra
$L^{\mathfrak{X}}$. This algebra consists of the lattice $L^X$ equipped with an
additional $n_i$-ary operation $f_i$ for each $n_i+1$-ary relation $R_i$ of
$\mathfrak{X}$. For $\alpha_1,\ldots,\alpha_{n_i}\in L^X$ and $x\in X$ we set
$f_i(\alpha_1,\ldots,\alpha_{n_i})(x)=\bigvee\{\alpha_1(x_1)\wedge\cdots\wedge\alpha_{n_i}(x_{n_i}):(x_1,\ldots,x_{n_i},x)\in
R_i\}$. For the 2-element lattice $2$, $2^\mathfrak{X}$ is the reduct of the
familiar complex algebra $\mathfrak{X}^+$ obtained by removing Boolean
complementation from the signature. It is shown that this construction is
bifunctorial and behaves well with respect to one-one and onto maps and with
respect to products. When $L$ is the reduct of a complete Heyting algebra, the
operations of $L^\mathfrak{X}$ are completely additive in each coordinate and
$L^\mathfrak{X}$ is in the variety generated by $2^\mathfrak{X}$. Extensions to
the construction are made to allow for completely multiplicative operations
defined through meets instead of joins, as well as modifications to allow for
convolutions of relational structures with partial orderings. Several examples
are given.
