=Paper= {{Paper |id=Vol-2341/paper-07 |storemode=property |title=Generating of the Coefficient Matrix of the System of Homogeneous Differential Equations |pdfUrl=https://ceur-ws.org/Vol-2341/paper-07.pdf |volume=Vol-2341 |authors=Kirill S. Shardakov,Vladimir P. Bubnov,Alexander N. Pavlov }} ==Generating of the Coefficient Matrix of the System of Homogeneous Differential Equations== https://ceur-ws.org/Vol-2341/paper-07.pdf

Generating of the Coefficient Matrix of the System of
Homogeneous Differential Equations

Kirill S. Shardakov Vladimir P. Bubnov Alexander N. Pavlov
Department of Information Department of Information Laboratory of Information
Systems and Technologies, Systems and Technologies, Technologies in System
Emperor Alexander I St. Emperor Alexander I St. Analysis and Modeling,
Petersburg State Transport Petersburg State Transport St. Petersburg Institute for
University University Informatics and
St. Petersburg, Russia St. Petersburg, Russia Automation of the RAS,
k.shardakov@gmail.com bubnov1950@yandex.ru St. Petersburg, Russia
pavlov62@list.ru

Great practical and theoretical interest are non-
stationary queueing system (nSQS). There are few
works devoted to this topic in comparison with
Abstract works devoted to the stationary regime. Examples
of such works are [Bub11, Bub10, Bub99]. The
In this paper the sequential algorithm for various models are discussed in detail in [Bub99].
generating a matrix of coefficients for a The disadvantage of the work [Bub11, Bub10] is
system of homogeneous differential that they consider only the classical numerical
equations describing a model of a non- method for solving systems of ordinary differential
stationary queueing system is proposed. Its equations (ODE) - the Runge-Kutta method.
comparison with the recursive algorithm is Later in [7–9] a numerical-analytical method is
given. The optimal storage structure of the presented, the speed and accuracy of which, when
list of states for a sequential algorithm is solving an ODE system describing nSQS, are
given. A decrease of the performing time superior to the most common Runge-Kutta method
for the algorithm compared with the for solving this kind of problems. One of the
recursive one was noted due to no need to advantages of this method is the recursive
sort the list of states and matrix of algorithm for generating the matrix of coefficients
coefficients. of an ODE system without deriving the general
equation of the ODE system. But this algorithm
1 Introduction also has significant disadvantages: (1) the output of
the algorithm provides an unordered list of states,
Automated monitoring systems play an important the states in it are in the order of their recursive
role in the life of modern society. Monitoring is a generation; (2) the output of the algorithm provides
continuous process of observing and recording the an array of the desired dimension instead of the
parameters of an object in comparison with the lower triangular matrix; (3) based on the first two
specified criteria. In some industries data is points, it follows the necessity of sorting the list of
collected and accumulated very intensively. The states and the matrix of coefficients to bring them
mathematical basis for simulation of monitoring into a ready for further use. When replacing the
systems is queuing theory. Most authors use models values in the list of states, it is necessary to swap
of theory on the assumption that the task queue is rows and columns for the same state numbers in the
infinite, there is a stationary mode, and the load matrix, and for large matrix sizes, this is a resource-
factor does not exceed unity [Zeg12, Oso13, intensive operation. To eliminate these
Upa16].1 disadvantages, a sequential algorithm for generating
a matrix of coefficients is proposed, this algorithm
Copyright © by the papers’ authors. Copying is using a completely different approach.
permitted for private and academic purposes.
In: B. V. Sokolov, A. D. Khomonenko, A. A.
Bliudov (eds.): Selected Papers of the
Workshop Computer Science and Engineering
in the framework of the 5 th International
Scientific-Methodical Conference "Problems of Russia, 8–9 November, 2018, published at
Mathematical and Natural-Scientific Training http://ceur-ws.org
in Engineering Education", St.-Petersburg,
42
2 Essence of a sequential algorithm the matrix of coefficients as A, the number of the
current state as Num, µ and λ – the intensities of
The essence of the sequential algorithm is to divide arriving and maintenance of the task with the
the list of states into subgroups with the same number Num.
properties and further use these properties. For
example, consider the simplest single-channel 1. If this is not the first state within group:
queueing system (QS) characterized by the number ANum, Num = ANum, Num - µ ;
of tasks i (i=¯(0,N)) in it and the number of tasks j
(j=¯(0,N-i)), that have already been completed, ANum, Num-1 = ANum, Num-1 + l ;
where N is the total number of tasks that can enter
2. If this is not the last state within group:
into the system. The input is sequentially received
N tasks with intensities {λ1, λ2, … , λN}, which ANum , Num = ANum , Num - l ;
depends on the task number, and they are served 3. If this is not the first group:
with intensities{µ1, µ2, … , µN}, which also ANum,Pr ev _ Num = ANum,Pr ev _ Num + µ ,
depends on the task number.
We divide states into groups, in a way that in where Prev_Num is the state number from which
each group with constant j, the value of i will grow you can transit to the state with the Num state
to N-j. Note some important facts: (1) the number number after completed the task, in the state list it
of groups will always be N+1; (2) the length of is always in group j-1 and has a number in its group
each next group will always be 1 less than the i + 1.
current; (3) within one group, states can transit into After processing all states, such algorithm at the
each other sequentially and only with intensity λ; output provides a ready-made lower triangular
(4) the transition with intensity µ can occur only matrix of coefficients that eliminates the need to
from state i of group j to the state of the next group sort it.
j + 1, while the number of the new state inside the The flowchart of the entire algorithm is shown
group will always be i-1, the intensity of such a in Figure 1.
transition will always be µj.
The next step is generating a list of states with 3 Comparative analysis of recursive and
length Ns = (N+1)*(N+2)/2. The list is generated sequential algorithms
by simply iterating j in the outer loop, i in the inner
loop, until i+j <= N. When this threshold is Both algorithms for generating a matrix of
reached, j increases by one. At the output, the coefficients of an ODE system without deriving the
algorithm provides an ordered list of states and does general system equation were implemented in
it in a single loop pass. Python3. All measurements were performed when
An important component is the data structure the algorithms are running on the same device, it
for storing this list. The main list of states contains allows us to consider the obtained values as valid
several groups, each of them is a separate list. for comparison. The performing time of the
Inside the group there are states, each of them is algorithms may differ up or down depending on the
stored as a list containing a state number and a list power of the platform on which the algorithms are
with its description. This storage structure running, but the general trends will remain correct.
simplifies further filling of the matrix of The results of the comparative analysis are
coefficients and makes it possible not to go through presented in the table 1.The flowchart of the entire
the list of states when searching for the desired algorithm is shown in Figure 1.
state, but to immediately go to the right place in the As we can see from Table 1, the number of
list. For example: possible states of the system, and consequently, the
Main list of states [ number of equations in the system of ODE grows
Group [ exponentially from the number of tasks that can
State [ enter the nSQS. A graph of dependence between
State number, number of tasks and number of states is presented
[tasks in the system, in Figure 2.
completed tasks]
]
]
].
The next step is filling of the coefficient matrix.
Under initial conditions, this is a square zero matrix
with dimension Ns. We must sequentially take
states one by one from the list of states and
sequentially apply 3 boundary conditions for each
state, due to it all necessary changes of the matrix Figure 2: Dependence between number of tasks
of coefficients that describe this state occur. Denote and number of states

43
Figure 1: The flowchart of the sequential algorithm

44
Table 1: Comparison of performing time of algorithms

Performing time of Generation without
Performing time of sequential
Tasks States recursive algorithm, sorting (for recursive),
algorithm, seconds
seconds seconds

3 10 0.0027289390564 0.000235080718994 0.000102996826172
5 21 0. 000874042510986 0.000907897949219 0.000251054763794
10 66 0. 000315189361572 0.00605607032776 0.000638008117676
20 231 0. 00100684165955 0.129016876221 0.00578188896179
30 496 0. 00470900535583 0.592235088348 0.0215079784393
40 861 0. 00546598434448 2.48418688774 0.0802609920502
50 1326 0.0105609893799 12.4112920761 0.151191949844
60 1891 0.0128128528595 83.0276899338 0.318285942078
70 2556 0.0225200653076 224.342078924 0.576465129852
80 3321 0.0305080413818 568.904677153 0.847626924515
90 4186 0.0393660068512 1163.46502709 1.33484387398
100 5151 0.105370044708 2274.09017706 1.87042212486

Figure 3 shows a comparison of two parts of the
recursive algorithm: generating a list of states and a
matrix of coefficients and their sorting. As we can
see from Figure 3, with an increase the number of
states, most of the time the recursive algorithm is
busy sorting the results.

Figure 4: Performing time for sequential and
recursive algorithms

Figure 5 shows the execution time of the
sequential algorithm and the execution time of the
recursive algorithm without the time-consuming
sorting step. As you can see, even in this case, the
Figure 3: Performing time for both parts of recursive algorithm is inferior to the sequential
recursive algorithm algorithm in speed.

Figure 4 presents a comparison of the total time
of the recursive and sequential algorithms for
generating the coefficient matrix. The execution
time of the recursive algorithm grows exponentially
with an increase the number of states, from Figure 3
it can be concluded that most of this time is spent to
sorting.

Figure 5: Performing time for sequential algorithm
and recursive algorithm excluding sorting

Figure 6 shows a graph of dependence between
number of states and performing time of sequential

45
algorithm, 100 values are used with the number of [Upa16] S. Upadhyaya (2016). Queueing systems
incoming applications from 1 to 100. with vacation: an overview. International
journal of mathematics in operational
research, vol. 9, issue 2. Рp. 167–213.
[Bub11] V.P. Bubnov, A.D. Khomonenko, A.V.
Tyrva Software reliability model with
coxian distribution of length of intervals
between errors detection and fixing
moments // International Computer
Software and Applications Conference.
2011. Pp. 310-314.

[Bub10] V.P. Bubnov, A.V. Tyrva, A.D.
Khomonenko Model of reliability of the
software with coxian distribution of
length of intervals between the moments
of detection of errors // International
Computer Software and Applications
Figure 6: Dependence between number of states
Conference. 34th Annual IEEE
and performing time of sequential algorithm
International Computer Software and
Applications Conference, COMPSAC
As we can see from Figure 6, the performing
2010. Seoul, 2010. Pp. 238-243.
time of this algorithm has an ordinary linear
dependence on the number of tasks coming into the
[Bub99] V.P. Bubnov, V.I. Safonov Razrabotka
system and the number of states of this system.
dinamicheskih modelej nestacionarnyh
system obsluzhivaniya. [Developing
4 Conclusion dynamic modeling of non-stationary
systems.] / V.P. Bubnov, V.I. Safonov. –
The proposed sequential algorithm has undeniable
Saint-Petersburg, 1999, 65 p.
advantages compared with the recursive algorithm:
the performing time of it is significantly less and
[Bub15] V.P. Bubnov, A.S. Eremin, S.A. Sergeev
has a linear dependence on the number of tasks
Osobennosti programmnoj realizacii
coming into the system, in contrast to the
chislenno analiticheskogo metoda
exponential dependence in the recursive algorithm.
raschyota modelej nes-tacionranyh sistem
A sequential output algorithm provides a sorted list
obsluzhivaniya: Trudy SPIIRAN.
of states and a lower triangular matrix of
[Features of the software implementation
coefficients, which eliminates the need for sorting
of numerical-analytical method of
used in the recursive algorithm.
calculation models non-stationary service
As the system parameters increase, the number
systems: SPIIRAS Proceedings.] / V.P.
of states may increase, in some individual cases, the
Bubnov, A.S. Eremin, S.A. Sergeev.
number of rules and conditions for transitions, but
2015. №1. Pp. 218-232.
the overall complexity remains at the same level. It
is recommended to use a sequential algorithm for
[Bub15] V.P. Bubnov, A.D. Khomonenko, S.A.
implementations of the numerical-analytical
Sergeev Recursive method for generating
method, instead of a recursive algorithm.
the coefficient matrix of the system of
homogeneous differential equations
References describing nonstationary system
maintenance: Proceedings of International
[Zeg12] P.D. Zegzhda, D.P. Zegzhda, A.V.
Conference on Soft Computing and
Nikolskiy (2012). Using graph theory for
Measurements, SCM 2015 18. 2015. Pp.
cloud system security modeling. Lecture
75-77.
Notes in Computer Science (including
subseries Lecture Notes in Artificial
[Ser15] S.A. Sergeev Method for compilation of the
Intelligence and Lecture Notes in
system of homogeneous differential
Bioinformatics). Рp. 309–318.
equations for calculation probability-time
characteristics which describing non
[Oso13] T. Osogami, R. Raymond (2013). Analysis
stationary systems. // Intellectual
of transient queues with semi definite
Technologies on Transport.. 2015. №2.
optimization. Queueing Systems, vol. 73.
Pp. 32-42.
Рp. 195–234.

46
[Wol14] R.W. Wolff, Y.-C. Yao Little’s law when Trudy SPIIRAN – SPIIRAS Proceedings,
the average waiting time is infinite. 2014. vol. 6(37). Pp. 61–71.
Queueing Systems, 2014. vol. 76. Pp. [Feh69] E. Fehlberg Low-order classical Runge—
267–281. Kutta formulas with step size control and
[Sud13] R. Sudhesh, K.V. Vijayashree Stationary their application to some heat transfer
and transient analysis of M/M/1 G- problems. NASA Technical Report 315
queues. Int. J. of Mathematics in (1969), extract published in Computing
Operational Research, 2013. vol. 5. no 2. vol. 6, no. 1–2, 1970. Pp. 61–71.
Pp. 282–299.
[Bub11] V.P. Bubnov Algoritm analiticheskogo
[Sud13] R. Sudhesh, L. Francis Raj Stationary and raschyota veroyatnostej sostoyanij
transient solution of Markovian queues — nestacionarnyh system obsluzhivani-ya:
an alternate approach. Int. J. of Izvestiya Peterburgskogo universiteta
Mathematics in Operational Research, putej soobshcheni-ya. [Algorithm of
2013. vol. 5. no. 3. Pp. 407–421. analytical calculation of non-stationary
state probabilities service systems: News
[Bub14] V.P. Bubnov, A.V. Tyrva, A.S. Eremin [A from the St. Petersburg University of
set of non-stationary queuing system communication.] / V.P. Bubnov. 2011. №
models with phase-type distributions]. 4. 90-97 p.