This seems like it could be one of the most challenging parts of doing parallel computations. In this case, one would need to be an expert in PDEs like this to realize that the Gauss-Seidel method is allowed and that it would allow us to parallelize this better. This has made me think what if we wanted to parallelize the game of life in a similar way? In the case of the game of life, there are even more dependencies. When it comes to the game of life, though, there isn't an approximate numerical method like the Gauss-Seidel method to reduce dependencies. However, one thing we have going for us in the game of life is that it doesn't have all that much data, because the state for each cell only requires one bit. So, we can just have two bits per cell, where one is the previous state and the other is the new state, and then we can update state in parallel without needing really any communication at all.

This may be a practical engineering rule as well. If we cannot find a good way to solve the dependency problem, we may probably think of another algorithm.