Given $n\times n$ dense real valued matrices $A_1,\ldots, A_L$ let $P_i=A_1\ldots A_i$

For each $P_i$ I'm interested in obtaining the sum of all rows, and the sum of all columns.

Naive approach:

  • takes $O(L n^2)$ time to get $L$ rows sums
  • takes $O(L^2 n^2)$ time to get $L$ column sums

Is there a way to estimate $L$ column sums faster than $O(L^2 n^2)$?

We know that $n>L$.

More precisely, row sum $r_i$ and column sum $c_i$ are defined as follows $$\begin{align} r_i&=(1,\ldots,1) P_i\\ c_i&=P_i \left(\begin{matrix}1\\ \cdots\\1\end{matrix}\right) \end{align} $$

enter image description here

  • $\begingroup$ Why should the computation of the row sums take $O(Ln^2)$ but for the column sums $O(L^2n^2)$? They should take the same time? The $O(Ln^2)$ algorithm should also work for the column sums just by indexing differently? $\endgroup$
    – plshelp
    Jul 14, 2022 at 14:30
  • $\begingroup$ See the hand-drawn diagram with naive approach, row sums reuse work so computing L of them has same cost as computing the last one $\endgroup$ Jul 14, 2022 at 15:08
  • $\begingroup$ Ahh now I get it. $\endgroup$
    – plshelp
    Jul 14, 2022 at 16:34
  • $\begingroup$ @YaroslavBulatov do you have a lower bound on $L$? For example can we assume that $L \ge n^{2/5}$? $\endgroup$
    – Steven
    Jul 14, 2022 at 18:25
  • $\begingroup$ In my application $L$ is generally much smaller than $n$. Question basically comes down to asking if there's some smart way to summarize intermediate work so as to not require $O(L^2)$ passes $\endgroup$ Jul 14, 2022 at 19:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.