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

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  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?

 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

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.