LIMITING THE NUMBER OF DIFFERENT TEST VECTORS TO OBTAIN ALL SOLUTIONS OF A SYSTEM OF THE SECOND MULTIPLICITY LINEAR EQUATIONS ON MULTIPROCESSOR COMPUTER SYSTEM
Abstract
In the paper we consider calculation of all integer nonnegative solutions of a linear equation
system (LES) of the second types order by a method of sequential vector testing. The method
checks whether a vector is a solution of the LES. We consider different vectors and test if they
belong to the set of the LES solutions. As a result, after such testing we obtain all solutions of the
LES. The LES testing vector consists of the elements which are the numbers of some alphabet signs
with the same number of occurrences in the sample. The LES unites the number of occurrences of
the elements of all types into the considering sample, the power of the alphabet, the size of the
sample, and the limitation for the maximum number of occurrences of the alphabet signs into the
sample. The LES solution is the base for calculation of exact statistics probability distributions
and their exact approximations by the method of the second types order. Here, the exact approximations
are Δexact distributions. The difference between the Δexact distributions and the exact
distributions does not exceed the predefined arbitrary small value Δ. The number of test vectors is
one of those which defines algorithmic complexity of the method of second types order. Without it,
it is impossible to define the parameters of samples, and to calculate exact distributions and their
exact approximations for limited hardware resource. We consider various test vectors for the limited
maximum number of occurrences of the alphabet signs in the sample, and for the unlimited
one. We have obtained formulas to calculate the number of tests for various vectors. Here, the
values of the power of the alphabet, the size of the sample, and the limitations for the maximum
number of occurrences of the alphabet signs into the sample can be arbitrary. Using the obtained
formulas, we can get all integer nonnegative solutions of the LES of the second types order. We
can use the obtained formula for analysis of algorithmic complexity of calculations of exact distributions
and their exact approximations with the predefined accuracy Δ.
References
computing systems], under the general ed. of I.A. Kalyaeva. Taganrog: Izd-vo YuFU, 2016,
472 p. ISBN 978-5-9275-1918-7.
2. Korneev V.V. Vychislitel'nye sistemy [Computing systems]. Moscow: Gelios ARV, 2004,
512 p. ISBN 5-85438-117-6.
3. Mel'nikov A.K. Avtomatizatsiya protsedury analiza soobshcheniy na gibridnykh vysokoproizvoditel'nykh
vychislitel'nykh kompleksakh [Automation of message analysis procedure
on hybrid high performance complexes], Superkomp'yuternye tekhnologii (SKT-2016): Mater.
4-y Vserossiyskoy nauchno-tekhnicheskoy konferentsii [Proceedings of the 5 th All-Russia
Conference on Supercomputer Technologies (SCT-2016)]: in 2 vol. Rostov-on-Don: Izd-vo
YuFU, 2016, pp. 69-73. ISBN 978-5-9275-2039-8 (T. 1).
4. Chepovskiy A.M. Informatsionnye modeli v zadachakh obrabotki tekstov na estestvennykh
yazykakh [Information models in tasks of processing of natural language texts]. Moscow:
Natsional'nyy otkrytyy universitet «INTUIT», 2015, 228 p. ISBN 978-5-9556-0176-2.
5. Dvoynikova A.A., Karpov A.A. Analiticheskiy obzor podkhodov k raspoznavaniyu tonal'nosti
russkoyazychnykh tekstovykh dannykh [Analytical review of approaches to Russian text sentiment
recognition], Informatsionno-upravlyayushchie sistemy [Information and Control Systems],
2020, No. 4, pp. 20-30. Doi: 10.31799/1684-8853-2020-4-20-30.
6. Mal'tsev G.N., Dzhumkov V.V. Additivnaya granitsa veroyatnosti oshibki v diskretnom kanale
peredachi informatsii s pomekhoustoychivym kodirovaniem i gruppirovaniem oshibok [Additive
boundary of error probability in a discrete data transmission channel with noise-immune
coding and grouping of errors. Informatsionno-upravliaiushchie sistemy], Informatsionnoupravlyayushchie
sistemy [Information and Control Systems], 2020, No. 4, pp. 78-86. Doi:
10.31799/1684-8853-2020-4-78-86.
7. Dikiy D.I. Metod obnaruzheniya DoS-atak na prikladnom urovne v setyakh ≪izdatel'-
podpischik≫ [DoS attack detection at application level in publish-subscribe networks],
Informatsionno-upravlyayushchie sistemy [Information and Control Systems], 2020, No. 4,
pp. 50-60. Doi: 10.31799/1684-8853-2020-4-50-60.
8. Ronzhin A.F. Asimptoticheskaya lokal'naya otnositel'naya effektivnost' (ALOE) kriteriev soglasiya
[Asymptotic local relative efficiency (ALRE) of fitting criteria], Tez. dokladov Vsesoyuznoy
konferentsii «Veroyatnostnye metody v diskretnoy matematike» [Reports of All-USSR conference
“Probabilistic methods in discrete mathematics”]. Petrozavodsk, 1983, pp. 70-71.
9. Mel'nikov A.K. Sravnenie effektivnosti obrabotki tekstov pri primenenii v statisticheskikh
kriteriyakh tochnykh i predel'nykh priblizheniy bazovykh raspredeleniy veroyatnostey
znacheniy testovykh statistik [Comparison of the efficiency of text processing when applying
accurate and limiting approximations of basic probability distributions values of test statistics
in statistical criteria], Obozrenie prikladnoy i promyshlennoy matematiki [Review of applied
and industrial mathematics], 2018, Vol. 25, Issue 4, pp. 375-378. ISSN 0869-8325. Available
at: https://tvp.ru/conferen/vsppmXIX/repso114.pdf (accessed 14 October 2019).
10. Mel'nikov A.K. Primenenie tochnykh raspredeleniy v protsedure dvukhetapnoy obrabotki
tekstov [Application of exact distributions in the procedure of two-step text processing],
Obozrenie prikladnoy i promyshlennoy matematiki [Review of applied and industrial mathematics],
2018, Vol. 25, Issue 2, pp. 89-95. ISSN 0869-8325. Available at:
https://tvp.ru/conferen/vsppmXIX/repso051.pdf (accessed 24 January 2019).
11. Mel'nikov A.K. Slozhnost' rascheta tochnykh raspredeleniy veroyatnosti simmetrichnykh
additivno razdelyaemykh statistik i oblast' primeneniya predel'nykh raspredeleniy [The complexity
of calculating the exact probability distributions of symmetric additive-separated statistics
and the application of limit distributions], Doklady TUSUR [Proceedings of Tomsk State
University of Control Systems and Radioelectronics]. Tomsk, 2017, Vol. 20, No. 4, pp. 126-
130. ISSN 1818-0442.
12. Mel'nikov A.K. Metodika rascheta raspredeleniya veroyatnostey znacheniy simmetrichnykh
additivno razdelyaemykh statistik, priblizhennykh k ikh tochnomu raspredeleniyu [A method
for calculating the probability distribution of values of symmetric additively separated statistics
that are close to their exact distribution], Nauchnyy vestnik NGTU [Science bulle-tin of the
Novosibirsk state technical university], 2018, No. 1 (70), pp. 153-166. ISBN 1814-1196.
Doi: 10.17212/1814-1196-2018-1-153-166.
13. Kendall M.G., St'yuart A. Teoriya raspredeleniy [Distribution theory]. Moscow: Nauka, 1966,
302 p.
14. Zuev Yu.A. Sovremennaya diskretnaya matematika: Ot perechislitel'noy kombinatoriki do
kriptografii XXI veka [Modern Discrete Mathematics: From Enumerative Combinatorics to
XXI century Cryptography]. Moscow: LENARD, 2019, 720 p. (Fundamentals of information
security No. 17). ISBN 978-5-9710-5660-7.
15. Kramer G. Matematicheskie metody statistiki [Mathematical methods of Statistics]: trans.
from engl. Moscow: Mir, 1975, 648 p.
16. Mel'nikov A.K., Ronzhin A.F. Obobshchennyy statisticheskiy metod analiza tekstov,
osnovannyy na raschete raspredeleniy veroyatnosti znacheniy statistik [Generalized statistical
method of text analysis based on the calculation of probability distributions of statistical values],
Informatika i ee primeneniya [Informatics and its Applications], 2016, Vol. 10, Issue 4,
pp. 91-97. ISSN 1992-2264.
17. Shurygin V.A. Slozhnostnyy metod teorii algoritmov [The complexity method of the theory of
algorithms]. Moscow: Knizhnyy dom "LIBROKOM", 2009, 200 p.
18. Fisher R.A. Statisticheskie metody dlya issledovateley [Statistical methods for researchers]:
trans. from engl. Moscow: Gosstatizdat, 1958, 73 p.
19. Alekseev V.E. Diskretnaya matematika: ucheb. posobie [Discrete mathematics. Training manual].
Nizhniy Novgorod: Nizhegorodskiy gosuniversitet, 2017, 139 p.
20. Knut D.E. Iskusstvo programmirovaniya dlya EVM. T. 3. Sortirovka i poisk [The art of computer
programming. Vol. 3. Sorting and search]. Moscow: Mir, 1978, 844 p.
21. Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2020664143. Raschet
chisla resheniy sistemy lineynykh uravneniy vtoroy kratnosti tipov. Pravoobladatel' Kolodzey
A.V. Avtor: Kolodzey A.V. i Mel'nikov A.K. Zayavka № 2020662473. Data postupleniya 19
oktyabrya 2020 g. Data gosudarstvennoy registratsii v Reestre pro-gramm dlya EVM 9
noyabrya 2020 g. [Certificate of state registration of computer software № 2020664143. Calculation
of the number of solutions to a system of linear equations of the second multiplicity of
types. Proprietor Kolodzey A.V. Authors: Kolodzey A.V и Melnikov A.K. Application
№ 2020662473. Date of filing – October 19, 2020. Date of state registration in the Register of
computer software – November 9, 2020].
22. Kholl M. Kombinatorika [Combinatorics]. Moscow: Mir, 1970, 424 p.
23. Riordan Dzh. Vvedenie v kombinatornyy analiz [Introduction to combinatorial analysis]. Moscow:
Izd-vo inostrannoy lit., 1963, 288 p.
