Search

Search Results

• CALCULATION OF THE NUMBER OF SOLUTIONS TO THE EQUATION OF THE FIRST MULTIPLICITY OF TYPES UNDER RESTRICTIONS ON THE FREQUENCY OF OCCURRENCE OF ALPHABET CHARACTERS

  A.K. Melnikov

  2021-02-25

  Abstract ▼

  The article considers the number of solutions to the equation of the first multiplicity of types,
  composed of vectors of multiplicity of types, each element of which is the number of occurrences of
  elements of a certain type (any sign of the alphabet) in the sample under consideration. The equation
  of the first multiplicity of types relates the number of occurrences of elements of all types in
  the sample under consideration and the volume of this sample. The main attention is paid to the
  conclusion and proof of the correctness of the expression that determines the number of nonnegative
  integer solutions of the equation of the first multiplicity of types under conditions of restrictions
  on the frequency of occurrence of alphabet characters. The solution of the equation ofthe first multiplicity of types is the basis for calculating exact approximations of the probabilities
  of statistical values by the first multiplicity method, where the exact approximations are Δexact
  distributions that differ from the exact distributions by no more than a predetermined, arbitrarily
  small value Δ. The value that expresses the number of solutions to the equation of the first multiplicity
  of types is one of the values that determine the algorithmic complexity of the method of the
  first multiplicity, without knowing the value of which it is impossible to determine the parameters
  of samples for which, under restrictions on the computational resource, exact approximations of
  distributions can be calculated. Also, the value expressing the number of solutions to the equation
  of the first multiplicity of types is used in the method of the first multiplicity to limit the search area
  for solutions to the equation. The number of solutions to the equation of the first multiplicity is
  considered under conditions of restriction on the maximum value of the elements of the multiplicity
  vector, and the case is considered when one or more elements of the alphabet may be missing in
  the sample. First obtained the expression that defines the number of nonnegative integer solutions
  to equations of the first multiplicity of types in terms of restrictions on the values of the frequencies
  of occurrence of signs and the possibility of absence of one or more characters of the alphabet in
  the sample reviewed. Analytical expressions are obtained that allow calculating the number of
  integer nonnegative solutions of the equation of the first multiplicity of types for any values of the
  alphabet power, the sample size, and the limit on the maximum frequency of occurrence of alphabet
  characters. The form of the obtained expression allows you to use it when studying the algorithmic
  complexity of calculating exact approximations of probability distributions of statistical
  values with a pre-specified accuracy Δ.

• ALGORITHMIC COMPLEXITY OF CALCULATING EXACT APPROXIMATIONS OF PROBABILITY DISTRIBUTIONS OF STATISTICAL VALUES BY SOLVING THE EQUATION OF THE FIRST MULTIPLICITY OF TYPES

  A.K. Melnikov

  2021-02-25

  Abstract ▼

  We consider the algorithmic complexity of calculating the exact probability distributions of
  statistical values and their exact approximations by solving the first multiplicity equation. As exact
  approximations of probability distributions of statistical values, we consider their Δ−exact distributions
  that differ from the exact distributions by no more than a predetermined, arbitrarily small
  valueΔ. It is shown that the basis of the method for calculating the exact probability distributions
  of statistical values is the enumeration of elements of the search area for solutions to a linear
  equation of multiplicity of types, composed of vectors of multiplicity of types, each element of
  which is the number of occurrences of elements of a certain type (any sign of the alphabet) in the
  sample under consideration. At the same time, it is shown that the method of limiting the search
  area for solutions is used to calculate exact approximations of the probability distribution of statistical
  values. An expression is given that defines the algorithmic complexity of calculating exact
  distributions by solving the first multiplicity equation. The given expression is finite and allows for
  each value of the alphabet power to determine the maximum sample size for which, using a limited
  computational resource, exact distributions can be calculated by solving the first multiplicity
  equation. The range of parameters represented by the sample size and alphabet power for which
  exact distributions can be calculated with a limited computing resource is defined. To estimate the
  algorithmic complexity of calculating exact approximations of distributions, we present an expression
  for the first time obtained for the number of solutions to the equation of the first multiplicity
  with a restriction on the coordinate values of the solution vectors. An expression is given that defines
  the algorithmic complexity of calculating exact approximations by solving the first multiplicity
  equation with a restriction on the coordinate values of the solution vectors. As a parameter for
  limiting the coordinates of solution vectors, the maximum frequency statistic value is used, the
  probability of exceeding it is less than a pre-set, arbitrarily small valueΔ, which allows calculating
  exact approximations of distributions that differ from their exact distributions by no more than the
  selected value Δ. The given expression is finite and allows for each value of the alphabet to determine
  the maximum sample size for which, when using a limited computational resource, exact
  approximations can be calculated by solving the equation of the first multiplicity under the restrictions
  set using the valueΔ. The results of calculations of the maximum sample volumes for
  which exact approximations can be calculated are presented. It is shown that the algorithmiccomplexity of calculating exact distributions exceeds the complexity of calculating their exact approximations
  by many orders of magnitude. It is shown that the use of the first multiplicity method
  for calculating exact approximations allows for the same values of the alphabet power to increase
  the sample volume by two or more times compared to the calculation of exact distributions.

• LIMITING THE NUMBER OF DIFFERENT TEST VECTORS TO OBTAIN ALL SOLUTIONS OF A SYSTEM OF THE SECOND MULTIPLICITY LINEAR EQUATIONS ON MULTIPROCESSOR COMPUTER SYSTEM

  А.К. Melnikov

  2021-07-18

  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 Δ.

• ANALYSIS OF ADVANCED COMPUTER TECHNOLOGIES FOR CALCULATION OF EXACT APPROXIMATIONS OF STATISTICS PROBABILITY DISTRIBUTIONS

  А.К. Melnikov, I.I. Levin, А.I. Dordopulo, L.M. Slasten

  2022-11-01

  Abstract ▼

  The paper is devoted to the evaluation of the hardware resource of computer systems for
  solving a computational-expensive problem such as calculation of the probability distributions of
  statistics by the second multiplicity method based on Δ-exact approximations for samples with a
  size of 320-1280 characters and an alphabet power of 128-256 characters, and with an accuracy
  of Δ=10-5. The total solution time should not exceed 30 days or 2.592·106 seconds for 24/7 computing.
  Owing to the use of the properties of the second multiplicity method, the computational complexity
  of the calculations can be brought to the range of 9.68·1022-1.60·1052 operations with the
  number of tested vectors of 6.50·1023-1.39·1050. The solution of this problem for the specified parameters
  of samples during the given time requires the hardware resource which cannot be provided
  by modern computer means such as processors, graphics accelerators, programmable logic
  integrated circuits. Therefore, in the paper we analyze the possibilities of promising quantum and
  photon technologies for solving the problem with the given parameters. The main advantage of
  quantum computer systems is the high speed of calculations for all possible parameter values.
  However, quantum acceleration will not be achieved to calculate the probability distributions of
  statistics due to the need to check all the obtained solutions. Here, the number of obtained solutions
  corresponds to the dimension of the problem. In addition, due to the current development
  level of the quantum hardware components, it is impossible to create and use the 120-qubit quantum
  computers for the solution of the considered problem. Photon computers can provide high
  computation speed at low power consumption and require the smallest number of nodes to solve
  the considered problem. However, unsolved problems with the physical implementation of efficient
  memory elements and the lack of available hardware components make the use of photon computer
  technologies impossible for calculation of the probability distributions of statistics in the near
  future (5-7 years). Therefore, it is most reasonable to use hybrid computer systems containing
  nodes of different architectures. To solve the problem on various hardware platforms (generalpurpose
  processors, GPUs, FPGAs) and configurations of hybrid computer systems, we suggest to
  use an architecture independent high-level programming language SET@L. The language combines
  the representation of calculations as sets and collections (based on the alternative set theory
  of P. Vopenka), the absolutely parallel form of the problem represented as an information graph,
  and the paradigm of aspect-oriented programming.