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


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?

  • $\begingroup$ 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? $\endgroup$ – Discrete lizard Jan 17 '18 at 17:25
  • $\begingroup$ 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? $\endgroup$ – D.W. Jan 17 '18 at 17:41
  • $\begingroup$ @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. $\endgroup$ – FooBar Jan 18 '18 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.