Large difference in computation time of expv from 4*4 matrix to 3*3 matrix

General Usage
, , ,
1

Hi Guys,

I tried to profile the performance of ExponentialUtilities on static array as matrix. I found there is a big jump from 33 matrix to 44 matrix. May I know why? Here is the script I used for the testing:

using ExponentialUtilities
using BenchmarkTools
using StaticArrays

t = 1e-3
# check for A from 2*2 to 10*10 case
for n in 2:10
    An = rand(n, n)
    Asn = SMatrix{n, n}(An)
    vn = rand(n)
    vsn = SVector{n}(vn)
    println("n = $n")
    @btime expv($t, $An, $vn)
    @btime expv($t, $Asn, $vsn)
    @btime exp($t*$Asn)*$vsn
    println("===================================")
end

results are

n = 2
  865.206 ns (27 allocations: 1.39 KiB)
  13.360 ns (0 allocations: 0 bytes)
  13.346 ns (0 allocations: 0 bytes)
===================================
n = 3
  1.212 μs (27 allocations: 1.67 KiB)
  29.480 ns (0 allocations: 0 bytes)
  29.565 ns (0 allocations: 0 bytes)
===================================
n = 4
  2.120 μs (27 allocations: 2.22 KiB)
  145.361 ns (0 allocations: 0 bytes)
  135.082 ns (0 allocations: 0 bytes)
===================================
n = 5
  2.477 μs (27 allocations: 2.75 KiB)
  188.325 ns (0 allocations: 0 bytes)
  228.850 ns (0 allocations: 0 bytes)
===================================
n = 6
  3.469 μs (27 allocations: 3.64 KiB)
  203.497 ns (0 allocations: 0 bytes)
  344.448 ns (0 allocations: 0 bytes)
===================================
n = 7
  5.000 μs (27 allocations: 4.55 KiB)
  270.764 ns (0 allocations: 0 bytes)
  533.116 ns (0 allocations: 0 bytes)
===================================
n = 8
  4.986 μs (27 allocations: 5.41 KiB)
  298.832 ns (0 allocations: 0 bytes)
  815.551 ns (0 allocations: 0 bytes)
===================================
n = 9
  6.917 μs (27 allocations: 6.53 KiB)
  315.094 ns (0 allocations: 0 bytes)
  1.054 μs (0 allocations: 0 bytes)
===================================
n = 10
  7.875 μs (27 allocations: 8.27 KiB)
  347.028 ns (0 allocations: 0 bytes)
  1.375 μs (0 allocations: 0 bytes)
===================================

You could see there is a big jump from the case of n=2 to n=3. May I ask the reason? because I am using it in my model to calculate the exponential of a 4*4 matrix. I’m thinking reduce the size of the matrix, then I found there is a big difference between the case of 2 and 3…nearly 4-5 bigger… but why?

2

Could just be the conditioning of the matrix.

3

I don’t know a lot about linear algebra but I do know that most things take time O(n^3) (unless you have large matrices which can often use cleverer algorithms). So if you double n then you expect the time to go up by 8x, which appears to roughly hold in your timings.

1 Like
4

The matrix exponential uses a polyalgorithm that switches methods based on various things. e.g. expv for StaticArrays switches to a different method for n \times n matrices when n > 5. For n = 3 and n = 4, it looks like it just calls this exp method from StaticArrays, but even that method switches algorithms depending on the norm of the matrix.

Every time you cross the boundaries of one of these switches, there is going to be a jump in cost (in addition to the general O(n^3) trend).

4 Likes