I am trying to compute $\mathbf{X}\mathbf{u}$ for many times in my algorithm, where $\mathbf{X}\in \mathbb{R}^{n\times m}$ and $\mathbf{u} \in \mathbb{R}^{m}$. The problem is that, during the computational process of the algorithm, $\mathbf{X}$ is a constant, however, more and more elements in $\mathbf{X}$ can be changed to zero, which might help us to save computational time. $\mathbf{u}$ is just a variable. This process is kind similar to a process of changing a dense matrix to a band matrix and finally a sparse matrix. But the band matrix is not standard as it might look like a boomerang or something else.
I know that using a sparse matrix to represent the $\mathbf{X}$ can speed up the multiplication, but the advantage only appears when the sparsity is above 90% percent. It is not suitable for me because most of the time my $\mathbf{X}$ is not that sparse, and even when it reached 90% percent sparsity, the speed-up ratio of the Sparse Matrix multiplication in Scipy is not that oblivious.
I use NumPy in python to apply the multiplication $\mathbf{X}\mathbf{u}$, which is really fast. I wonder whether it is possible to be faster as we are sure that more and more elements in $K$ are zeros and unimportant. Can we speed up it by using space to exchange for computational time?

  • 2
    $\begingroup$ How big is your matrix? If it's smallish then sparsity just isn't going to be able to help you much. $\endgroup$
    – Richard
    Oct 23, 2022 at 3:00
  • $\begingroup$ As it is an algorithm, we hope it would be able to deal with large-scale problems. The matrix would have hundreds of dimensions in some real applications. $\endgroup$
    – Xun Maoapo
    Oct 23, 2022 at 7:47
  • 2
    $\begingroup$ Do you mean the order of the matrix is at most a few hundred? If so that's not very big at all for a matrix vector multiply, and simply using BLAS will probably not be a bad solution $\endgroup$
    – Ian Bush
    Oct 23, 2022 at 11:03
  • 4
    $\begingroup$ Before you go down this rabbit hole, you should check whether your algorithm is spending a lot of time on the $Xu$ multiplcations. It could well be that there are other more important hot spots. $\endgroup$ Oct 23, 2022 at 16:20
  • 3
    $\begingroup$ What do you mean by "X is a constant, however more and more elements in X can be changed to zero"? $\endgroup$ Oct 23, 2022 at 16:25


Your Answer

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