W. D. Gropp, D. K. Kaushik, and D. E. Keyes

Computational complexity analysis for numerical algorithms has emphasized floating-point operations. This is a historical accident, caused by the cost of floating point operations relative to other operations in early computers. In current computers, the most costly operations are accesses to memory, particularly in machines with deep memory hierarchies. In this paper, we develop a complexity model based on memory references and instruction counts rather than floating-point operations and show that our model provides a far more accurate estimator of performance on real computers. Because domain decomposition algorithms provide a way to manage memory hierarchies, it is natural to evaluate domain decomposition algorithms in terms of memory references rather than just floating-point operations. We will discuss how our model influences the choice of domain sizes, algorithm, and implementation strategy.