# Help me analyze the computational cost of two kinds of operations

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

• 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. – 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.
• 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)$? – Hsien-Ming Ku Nov 20 '14 at 12:57