Let $\phi_{ij}(x, y) = \psi_i(x) \psi_j(y)$ and $1 \le i, j \le n$
Let
$$M_{ij, kl} = \sum_{\alpha, \beta} w_{\alpha} w_{\beta}\phi_{ij}(x_\alpha, x_\beta) \phi_{kl}(x_\alpha, x_\beta)G(x_\alpha, x_\beta)$$
where $G$ is a weight function, $w_1,...,w_n$ are weights and $x_1,...,x_n$ are points.
How can one compute $y = Mu$ in $\mathcal{O}(n^3)$?
We can map the indices of $y$ to a tensor and then we can write the elements of $y$ as follows:
$$y_{i,j} = \sum_{k, l} M_{ij, kl} \ u_{k, l}$$
$$ = \sum_{k, l} [\sum_{\alpha, \beta} w_{\alpha} w_{\beta}\ \psi_{i}(x_\alpha)\ \psi_{j} (x_\beta)\ \psi_k (x_\alpha)\ \psi_{l} (x_\beta) G(x_\alpha, x_\beta)]\ u_{k, l}$$
If there weren't the weight function we could split the sum into the $\alpha$ and $\beta$ part but I don't see how that would help either. Naively we can compute $y$ in $\mathcal{O}(n^4)$, has anyone an idea how we can do it in $\mathcal{O}(n^3)$?
First, exchange order of summation, and sum with respect to $k,l$: $$ a_{\alpha,\beta}:=\sum_{k}\psi_k (x_\alpha)\ \left(\sum_l \psi_{l} (x_\beta)\ u_{k, l}\right), $$ this are two products of $n\times n$ matrices, so $O(n^3)$ operations are needed to compute the entries $a$. Then compute $$ b_{\alpha,\beta}:=w_{\alpha} w_{\beta}G(x_\alpha, x_\beta)a_{\alpha,\beta}, $$ which are $3n^2$ multiplications. Then compute $$ \sum_\alpha \left( \sum_{\beta} b_{\alpha,\beta}\psi_j (x_\beta) \right)\psi_i (x_\alpha) $$ again two matrix multiplications of $O(n^3)$.