# Most efficient way to shift arrays

I would like to know what would be the most efficient way to shift numerical 2D arrays along its dimensions as follows:

(A = Partition[Range[9], 3])//TableForm


$$\left( \begin{array}{ccc} 1. & 2. & 3. \\ 4. & 5. & 6. \\ 7. & 8. & 9. \\ \end{array} \right)$$

(AR = PadLeft[A, {3, 4}][[All, ;; -2]]) // TableForm
(AL = PadRight[A, {3, 4}][[All, 2 ;;]]) // TableForm
(AD = PadLeft[A, {4, 3}][[;; -2, All]]) // TableForm
(AU = PadRight[A, {4, 3}][[2 ;;, All]]) // TableForm


\begin{align}AL&=\left( \begin{array}{ccc} 0. & 1. & 2. \\ 0. & 4. & 5. \\ 0. & 7. & 8. \\ \end{array} \right),& AR&=\left( \begin{array}{ccc} 2. & 3. & 0. \\ 5. & 6. & 0. \\ 8. & 9. & 0. \\ \end{array} \right),\\ AD&=\left( \begin{array}{ccc} 0. & 0. & 0.\\ 1. & 2. & 3. \\ 4. & 5. & 6. \\ \end{array} \right),& AU&=\left( \begin{array}{ccc} 4. & 5. & 6. \\ 7. & 8. & 9. \\ 0. & 0. & 0. \\ \end{array} \right). \end{align}

In this post a question of array rotation has been asked. I am asking for the efficient numerical shift. Actually, I need to achieve even a simpler goal of computing the sum

(B = AL + AR + AU + AD) // TableForm


\begin{align}B&=\left( \begin{array}{ccc} 6. & 9. & 8. \\ 13. & 20. & 17. \\ 12. & 21. & 14. \\ \end{array} \right) \end{align}.

In real application, the dimensions are not $$3\times3$$ but $$201\times201$$, and this operation needs to be performed repeatedly. As an answer, I am expecting some super efficient function ArraySpread defined as follows:

ArraySpread[a_?ArrayQ] := Module[{...},
....
]


such that

B=ArraySpread[A]


My current implementation:

ArraySpread[a_?ArrayQ] := Module[{al, ar, au, ad, dim},
dim = Length[a];
ar = PadLeft[a, {dim, dim + 1}][[All, ;; -2]];
al = PadRight[a, {dim, dim + 1}][[All, 2 ;;]];
ad = PadLeft[a, {dim + 1, dim}][[;; -2, All]];
au = PadRight[a, {dim + 1, dim}][[2 ;;, All]];
al + ar + ad + au
]


performs as

an = RandomReal[{0., 1.}, {201, 201}]
RepeatedTiming[ArraySpread[an]]

(*0.036*)


But can one achieve a better performance?

• Some of you outputs show Real arrays, but all the inputs seem to be Integer arrays. Jun 19, 2021 at 13:46
• @MichaelE2 Good catch, in the process of typing I realized that for me only real case is of interest, but I overlooked that some results were obtained with the previous command. I will correct it now. Jun 19, 2021 at 15:13

## 1 Answer

Here's an approach using ArrayPad. It's not a lot faster, but doesn't need the dimension to be explicitly determined:

ArraySpread2[a_] := ArrayPad[a, {{1, -1}, 0}]
+ ArrayPad[a, {{-1, 1}, 0}]
+ ArrayPad[a, {0, {1, -1}}]
+ ArrayPad[a, {0, {-1, 1}}]

an = RandomReal[{0., 1.}, {201, 201}];
RepeatedTiming[ArraySpread[an];]
(* {0.023, Null} *)

RepeatedTiming[ArraySpread2[an];]
(* {0.020, Null} *)


After some tinkering with the parameters, here is another approach using ListConvolve that is more than 10 times faster:

ArraySpread3[a_] := ListConvolve[{{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, a, {2, -2}, 0]

RepeatedTiming[ArraySpread3[an];]
(* {0.0017, Null} *)

ArraySpread[an] == ArraySpread2[an] == ArraySpread3[an]
(* True *)

• Around 10% faster. Not bad! Jun 19, 2021 at 9:16
• @yarchik Now it's 10x faster :) Jun 19, 2021 at 9:22
• Amazing, really amazing! I should not have forgotten the FFT approach. Jun 19, 2021 at 9:25