Is operation count a reliable predictor of performance when comparing two formulations?

Question

I have two formulations to solve a problem (both give dense, complex and symmetric system). They are solved multiple times in a loop. I am trying to predict which is better to use.

The first one builds a coefficient matrix $W$ of size $3n \times 3n$. Through reduction of that system, we get the second formulation: a coefficient matrix $Y$ of size $n \times n$ that needs to do two (well-conditioned) matrix inversions.

In every iteration of the loop, matrices $Z_1$, $Z_2$ and $I_\text{in}$ change, but $A_1$ and $A_2$ are constant.

The first system:

$$ \begin{bmatrix} \mathbf{0} & A_1^T & A_2^T \\ A_1 & -Z_1 & \mathbf{0} \\ A_2 & \mathbf{0} & -Z_2 \\ \end{bmatrix} \cdot \begin{bmatrix} U \\ I_1 \\ I_2 \end{bmatrix} = \begin{bmatrix} I_\text{in} \\ \mathbf{0} \\ \mathbf{0} \end{bmatrix} \\ $$

The second system, useful when only $U$ is of interest:

$$ Y\cdot U = I_\text{in} \\ Y = A_1^T \cdot Z_1^{-1} \cdot A_1 + A_2^T \cdot Z_2^{-1} \cdot A_2 \\ $$

I am using LAPACK to solve those system and was looking at Appendix C of [1] and got the following number of operations needed in each formulation to calculate and solve the system:

$$ OP(W) = 36n^3 + 27n^2 + 59n \\ OP(Y) = \frac{124}{3}n^3 + 17n^2 + \frac{209}{3}n \\ $$

From the number of operations needed, I expected the first formulation ($W$) to be faster, but my benchmark (serial processing) shows that the second formulation ($Y$) is faster.

For $n=250$, I get:

• time $W$: 25.873927 s
• time $Y$: 24.696305 s

For $n=1000$, I get:

• time $W$: 10.535318 min.
• time $Y$: 8.236748 min.

The only thing that changes between the two formulations is how the linear system is assembled. Could it be that filling the the bigger matrix ($W$) has an overhead due to memory movement (related to the way I chose to fill it), or is it that the operation count is not a reliable predictor of performance?

[1] S. Blackford and J. Dongarra, “Installation guide for lapack, revised: version 3.0,” Department of Computer Science, University of Tennessee, LAPACK Working Note 41, 1999. [Online]. Available: http://www.netlib.org/lapack/lawnspdf/lawn41.pdf

Answer 1

No. There a number of aspects of modern computer architecture that make operation counts unreliable as a way to compare the performance of algorithms. These include memory caches, vector instructions, and multiple processor cores.

Two implementations that perform the same number of floating point operations may take very different amounts of time.

Looking at your times for $N=250$ and $N=1000$, one would expect from the operation counts a cubic rate of growth in the run time so the run time with $N=1000$ should be about 64 times as long as with $N=250$. In fact, both versions take only about 20 to 25 times as long at $N=1000$ as with $N=250$ (note the switch from seconds to minutes!) This is likely due to the code making better use of multiple processors and cache memory on the larger problem.