Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph
The problem of locating sensors on the network to monitor flows has been object of growing interest in the past few years, due to its relevance in the field of traffic management and control. The basis for modeling the processes of estimating flows in generalized multinetwork is a sparse underdetermin...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Belarusian |
| Published: |
Belarusian State University
2018-01-01
|
| Series: | Журнал Белорусского государственного университета: Математика, информатика |
| Subjects: | |
| Online Access: | https://journals.bsu.by/index.php/mathematics/article/view/747 |
| _version_ | 1818064403843514368 |
|---|---|
| author | Ludmila A. Pilipchuk |
| author_facet | Ludmila A. Pilipchuk |
| author_sort | Ludmila A. Pilipchuk |
| collection | DOAJ |
| description | The problem of locating sensors on the network to monitor flows has been object of growing interest in the past few years, due to its relevance in the field of traffic management and control. The basis for modeling the processes of estimating flows in generalized multinetwork is a sparse underdetermined system of linear algebraic equations of a special type. Sensors are located in the nodes of the multinetwork for the given traffic levels on arcs within range covered by the sensors, that would permit traffic on any unobserved flows on arcs to be exactly. The problem being addressed, which is referred to in the literature as the Sensor Location Problem (SLP), is known to be NP-complete. In this paper the effective algorithms are developed to determine the ranks of the matrices of each of the independent subsystems obtained as a result of applying the theory of decomposition. From the equality of the sum of the ranks of the matrices of independent subsystems and the number of unknowns in independent subsystems, the uniqueness conditions for the solution of a special sparse system of linear algebraic equations follow. The results of the research can also be applied to constructing optimal solutions to problems of mathematical programming. |
| first_indexed | 2024-12-10T14:35:27Z |
| format | Article |
| id | doaj.art-2e422f3ebaf6420fbbabf0d884dd43ac |
| institution | Directory Open Access Journal |
| issn | 2520-6508 2617-3956 |
| language | Belarusian |
| last_indexed | 2024-12-10T14:35:27Z |
| publishDate | 2018-01-01 |
| publisher | Belarusian State University |
| record_format | Article |
| series | Журнал Белорусского государственного университета: Математика, информатика |
| spelling | doaj.art-2e422f3ebaf6420fbbabf0d884dd43ac2022-12-22T01:44:50ZbelBelarusian State UniversityЖурнал Белорусского государственного университета: Математика, информатика2520-65082617-39562018-01-0123743747Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraphLudmila A. Pilipchuk0Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, BelarusThe problem of locating sensors on the network to monitor flows has been object of growing interest in the past few years, due to its relevance in the field of traffic management and control. The basis for modeling the processes of estimating flows in generalized multinetwork is a sparse underdetermined system of linear algebraic equations of a special type. Sensors are located in the nodes of the multinetwork for the given traffic levels on arcs within range covered by the sensors, that would permit traffic on any unobserved flows on arcs to be exactly. The problem being addressed, which is referred to in the literature as the Sensor Location Problem (SLP), is known to be NP-complete. In this paper the effective algorithms are developed to determine the ranks of the matrices of each of the independent subsystems obtained as a result of applying the theory of decomposition. From the equality of the sum of the ranks of the matrices of independent subsystems and the number of unknowns in independent subsystems, the uniqueness conditions for the solution of a special sparse system of linear algebraic equations follow. The results of the research can also be applied to constructing optimal solutions to problems of mathematical programming.https://journals.bsu.by/index.php/mathematics/article/view/747multigraphsparse systemrankdecompositionsupportunique solution |
| spellingShingle | Ludmila A. Pilipchuk Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph Журнал Белорусского государственного университета: Математика, информатика multigraph sparse system rank decomposition support unique solution |
| title | Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph |
| title_full | Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph |
| title_fullStr | Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph |
| title_full_unstemmed | Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph |
| title_short | Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph |
| title_sort | decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph |
| topic | multigraph sparse system rank decomposition support unique solution |
| url | https://journals.bsu.by/index.php/mathematics/article/view/747 |
| work_keys_str_mv | AT ludmilaapilipchuk decompositionmethodsofsparsesystemsoflinearalgebraicequationsforestimationofthetrafficforthegeneralizedmultigraph |