Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

Question

$A$ is an array of length $n$
$B$ is an $n\times n$ matrix \

I want to return an array C of size n such that:
$$C_{i} = \sum_{j=1}^{n} \max(0, a_i - b_{ij}) $$

In pseudocode it could be like below

for i = 1 to n:
   C[i] = 0
   for j = 1 to n:
      C[i] += max(0, a[i] - b[i,j])

this runs on O(n^2) but it is possible to lower that.

Answer 1

That's not possible. You have to read in the entire $B$ matrix to determine the correct answer, which fundamentally requires $O(n^2)$ time.

Answer 2

A key observation is that if $i$-problems are completely independent, you need to compute $n$ sums of the form

$$s=\sum_{j=1}^n\max(0,a-b_j).$$

With $a=0$ and all $b_j<0$, we get the even simpler form

$$-s=\sum_{j=1}^nb_j$$ which is a sum of $n$ terms and takes $\Omega(n)$ additions. (If parallelized, this can be lowered to $\Omega(\lg(n))$ using $n$ processors.) In the general case, you need the same amount of comparisons.

---

If you know a priori that only few terms are such that $b_j<a$ and you can efficiently determine which ones, then you can avoid accumulating the zeroes.

---

More interesting question is when $b$ is a sparse matrix. Then, two cases: if

• $a\le0$, just add the terms $\max(0, a_i-b_{ij})$ for all $i$. But if
• $a>0$, add $na_i$ and the terms $\max(-a_i,-b_{ij})$ or $-\min(a, b_{ij})$.

Answer 3

While the worst-case complexity is $O(n^2)$, the following special case might be of interest for some applications of this algorithm:

If:

• $B$ does not contain negative values

and:

• $a_i = 0$

Then $C_i = 0$, with no need to consider the matrix entries $b_{i1}$ to $b_{in}$.

This short circuit may make the algorithm behave linear in practice if $A$ is rather sparse and the condition of $B$ containing no negative numbers holds.