everyone, I have a question about computational costs for a algorithm. That is:

I have two vectors $u_n,\ v_n\in \mathbb{C}^N$, a matrix $A\in \mathbb{C}^{N\times N}$ (can be both sparse and dense) and scalar coefficient $\alpha_n$, than I need to compute (run by Matlab):

(1) $y_n = u_n + \alpha_nv_n$ (its computational cost (mainly CPU time) is referred to as $\mathcal{K}$);

(2) matrix-vector product: $z_n = Au_n$ (its computational cost (mainly CPU time) is referred to as $\mathcal{L}$).

So I want to know that we have:

1) $5\mathcal{K} >\mathcal{L}$ ??

2) $5\mathcal{K} <\mathcal{L}$ ??

Are the assumptions of 1)-2) rational ? I want to receive some comments about this problem.

  • 1
    $\begingroup$ In practice, you're more likely to be limited by memory bandwidth than the time that it takes to do the floating point operations for both of theses, since there's no opportunity for cache reuse. Time for the matrix vector product will depend a lot onf the density of the matrix. $\endgroup$ – Brian Borchers Nov 21 '14 at 5:28

Let the average number of sparse entries in a row for a sparse matrix be $N_s$. Then the complexity of the matrix-vector product ($z_n = Au_n$) is approximately $O(NN_s)$.

The complexity of $y_n = u_n + \alpha_nv_n$ is $O(2N)$. For the second to hold true

$5\mathcal{K} <\mathcal{L}$, we need $5(2N)$ < $NN_s$

So if $N_s > 10$, i.e., the second condition holds true.

| cite | improve this answer | |
  • $\begingroup$ thank you for your comments which draw my attention to the implementation of MV product, i.e, at present, we have FFT and Multi-Level Fast Multiple method to accelerate the matrix-vector product. may be $O(N\log N)$ or $O(N)$? $\endgroup$ – Hsien-Ming Ku Nov 20 '14 at 12:57
  • 1
    $\begingroup$ As far as I know, both FFT and FMM methods work for particular structures of matrices and the complexity of these methods does not hold true for all matrix-vector products. $\endgroup$ – gk1 Nov 20 '14 at 13:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.