Filling a matrix with the sum of conditional values

Question

I have $P$ vectors of size $N$ with elements in $\{0,1\}$. Each vector $v$ has a value $\alpha_v$.

I would like to Fill a square matrix $M$ of size $N\times N$ in the following way:

$$\forall i,j \in \{1,2,...,N\}~ M_{i,j} = \sum_{\text{vectors}~v : v_i v_j =1} \alpha_v$$

Is it possible to fill the matrix $M$ in time complexity better than $O(P\cdot N^2)$?

Assuming that each vector has at most $Q$ elements equal to $1$, is it possible to do better than $O(P\cdot(N+Q^2))$ ?

Answer 1

Let $V$ be the $N\times P$ matrix whose columns are the vectors $v$, and let $D$ be the $P\times P$ diagonal matrix with elements $D_{vv} = \alpha_v$. Then you want to compute $VDV^T$. Computing $U = DV^T$ takes time $NP$, and it remains to compute $VU$. When $P < N^{0.3029}$, for every $\epsilon > 0$ there is an (impractical) algorithm to compute this product in time $O_\epsilon(N^{2+\epsilon})$. See Le Gall, who improved on an earlier result of Coppersmith.