Advancement of a long arithmetic technology in the construction of algorithms for studying linear systems

We have advanced the application of algorithms within a method of basic matrices, which are equipped with the technology of long arithmetic to improve the precision of performing the basic operations in the course of studying the ill-conditioned linear systems, specifically, the systems of linear algebraic equations (SLAE). Identification of the fact of ill-conditionality of a system is a rather time-consuming computational procedure. The possibility to control computations entering the state of incorrectness and the impossibility of accumulating calculation errors, which is a desirable property of the methods and algorithms for solving practical problems, were introduced. Modern computers typically use the standard types of integers whose size does not exceed 64 bytes. This hardware limitation was resolved using software, specifically, by developing a proprietary type of data in the form of a special Longnum library in the C++ language (using the STL (Standard Template Library)). Software implementation was aimed at carrying out computations for methods of basic matrices (MBM) and Gauss matrices, that is, long arithmetic for models with rational elements was used. We have proposed the algorithms and computer realization of the Gauss type methods and methods of artificial basic matrices (a variant of the method of basic matrices) in MatLAB environment and Visual C++ environment using precise computation of the methods' elements, first of all, for the ill-conditioned systems of varying dimensionality. The Longnum library with the types of long integers (longint3) and rational numbers (longrat3) with the numerator and denominator of the longint3 type was developed. Arithmetic operations on long integers were performed based on the modern methods, including the Strassen multiplication method. We give the results from the computational experiment employing the mentioned methods, in which test models of the systems were generated, specifically, based on the Gilbert matrices of different dimensionality

section_content: Mathematical modeling of processes of different nature is known to lead to the need to explore non-linear equations and systems of varying complexity (mathematical models). 

In many cases, they are solved by the introduction of certain simplifications in statements, transition, in particular, to difference analogues (discrete variant) and eventually to the systems of linear algebraic equations (SLAE) of different dimension, often with a square matrix of restrictions. The
section_name: Introduction

section_content: methods and algorithms of SLAE (as the basic ones) have become the subject-matter of research of many scientists. This, in turn, caused the development of (currently) many dozens of exact methods and, perhaps, hundreds of iterative methods. An exceptional position in the chain of the solution of an initial problem of modeling caused exceptional requirements for computing properties of the methods and algorithms for the solution of the SLAE. Natural complexity of solving such problems is manifested in incorrectness and ill-conditionality. The efforts of calculators are aimed to overcome (or weaken) the manifestation of ill-conditionality and incorrectness in the course of solving a problem and (accumulation of calculation errors). There appear new approaches to solving the known problems. According to the authors, one of the promising approaches is the development of the known methods (including the algorithms of the method of basic matrices), equipment with the technology of long arithmetic during studying ill-conditioned linear systems. Of course, the latest technology (of long arithmetic) involves the use of other technologies, which will be mentioned below, specifically, the introduction of a new data class. It is the successful combination of a series of new technologies of computation algorithms organization that can provide new positive possibilities. 

The problem of modeling the processes of different nature is often described by a class of optimal problems (for extremum), in particularly, the SLAE. Precise methods for the solution of the SLAE in the number of the above problems are fundamental, since research into the initial more complex mathematical models "is reduced" (after some simplifications) to the analysis of such linear systems. 

It is known that:

-most mathematical problem statements (in the first place, on studying the properties of processes) are inherently non-linear, that is they do not have any adequate representation in the class of linear models (matrix structures) -the systems of linear algebraic equations, inequalities, linear programming problems, etc. ;

-important parameters of the process (in the process of simulation and simplifications) are mapped ("transfer") to separate elements, rows, columns and blocks ("sub-matrices") of the restriction matrix, etc., that is, undergo changes and clarifications. Therefore, taking into consideration the impact of the changes in a model as a result of specifications (without re-solving) is a desirable characteristic of the methods of modeling. 

The existing property of ill-conditionality and incorrectness in the problem is at all stages of the simulation. Specifically, at the stage of a computer representation of a modelrounding, truncation, the limited length of the mantissa causes the accumulation of mistakes, errors, inaccuracies of the model representation, etc. This gives rise to inadequacy of the studied process and the model. It should be noted that in such situations, even minor quantitative inaccuracy in the representation of a model can often lead to significant deviation (error) of the solution. Equipment of algorithms with the technology that prevents the accumulation of errors at the stages of modeling, specifically, during the iterations of the algorithm of the method is the relevant direction of research.
section_name: Розвинуто застосування алгоритмів методу базисних матриць, які оснащені технологією довгої арифметики для покращення точності виконання основних операцій при дослідженні погано обумовлених лінійних систем, зокрема систем лінійних алгебраїчних рівнянь (СЛАР). Встановлення факту поганої обумовленості системи є досить трудомісткою обчислювальною процедурою. Закладено проведення контролю входження обчислень в стан некоректності та унеможливлення накопичення похибок обчислень, що є бажаною властивістю методів та алгоритмів розв'язання практичних задач. В сучасних ЕОМ, як правило, використовуються стандарті типи цілих чисел, розмір яких не перевищує 64 байта. Було подолано це апаратне обмеження програмним шляхом, а саме, розробкою власного типу даних у вигляді спеціальної бібліотеки Longnum мовою С++ з використанням стандартної бібліотеки шаблонів STL(Standard Template Library). Програмна реалізація була розвинута на проведення обчислень за методами базисних матриць (МБМ) та Гауса, тобто використано довгу арифметику для моделей з раціональними елементами. Запропоновано алгоритми та комп'ютерну реалізацію методів типу Гауса та штучних базисних матриць (варіант методу базисних матриць) в середовищах Мatlab та Visual С++ з використанням технології точних обчислень елементів методів, в першу чергу, для погано обумовлених систем різної розмірності. Розроблено бібліотеку Longnum з типами довгих цілих чисел (longint3) та раціональних чисел (longrat3) із чисельником та знаменником типу longint3. Арифметичні операції над довгими цілими числами реалізовано на основі сучасних методів: зокрема, методу Штрасена множення. Наведено результати обчислювального експерименту за згаданими методами, в якому тестові моделі систем генерувались, зокрема, на основі матриць Гільберта різної розмірності, які характеризуються як "незручні" Ключові слова: метод базисних матриць, точні обчислення, погано обумовлена система лінійних рівнянь

section_content: Up to now, quite a lot of precise and iterative methods for solving systems of linear algebraic equations have been developed. Specifically, some of them are listed in papers [3, 4] and there exist many others. It may be stated that the problem of the development of a universal high-precision method for solving a wide class of linear problems has not been solved so far. This can be explained by the objective complexities of problems that arise, especially when modeling the processes of different nature. Mathematical models are quite often represented as great dimensionalities, are incorrect (sensitive to inaccuracies), ill-conditioned, etc. [1, 2]. Technological advances of today, such as increasing the digits of processors up to 64 and the volumes of different memory types, together with the increasing rate of performing operations, provide additional opportunities for representing long numbers. However, they do not solve the problem of the representation of numbers and implementation of operations for the numbers with more than 64 digits and it remains open. In this regard, for various kinds of ill-conditionality or the structure of the restriction matrix, there is a need to adapt the solution algorithm to ensure the computational quality [3] [4] [5]. 

Of course, among them, a special place is taken by algorithmic schemes that are based on the Gaussian method. It is known that the SLAE models can often be incorrect by their structural properties (natural complexity). One of the manifestations of incorrectness is the property of ill-conditionality (conditionality number

takes large values that affect the errors of performing basic operations) [1] [2] [3] [4] [5]. It is possible to make sure that the information on the significance of the conditionality number (or its assessment) as a factor of control of calculation correctness currently remains in the scope of further research [3] [4] [5]. Specifically, the existence of the system conditionality control, accumulation of calculation errors when solving such inconvenient problems is a necessary and integral component of the computation process. From the point of view of the classical methods of the Gaussian type, for example, the procedure of construction the estimator of conditionality number can be added somehow "from the outside". In the scheme of these methods, there are no components of finding or assessment of conditionality

(since the inverse matrix is unknown) and in itself is a computationally time-consuming procedure. It is a specific task to "embed" organically such procedure into the algorithm. The problem of evaluation of the conditionality number became especially acute during accumulation of considerable experience of solving practical problems. The existence of estimation of conditionality during the computation is an important component, because it "gives the signal" (points out) of correctness of calculations. As an additional measure in solving the conditionality problem (conditionality improvement), it can be represented in the form of directed conversion of the original problem (preconditioning), for example, by multiplication of SLAE on the left and on the right by special matrices [5, 6]. 

To check and control the properties of the solution algorithms (testing this class of tasks), a series of algorithms, programs and modeling problems with ill-conditioned restriction matrices, such as BLAS (Basic Linear Algebra Subroutines) were developed [6]. It is known that such test matrices include the Gilbert matrix. It is actively applied in this work for testing the algorithms. The research into the influence of disturbances (such as calculation errors) on the properties of a system remains the "corner stone" during modeling. This problem is explored in a series of scientific studies, specifically, [1, 2, 6, 7]. One of the areas that has been actively developing lately, is associated with the development of mathematical methods, algorithms and software for performing the basic operations, specifically, by the introduction of new data types (for actions with rational numbers), which prevents the accumulation of errors. These approaches are discussed in papers [8] [9] [10] [11]. One of the drawbacks of this approach is an additional computational load in the algorithm, which causes a slowdown of computation and imposes restrictions on dimensionality of the solved problems. 

But the mentioned approaches do not cover the problem, so it is advisable to develop the performance of calculations using the technology of long arithmetic on the model of rational elements, one of the variants of which was implemented in the form of the Longnum library in the C++ language [23]. The application of rational arithmetic for direct methods of solution of SLAE eliminates a computational error and makes it possible to concentrate on the properties of a model itself, for example, in [7]. 

Modern computers usually use the standard types of integers, dimensionality of whose does not exceed 64 bites. Overcoming such hardware limitations can be addressed via programs, specifically, the development of the own data type. The known examples of the implementation of such approach are the GMP [8], MPI [9], LIP [10], OpenSSL [11], and LibTomMath libraries [12]. The GMP and LIP libraries are time-consuming and not convenient enough to use; OpenSSL and LibTomMath have cryptographic purposes; MPI library is not currently developing [9]. It is important to develop a library that does not depend on outside developments, in addition to the standard C++ libraries and can flexibly change and adapt to specific research. 

Of course, the above-mentioned methods for intensification of calculation procedures have their strengths and weaknesses. They are often used separately. It seems expedient to develop the original calculation technology, which would rationally use the strengths of these approaches. 

The method proposed in [14] has a series of structural properties, specifically, the capability to analyze and address the problems of linear programming (PLP) along with the SLAE, it is applied to weakly non-linear problems, has in its elements the components for calculation and evaluation of conditionality of a system during iterations [15] [16] [17] [18], it can be equipped with the technology of long numbers. The mentioned properties of the method and the algorithms of basic matrices in equipment with the technology of operation with long numbers gain the versatility features for using in solving a wide class of problems. 

The analysis of literary sources and identification of the major problems in the organization of calculations indicate that it is possible to reach precision of performing basic operations by inclusion and successful combination of the additional procedures: preconditioning, finding evaluation and conditionality number, conducting high-precision basic operations. The efforts of researchers should be aimed at the development of the computation technology with such properties (with elements of universality). 

The choice of MBM as the basic one in the development of the technology of long numbers was based on the presence of such unique property as control of calculations entering the incorrectness state, specifically, the information on direct and inverse matrix as the components of the calculation of conditionality number. Construction of an estimator of conditionality number (and pre-conditioner) and its properties (with experiments) based of MBM are covered in [18]. 

This indicates the feasibility of application of MBM and its algorithms as those that were tested [14] [15] [16] [17] [18], for "add-in" with the procedures of high-precision conducting the basic operations (technology of long arithmetic) in the study of linear systems.
section_name: Literature review and problem statement

section_content: The aim of the study is to develop the technology of long arithmetic, which increases the precision of performance of the basic operations of the algorithms for studying and solution of SLAE and minimizes the module of magnitude of errors at the stage of computer modeling. 

To accomplish the aim, the following tasks have been set:

-to develop an algorithm for solving the SLAE (a linear system) with the elements of analysis and control of conditionality and accumulation of errors in the course of iterations (technology of long arithmetic) when implementing the technology of long arithmetic;

-to implement the types of long integers and rational numbers with fast operations of multiplication, division, constructed on modern algorithms and to accelerate the operation of multiplication and division of operations with long numbers.
section_name: The aim and objectives of the study

section_content: First of all, we would like to stress that the method of basic matrices (first mentioned in publications at the end of 1980s) was developed in the article by the equipment with the technology of long arithmetic [14]. It is possible to find the detailed substantiation of the method, its properties, the results of the computational experiments, comparisons with other methods in papers [15] [16] [17]. 

Let us consider the SLAE in the form

where matrix A of dimensionality (m×m),

are the rows of matrix A. Equation ( 1 ) is supplemented with the additional SLAE of the form:

where I is the unity-diagonal matrix of dimensionality (m×m) and (1,1,. . .,1) T K = is the vector of dimensionality m. It should be noted that system (2) is usually trivial, with the known properties and performs only the auxiliary role of building the initial values of the MBM elements, specifically, of the inverse matrix and solution. 

That is the construction of the algorithm for solving the SLAE is based on the method of basic matrices, since according to [14], it implies the ability:

-to find the magnitude of the rank of the matrix of the system restriction (1); -to find the solution to SLAE (1); -to control the conditionality of a system; -to analyze the influence of changes in the model (1) as a result of specifications (without re-calculations); -to equip with the technology that prevents error accumulation;

-to construct initial solutions to problems based on the trivial basic matrices (2), which excludes time-consuming initial calculations;

-to apply the system of analysis to the problems that imply multi-step or multiple calculations on the models with insignificant changes. 

We will remind briefly [14] that the proposed method of artificial basic matrices (MABM) is based on the idea of the ordinal basic matrix. Basic matrices during the iterations are sequentially changed by the input-output of rows-normals of problem restrictions from them. 

Submatrix b A, composed of m linearly independent restriction of row-normals (i 1, i 2, …, i m ), will be called artificial base, and solution u 0 to the corresponding to them equation system According to Theorem 1 [14], the corresponding ratios were established between the coefficients of expansion of normals of constraints, elements of inverse matrices, basic solutions, mismatches between restrictions in two adjacent basic matrices. 

Based of them, the scheme of determining the rank of the system (1) and the solution of the system of equations, successive changes of basic matrices and corresponding artificial solutions are constructed. 

The preliminary results of application of the technology of long arithmetic in conjunction with the method of basic matrices for analysis of the SLAE properties (with implementation) were examined in [22]. "Long arithmetic" of the representation of rational numbers when performing basic operations eliminates the accumulation of errors, which in combination with the conditionality control in the course of computing is effective, especially in the study of ill-conditioned systems. For the latter, even small errors in the representation of the model and the calculation have an essential impact. 

In the subsequent versions, the technology repeatedly underwent improvements and both programmatically and algorithmically, the relevant calculation experiments were conducted. 

The subject of research will be the properties of the new algorithm and the computer implementation of the method of artificial basic matrices [14] for model (1) in the Visual C++ environment using rational arithmetic, in which multiplication of long numbers is made with the help of the Strassen method based on the fast algorithm of discrete Fourier transform [19]. 

The concept of representation of integers. Modern computers usually use the standard types of integers, the size of which does not exceed 64 bytes. Overcoming such hardware limitations can be addressed programmatically, specifically, by the development of its own data type [22]. In the Longnum library developed in the language C++, the types of long integers longint3 and corresponding rational numbers and longrat3 with fast operations of multiplication, division, constructed on modern algorithms, were implemented. 

For the realization of long integers of arbitrary size and appropriate rational numbers in C++, the object-oriented approach (OOA) was used [21]. It involves the following: the real object of the domain is placed in line with the so-called object type or the class of objects, which is a generalization of a structural type. 

Let us use the definitions [21]. Definition 1. Class in C++ is a programming structure consisting of data (data elements or fields) and subroutines that operate on these fields and describe the properties of the corresponding object of the modeled subject area. 

The general concept of long or multiple precision arithmetic, the notion of a long integer is described in [12]. But for clarity, we will introduce the concepts:

A long integer or an integer of arbitrary size will be called an integer not limited to ranges of standard computer types. For example, in respect to the language C++, such numbers are fundamentally impossible to store in a variable of type _ _ int64 or unsigned_int64 that are limited to ranges from -2 63 to 2 63 and from 0 to 2 64 -1, respectively. 

Long or multiple precision arithmetic is the arithmetic of long integers. 

An integer of an arbitrary size is programmatically represented as class longint3. Rational number as a pair (numerator of longint3 class, denominator of longint3 class) is programmed in the form of longrat3 class. An integer is stored in a dynamic array, the maximum length of which is 4096. The elements of the vector are 16-byte unsigned numbers of the standard C++ unsigned__int16 type and are, in fact, the "numbers" in the number system with base BASE=2 16. Thus, for example, an integer from the range from 2 32 to 2 64 -1 will be stored in an array of size 3. 

Arrays of "numbers", the number sign and operations on numbers of such structure are organized in the form of longint3 class. Specifically, in the longint3 class, the following operations with integers are implemented: addition, subtraction, multiplication and division with residue, comparison, conversion into the character string of the char type. During the development of the Longnum library [22], the elements of the STL (Standard Template Library) were used [ Representation of rational numbers. A rational number is represented as a pair: the numerator and denominator of the longint3 type and is organized in the form of the longrat3 class. This class is also equipped with the operations of addition, subtraction, multiplication, division, reducing, comparison, representation as a decimal number with specified precision, conversion in the type double, conversion into the character string of the char type. Operations '+', '-', '*', ' /' are constructed using the appropriate operations on numbers of the longint3 type. These classes were compiled as a dynamic library and tested for precise solution of the systems of linear algebraic equations. Operations '+' and '-' are implemented by classic algorithms of addition and subtraction; multiplication and division and significantly improved in comparison with the traditional algorithms for multiplication and division in a column and optimized both for time and for the use of computer resources.
section_name: Technologies of long arithmetic of acceleration of performing major operations based on the algorithm for the method of basic matrices (MBM)

section_content: Arithmetic operations with precise rational numbers are based on multiplication of long integers. To reduce rational fractions, division of a long integer by a long integer was implemented. 

Multiplication of long integers using the Strassen method based on the discrete Fourier transform. 

The product of integers

and

in a number system with BASE can be interpreted as product of polynomials

where c i is the components of the vector -convolutions of vectors (a 0, a 1, …,. 

The Strassen method [20] of multiplication of long numbers is based on. 

Theorem of convolution [20]. Fourier transform from a cyclic convolution of two vectors is a scalar product of the Fourier-images of these vectors:

Here, * means component-wise multiplication of vectors. Thus, to multiply long integers A and B, it is enough: 1. To calculate coefficients of convolution, 0, 1. 

To make all transfers, for all coefficients to be smaller than BASE. 

The theorem of convolution allows constructing the effective algorithm for calculation of convolution coefficients at step 1 with the help of DFT:

1. 1. Calculate F(a) and F(b). 1. 2. To multiply the resulting vectors component-wise. 

1. 3. To calculate inverse DFT from scalar product. Multiplication of polynomials is reduced to scalar product of corresponding vectors. It is assumed that at every step the sizes of the vectors are the same and equal to N. The complexity of the multiplication algorithm has the order of O(NlogN). Moreover, the optimal performance is reached only by the options of FFT (fast algorithm of discrete Fourier transform) that operate on vectors of the size of N=2 k, so the vectors in these situations must be supplemented by zeros. The Strassen method is implemented in the longint3 class of the Longnum library. 

Division of long integers. The operation of division of long numbers is used in the operation of reduction of rational numbers. The "school" method of division "in column", the complexity of which is O(nm), where n and m are the number of digits of a dividend and a divisor, respectively, is taken as a base. 

Here are the main stages of the algorithmic scheme for finding the magnitude of rank, the initial basic matrix and solution of the non-degenerated system (1) with the rational elements, based on the technology of precise calculations. The algorithm can be applied in the conversion of an inverse matrix during the iteration process. It is advisable to use such conversion at the accumulation of significant errors when finding the elements of the method. Based on the results of the given algorithm, it is possible to construct the analytical representation of general solution of the corresponding system of linear algebraic inequalities (SLAE) [14].
section_name: Acceleration of operations of multiplication and division of long numbers.

section_content: At the input: matrix of coefficients of A of dimensionality m×m, vector of right parts of SLAE C of dimensionality m and unity basic matrix I of dimensionality m×m, representing dynamically created arrays of the elements of the longrat3 type. The following steps will be subsequent-ly performed with using the operations of comparison, addition, subtraction, multiplication and division of the longrat3 class. 

Step 1. We perform simplex iterations on substitution of the rows of basic matrix I of system (2) with the normals of restrictions of system (1), according to the ratios of theorem 1 [14]. 

We find the corresponding elements of the method: vectors of expansion by the rows of the basic restriction matrices (2), inverse basic matrix, artificial basic solutions ( ) 0 k u, where k is the number of iterations. 

Step 2. Check the number of iterations r of the substitution of the rows of the additional system with the rows of the main system, which meet the conditions of non-degeneration, i. e. ( ) 0 i lk α ≠ number determines the rank of the main system, (Consequence 2-3 of theorem 1 [14] ). 

Step 3. If the number of iterations, for which ( ) 0, i lk α ≠ is equal to m, proceed to the next step. Otherwise, to the last but one step. 

Step 4. Find the only solution (consequence 1 of theorem 1 [14] ). According to the ratio:

Step 5. Meeting condition r<m means violation of condition of a single solution by the scheme of the method, i. e., the models requires refinement and further analysis of solvability (consequence 1 of theorem 1 [14] ). 

Last step. Generation of original information according to the results of analysis (1) in the form of an array of elements of the longrat3 type. 

The algorithm can be applied in re-calculation of the inverse matrix during the iteration process of finding an optimal solution. It is advisable to perform such conversion at the accumulation of significant errors when finding the elements of the method. Based on the results of the presented algorithm it is possible to construct the analytical representation of the general solution of SLAE.
section_name: Algorithms MABM

section_content: We explored two SLAE with ill-conditioned matrices, specifically, the Gilbert matrix A 1 with elements (

,

Matrix A 1 was explored with such variations of vector c 1 of the right parts:

1

Vector of the right parts c 2 for matrix A 2 is determined from ratio:

(

Solution of SLAE using the Longnum library. In the process of solving the SLAE of dimensionality of m=50 with the Gilbert matrix and unity right part, using precise computations, we obtained the precise solution (Table 1 ). The SLAE were solved using the Gaussian methods and the MABM with the Gilbert matrix of dimensionality of m=100, the reference to precise solution was published in [22]. 

As a result of the experiments for SLAE with the Gilbert matrix A 1 of dimensionality of m=100 and the unity right part c 1, we obtained precise solutions (Table 2 ) both by the Gaussian method, and by the method of the coinciding artificial basic matrices. Tables 2 3 4 show the time of performance of the procedure of precise solution computation using the computer with the processor AMD Athlon(tm) 64X2 Dual Core Processor 4200+, 2. 21 GHz, 3 GB OSD. 

For SLAE with the matrix of coefficients A 2, calculations with the use of the Gaussian method and the MABM were carried out. The results of the computational experiment are shown in Table 3. As a result of the experiments for SLAE with the Gilbert matrix of dimensionality m=100 and unity right part c 1 (using the Strassen method), we obtained precise solutions by both the Gaussian method, and by the method of artificial basic matrices that are consistent with [2]. Thus, Table 4 shows that for the MABM with the SLAE with the Gilbert matrix, the minimal leading element decreases at an increase in dimensionality, which is associated with the property of ill-conditionality of the Gilbert matrix. In addition, the time of performance of calculations increases, which is caused by both an increase in the number of arithmetic operations on rational numbers and an increase in mantissas of numerators and denominators of rational numbers. It should be noted that according to the data of comparison of Table 4, the time of computation experiments is significantly shorter for the new version of the Longnum library, which is an improvement of the longint3 class.
section_name: Results of research into computational properties of software implementation of the methods and algorithms

section_content: Application of a new class of longint3 makes it possible (Table 4 ):

1) to accelerate precise computations by 2. 5 times: the SLAE with the Gilbert matrix of dimensionality of 100 was solved with the MBM in exact numbers in 1397. 4 sec, whereas the time of performance with the old class of longint2 on the same computer was 3731. 94 seconds [22] ;

2) to solve ill-conditioned SLAE of large dimensionality. Compared to the old version of the Longnum library of precise computations, the following was done in the new version:

-implementations of arithmetic operations with long integers were optimized taking onto account the new standard programming language C++17; -outdated functions (itoa, strcpy, sprintf, strcat) of standard C++ libraries were replaced by the new, more effective and safe analogues. 

Thus, the advantage of using the new version of Longnum compared with the previous version [22] is the higher computational effectiveness. 

The disadvantage of using precise calculations, specifically, the Longnum library, when solving SLAE is that the computation volume greatly depends not only on dimensionality of the SLAE, but also on the properties (conditionality) of the matrix of SLAE itself (Tables 2 3 4 ). 

The MABM in combination with the precise computation technology of the Longnum library can be particularly useful in scientific research into the properties of SLAE and SLAN, mathematical modeling, and applied research in sci-ence and technology, which relate to the necessity of solution of ill-conditioned SLAE. 

The presented study is the development of approaches to the organization and performance of the basic operations (presented in papers [8, 14]. Specifically, the technology of high-precision computation with rational numbers was combined with the control of conditionality of the system according to the scheme of the MBM algorithm, and software implementation (data type organization) was improved.
section_name: Discussion of results of the computational experiment

section_content: The results of the computational experiment on realization of the algorithms for conducting high-precision computations (the technology of long arithmetic) using the method of artificial basic matrices provide grounds to argue that:

1. The algorithm of SLAE (linear system), which effectively applies the value of the leading element of the method and elements of inverse matrix in order to carry out control of conditionality of the system (exceptional property of the MBM elements) was developed and implemented. 

2. We implemented: the types of long integers longint3 and corresponding rational numbers and longrat3 with fast operations of multiplication, division, constructed on modern algorithms, which prevents the accumulation of errors in the course of iterations (additional equipment of the MBM algorithm). 

The representation (for making computations) of rational numbers as a pair: numerator and denominator of the longint3 type was developed and organized in the form of the longrat3 class (improved compared with the previous version of the algorithm); the acceleration of the operations of multiplication and division of long numbers (for the new proposed version of the Longnum library in comparison with the previous version) was achieved. It should be noted that the additional capabilities of control of computations and measures to increase the precision of operations of the long arithmetic technology, in general, caused a slight slowdown of the algorithm operation and imposed restrictions on dimensionality of the solved SLAE. 

It was established that the developed algorithms can serve as testing programs to verify the precision of carrying out computations using other algorithms for the problems of medium dimensionality.
section_name: Conclusions

section_name: Проведена модернізація методів ідентифікації стану об'єктів в умовах нечітких вхідних даних, описаних своїми функціями належності. Обраний напрямок вдосконалення традиційних методів пов'язаний із принциповими особливостями вирішення цього завдання в реальних умовах малої вибірки вхідних даних. У цих умовах для розв'язання задачі ідентифікації стану доцільно перейти до менш вибагливої в інформаційному відношенні технології опису вихідних даних, заснованої на математичному апараті нечіткої математики. Цей перехід зажадав розробки нових формальних методів вирішення конкретних завдань. При цьому для багатовимірного дискримінантного аналізу розроблено методику розв'язання нечіткої системи лінійних алгебраїчних рівнянь. Для вирішення завдання кластеризації запропонована спеціальна процедура порівняння нечітких відстаней між об'єктами кластеризації і центрами групування. Обраний напрямок вдосконалення традиційного методу регресійного аналізу визначено неможливістю використання класичного методу найменших квадратів в умовах, коли всі змінні описані нечітко. Ця обставина привела до необхідності побудови спеціальної двохкрокової процедури вирішення завдання. При цьому реалізується мінімізація лінійної комбінації міри видалення шуканого рішення від модального і міри компактності функції приналежності пояснювальної змінної. Технологія нечіткого регресійного аналізу реалізована в важливому для практики випадку, коли вихідні нечіткі дані описані загальними функціями приналежності (L-R) типу. При цьому отримано аналітичний розв'язок задачі у вигляді розрахункових формул. В результаті обговорення показано, що модернізація класичних методів рішення задачі ідентифікації стану з урахуванням нечіткого характеру представлення вихідних даних дозволила проводити ідентифікацію об'єктів в реальних умовах малої вибірки нечітких вихідних даних Ключові слова: нечіткі багатовимірний дискримінантний, кластерний, регресійний аналізи, технології зведення нечітких задач до чітких