Decomposition became much slower for lazy_expm mode

[schillic]

Recent changes made decomposition for MNA5 run much slower. I ran it for at least 30 minutes and finally stopped it.
On March 27, 10 am, the whole analysis (which decomposition is only a part of) took 970 seconds (1D Interval) resp. 1,568 seconds (2D Hyperrectangle).

[schillic]

EDIT
I narrowed it down to this:
LazySets.jl: 976ff4b still works, 7daa8cd does not work anymore (→ #304 is the culprit)
For Reachability.jl one can use e8420e9.
The effect is less visible for the FOM model with lazy_expm option:

[info] - Decomposing X0
[info] elapsed time: 1.079548582 seconds

# vs.

[info] - Decomposing X0
[info] elapsed time: 2.407215414 seconds

[mforets]

Here it works:

compute(:δ => 1e-3, :N => 3, :mode=>"reach", :verbosity => "info", :lazy_expm=>true, :set_type=>Interval, :partition => [[i] for i in 1:10913])
[info] Time discretization...
[info] elapsed time: 342.700746425 seconds
[info] Reachable States Computation...
[info] - Decomposing X0
[info] elapsed time: 707.852182514 seconds
[info] - Computing successors
[info] elapsed time: 2.667469983 seconds
[info] - Total
[info] elapsed time: 712.20336396 seconds
[info] Projection...
[info] elapsed time: 0.360965227 seconds

For the real compute(:δ => 1e-3, :T => 20.0, :mode=>"reach", :verbosity => "info", :lazy_expm=>true, :set_type=>Interval, :partition => [[i] for i in 1:10913]) the cost of discretization and decomposition is the same, no?

The changeset #304 cannot affect decomposition i think because decomposition uses calls to the support vector \sigma directly, first through the generic project, then through overapproximate for intervals. OTOH, the functions get_row(s) and get_column(s)for a SparseMatrixExp are used only in the computation of succesors, in reach_blocks.

(To evaluate the support vector in some direction of a runtime object i used a call like save("X0_mna5.jld", "X0") inside from JLD: in reach. It can be loaded in another session like:

using JLD
julia> X0 = load("X0_mna5.jld", "X0");
julia> v = sparsevec([10], [1.0], 10913);
julia> @time σ(v, X0);
  0.015218 seconds (306 allocations: 7.295 MiB)

For this model it takes around 150ms... 200ms.

[schillic]

I just double-checked the experiment with FOM. Interestingly, the difference is only visible for Hyperrectangle decomposition. For HPolygon with box directions the runtime is the same.

For MNA5 it is so much slower. I added a ProgressMeter to the decomposition and it estimates the runtime at ~35 minutes (with the older revision it says ~9 minutes).

I agree that the PR should not have any effect on the decomposition. What is going on here?

[schillic]

I found out how get_columns influences decomposition:
The discretization by default uses a lazy symmetric interval hull. Thus when we evaluate the support vector in the decomposition, we actually perform the lazy computation.
EDIT:
Here we have EPsi = sih(Phi2Aabs * sih(cont_sys.A * inputs)). Phi2Aabs is the return value of get_columns. In the PR the type has changed from SparseMatrixCSC to a dense Matrix.