Find all local minima in a big 2d array
Scan the entire array to check each cell to see whether it is a local minimum.

There's no algorithm that is asymptotically better; this is optimal to within a constant factor.  (Proof: if there is any 3x3 region that you haven't looked at, it might contain a local minimum.  So any correct algorithm will need to examine at least one cell out of each 3x3 region, i.e., must examine at least 1/9th of the array.)