0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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, 2014 at 5:28

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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