# Operation count: Solving Ax=b with sparse diagonal matrix

I've seen several tables that list operation counts for matrix-inversion related problems, but none of them actually brought forward the way of computing them.

I'm interested in solving

Ax=b


for x, and k-diagonal sparse matrix A - which is a sparse matrix that has zero elements on all but k many diagonals. On these k diagonals, it can have either zero or non-zero elements.

I'd like to find out the number of operations as a function of N, the length of b, and k, the number of diagonals in A.

Is there an explicit answer? How could I compute it?

• Which operations do you want to count? The number of scalar multiplications and additions? Only one of those? Maybe more? Of what procedure do you want to count the operations? A given algorithm (which?) to solve the equation? Or do you want a lower bound on the number of operations required to solve the equation? – Discrete lizard Jan 17 '18 at 17:25
• What's a DIA sparse matrix? I am not familiar with the DIA acronym. Can you define it in a self-contained way? Is it important? – D.W. Jan 17 '18 at 17:41
• @Discretelizard Ultimately, I want a metric of how solving time increases in k and N. I thought that the number of total operations would be a good approximation to that, but perhaps that was naive. Yes, perhaps a lower bound is a good idea. – FooBar Jan 18 '18 at 7:08