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?
$\begingroup$
$\endgroup$
7
-
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$– RichardOct 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 MaoapoOct 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 BushOct 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$– Brian BorchersOct 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$– helloworld922Oct 23, 2022 at 16:25
|
Show 2 more comments