expv(A*t)v is slow for A,v sparse (it's fast for v non-sparse)

[volkerkarle]

Some how, as the titel suggest, we find the following problem:

N = 1000
d = 0.1
A_sparse = sprand(N,N,d)
v_sparse = sprand(N,d)
A_dense = Matrix(A_sparse)
v_dense = Vector(v_sparse) 

t = 1e-3

@time "exp(A_dense*t)*v_dense"    Q1 = exp(A_dense*t)*v_dense
@time "expv(t,A_dense,v_dense)"   Q2 = expv(t,A_dense,v_dense)
@time "expv(t,A_sparse,v_dense)"  Q3 = expv(t,A_sparse,v_dense)
@time "expv(t,A_sparse,v_sparse)" Q4 = expv(t,A_sparse,v_sparse);

# check if results are more or less the same
@printf("%.1e\n",norm(Q1 - Q2)/norm(Q1))
@printf("%.1e\n",norm(Q2 - Q3)/norm(Q1))
@printf("%.1e\n",norm(Q3 - Q4)/norm(Q1))

The result of this is for me:

exp(A_dense*t)*v_dense:    0.187399 seconds (32 allocations: 53.429 MiB)
expv(t,A_dense,v_dense):   0.027364 seconds (36 allocations: 301.234 KiB, 71.13% gc time)
expv(t,A_sparse,v_dense):  0.003087 seconds (39 allocations: 309.172 KiB)
expv(t,A_sparse,v_sparse): 4.626984 seconds (100 allocations: 2.593 MiB)
3.8e-16
6.2e-19
1.4e-16

As you see, the last one is pretty slow!

Output of using Pkg; Pkg.status()

Project MyProject v0.5.0
Status `~/Project.toml`
  [d4d017d3] ExponentialUtilities v1.27.0
  [37e2e46d] LinearAlgebra v1.11.0
  [2f01184e] SparseArrays v1.11.0
...

• Output of versioninfo()

Julia Version 1.11.3
Commit d63adeda50d (2025-01-21 19:42 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 4 × Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
  WORD_SIZE: 64
  LLVM: libLLVM-16.0.6 (ORCJIT, skylake)
Threads: 4 default, 0 interactive, 2 GC (on 4 virtual cores)
Environment:
  JULIA_NUM_THREADS = 4

[ChrisRackauckas]

This is probably because sparse * sparse is slow? It needs GraphBLAS integrations.