# Is there a mathematical property which could help "sum up" information from certain matrix areas?

I have a matrix

$$A= \begin{pmatrix} 2 & -1 & 4 \\ -3 & 8 & -5\\ 12 & -7 & 16 \end{pmatrix}$$

and I would like to create the matrix

$$B= \begin{pmatrix} 6 & 5 & 6 \\ 11 & 26 & 15\\ 10 & 21 & 12 \end{pmatrix}$$

where each entry of B is the sum of its surrounding cells in $A$. So the first entry of $B$ is $2-1-3+8=6$. The $3\times 3$ matrix and the summing "radius" are a simplification, the question aims at $m \times n$ matrices along with arbitrary rectangular areas to be measured.

Is there some mathematical property which could help avoid having to implement something along the lines of $$b_{kl}=\sum_{l-a}^{l+b}\sum_{k-c}^{k+d}a_{kl} ~~~\text{given that the entries exist}$$ ? Special case: would things be easier if the entries only consisted of a fixed amount of $0$ and $1$?

• You are going to have to do a lot of adding up however you approach it. If $m\times n$ is large and adjacent rectangles have substantial overlap you could take advantage of that (by just calculating the difference). Jun 12, 2016 at 19:17
• Why? Programming what? Jun 12, 2016 at 21:04
• @WillJagy Minesweeper and possible generalizations. Jun 12, 2016 at 22:03

Your example is essentially a convolution of $2$-dim array of data using a $3 \times 3$ kernel.
In the case where the kernel is not too big, rectangular and binary ( i.e weight $1$ if inside rectangle, $0$ otherwise), one can use the trick of sum table to compute the sum.
Given any array of data $a_{xy}$, define $$\Delta(x_0,y_0;x_1,y_1) = \sum_{x = x_0}^{x_1} \sum_{y = y_0}^{y_1} a_{xy} \quad\text{ and }\quad \Delta_0(x,y) = \Delta(0,0;x,y)$$ These functions satisfy: \begin{align} \Delta(x_0,y_0;x_1,y_1) &= \Delta_0(x_1,y_1) - \Delta_0(x_0-1,y_1) - \Delta_0(x_1,y_0-1) + \Delta_0(x_0-1,y_0-1)\\ \Delta_0(x_0,y_0) &= \Delta_0(x_0,y_0-1) + \sum_{x=0}^{x_0} a_{xy_0} \end{align} Let's say you have an $N_1 \times N_2$ array of data and you want to convolute it with a $M_1 \times M_2$ rectangular binary kernel. You can build the sum table $\Delta_0$ by scanning along the rows, storing the most recent seen $M_2+1$ rows of $\Delta_0$ and compute the $\Delta$ using row sums from current row and the previous $M_2+1$-th row. In this way, you can compute all the $\Delta$ sums in $O(N_1 \times N_2)$ steps using $O(N_1 \times M_2)$ working storage.