# Is it possible to compute $A \mathrm{diag}(v_1) A \mathrm{diag}(v_2) A\ldots$ faster?

Is it possible to somehow compute a matrix $$M$$ of the form

$$M = A\ \mathrm{diag}(v_1) A\ \mathrm{diag}(v_2) A\ \mathrm{...}\ A\ \mathrm{diag}(v_n) A$$

where $$A \in \mathbb{R}^{m \times m}$$ (and is diagonalizable) and $$v_i \in \mathbb{R}^m$$ faster than with the naive $$O(nm^{\text{matmul power}})$$ algorithm? Maybe with some specific type of $$A$$ (I can change it to some extent)?

• Is $A$ symmetric? Commented Jul 31 at 22:24
• @BrianBorchers no, and I can't make it so, unfortunately. Commented Jul 31 at 22:30
• Do you need $M$ element by element, or is it enough to just be able to compute the action of $M$ on a vector? Commented Aug 1 at 14:29
• @WolfgangBangerth Hello! Actually, now I only need to compute $Mx$ with a few different $x$ vectors, so yes, action would be sufficient. But then the question is whether is it possible to compute it in less than $O(nm^2)$. Commented Aug 1 at 16:19
• That seems unlikely. You can't beat $O(nm^2)$ if you had different matrices instead of the same $A$ every time, simply because that's how long it would take to read all of the matrix entries. At least for $n\ll m$, I see little hope that you could beat that bound. Commented Aug 1 at 19:57