I'm assuming delta x = delta y = 1 mile and delta z = 1/5 mile.

I did not mention initial and boundary conditions, which are necessary. Intuitively, all they need to believe is that given initial and boundary conditions, and given information about sources of pollution (e.g., location and rate of largest coal-burning power plants), the solution can be computed.

The classic algorithm is Gaussian elimination. The O (n3) complexity does not exploit sparsity in the matrices, which is inexcusable. But even with sparsity taken advantage of, the complexity would be something like O(n7/3).

The news is not all bleak, of course. there is tremendous research activity into algorithms that get the complexity down closer to O(n log n) or even O(n).


CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000