ResolveLoops scales as O(N^3) in large linear circuit models

[Francesco Casella]

The ScalableTestSuite contains several models of electrical distribution systems, which lead to large algebraic loops made of linear equations.

For the largest examples, the execution time of resolveLoops scales as O(N³). For example, DistributionSystemModelica_N_XXX_M_XXX (whose number of equations is proportional to N*M) gives these figures

N	M	Time [s]
56	56	3.34
80	80	35.4
112	112	203.7

Given the sparsity pattern of the equations, which have only O(N) nonzero entries in the A-matrix, I'm not sure what is the theoretical complexity of the underlying algorithm. It may be O(N²), but it is probably not O(N³).

@vwaurich, please make sure that the implementation is efficient and does not introduce O(N) or O(N²) overhead.

If the algorithm has really O(N³) inherent complexity, then I would suggest to introduce an upper limit to the size of the systems which are subject to this type of analysis, as we have for tearing. As a default, I would suggest 5000 equations, which currently means about 1 s of processing time on these systems. Above this limit, the spent time quickly gets prohibitive and probably not worth the effort in most cases.

[Henning Kiel]

Time eater is a call to List.unionEltOnTrue(). See attached screen shot of profiler. This is a run for N=M=56

[Volker Waurich]

I have rewritten the critical part of ResolveLoops.
Results on my machine are:

N=M	time
40	0.244
56	0.516
80	1.702
112	2.538

[Francesco Casella]

Sounds good. I've started a run on Hudson, will close the ticket afterwards.

[Francesco Casella]

Replying to vwaurich:

Results on my machine are:

N=M	time
40	0.244
56	0.516
80	1.702
112	2.538

The results on Hudson are

N=M	time
40	0.250
56	0.340
80	0.876
112	3.172

The step from 80 to 112 (2X size) is 4X, which hints to O(N²), but on the other hand from 56 to 112 (2X size) it is 8 times, which is only slightly superlinear. In any case, we have a drastic reduction in time compared to the previous situation (70X faster on the larger model), so this is no longer the bottleneck in the backend by far and large.