I have a question about how to do a scalar product. So I have $m$ vectors of length $n$ (we will refer to a such vector as $a$). Furthermore I have a matrix $B$ that is $n\times n$ and that does not change at all. I want to calculate the following quantity:
$$a_1(a_1B_{11}+…+a_nB_{1n}) + … + a_n(a_1B_{n1}+…+a_nB_{nn})$$
(There will be $n$ terms, $a_1(a_1B_{11}+…+a_nB_{1n})$ is the first term.)
I would like to know if there is a way I can calculate this in $O(n)$ time. For example if we removed the $a$'s before the parentheses, we would have:
$$(a_1B_{11}+…+a_nB_{1n}) + … + (a_1B_{n1}+…+a_nB_{nn})=a_1(B_{11}+…+B_{n1}) + … + a_n(B_{1n}+…+B_{nn})$$
And we could simply calculate $(B_{11}+…+B_{n1})$ beforehand and then have a vector of these quantities that we could do a scalar product with $a$ then.
Let me know if this does not make sense, then I will be happy to try and elaborate!
Looking forward to your answers!
EDIT: My matrix $B$ is symmetric does that somehow help with what I seek? And thanks so for the swift feedback!
Best Answer
In fact, your problem amounts to evaluate efficiently a quadratic expression (mathematics keyword : "quadratic form"):
$$Q=A^TBA$$
(where $A$ has entries $a_i$) which could, in a certain sense be called a "generalized dot product".
There is no general trick.
But if your matrix has a particular property, you can improve the efficiency. For example if $B$ is symmetric positive definite, you can do - once for all because you say $B$ is fixed - a so-called "Cholesky factorization" $B=C^TC$ where $C$ is upper triangular.
See for that https://blogs.sas.com/content/iml/2019/04/15/efficient-quadratic-form.html
Complexity analysis in the case of Cholesky factorisation $B=C^TC$:
For each new $A$, compute $D=CA$ (an $O(n^2)$ operation), then compute $Q:=\|D\|^2=(CA)^T CA$ which is $O(n)$. Finally, it's still a $O(n^2)$ algorithm, but more efficient than the direct calculation (the number of multiplications and additions is approximately halved).
Edit : I have seen what you wrote about "removal of the $a_i$s in front of the parentheses" but it will never be possible to assume that.