DOI: https://doi.org/10.15587/1729-4061.2019.157521

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

Volodymyr Kudin, Viacheslav Onotskyi, Ali Al-Ammouri, Lyudmyla Shkvarchuk

Abstract


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

Keywords


method of basic matrices; precise calculations; ill-conditioned system of linear equations

References


Kahaner, D., Mouler, K., Nesh, S. (2001). Chislennye metody i programmnoe obespechenie. Moscow: Mir, 575.

Demmel', Dzh. (2001). Vychislitel'naya lineynaya algebra. Teoriya i prilozhenie. Moscow: Mir, 430.

Han, D., Zhang, J. (2007). A comparison of two algorithms for predicting the condition number. Sixth International Conference on Machine Learning and Applications (ICMLA 2007). doi: https://doi.org/10.1109/icmla.2007.8

Ebrahimian, R., Baldick, R. (2001). State Estimator Condition Number Analysis. IEEE Power Engineering Review, 21 (5), 64–64. doi: https://doi.org/10.1109/mper.2001.4311389

Nishi, T., Rump, S., Oishi, S. (2013). A consideration on the condition number of extremely ill-conditioned matrices. 2013 European Conference on Circuit Theory and Design (ECCTD). doi: https://doi.org/10.1109/ecctd.2013.6662260

BLAS (Basic Linear Algebra Subprograms). Available at: http://www.netlib.org/blas/sblat1

Li, H., Yang, H., Shao, H. (2010). A note on the perturbation analysis for the generalized Cholesky factorization. Applied Mathematics and Computation, 215 (11), 4022–4027. doi: https://doi.org/10.1016/j.amc.2009.12.009

The GNU Multiple Precision Arithmetic Library. Available at: https://gmplib.org/

Multiple Precision Integer Library (MPI). Available at: https://github.com/servo/nss/tree/master/lib/freebl/mpi

OpenSSL Cryptographic Toolkit. Available at: http://openssl.org

Large Integer Package. Available at: https://github.com/luckyaibin/BigInt/tree/master/freelip

Denis, T., Rose, G. (2006). BigNum Math. Implementing Cryptographic Multiple Precision Arithmetic. Syngress, 291. doi: https://doi.org/10.1016/b978-1-59749-112-9.x5000-x

Galovic, Ya. (2018). C++17 STL. Standartnaya biblioteka shablonov. Sankt-Peterburg: Piter, 432.

Kudin, V. I., Lyashko, S. I., Hritonenko, N. M., Yacenko, Yu. P. (2007). Analiz svoystv lineynoy sistemy metodom iskusstvennyh bazisnih matric. Kibernetika i sistemniy analiz, 4, 119–127.

Bohaienko, V. O., Kudin, V. I., Skopetskyj, V. V. (2009). Analysis of computational schemes for basic matrix method. Komp'yuternaya matematika, 2, 3–13.

Bogaenko, V. A., Kudin, V. I., Skopeckiy, V. V. (2009). Analiz vychislitel'nyh skhem modelirovaniya processov geogidrodinamiki. Probl. upr. i informatiki, 4, 62–72.

Bogaenko, V. A., Kudin, V. I., Skopeckiy, V. V. (2012). Ob osobennostyah organizacii vychisleniy na osnove metoda bazisnyh matric. Kibernetika i sistemniy analiz, 48 (4), 146–155.

Bogainenko, V., Kudin, V. (2014). Building preconditioners using basis matrix method. International journal Information Content and Processing, 1 (2), 182–187.

Knut, D. (2000). Iskusstvo programmirovaniya. Vol. 2. Moscow: Izdatel'skiy dom «Vil'yams», 788.

Krendall, R., Pomerans, K. (2011). Prostye chisla: Kriptograficheskie i vychislitel'nye aspekty. Moscow: URSS, 664.

Straustrup, B. (2006). Yazyk programmirovaniya C++. Special'noe izdanie. Sankt-Peterburg-Moscow: «Nevskiy dialekt» - «BINOM», 1104.

Kudin, V. I., Onotskyi, V. V. (2011). Rozvynennia tekhnolohiyi dovhoi aryfmetyky pry pobudovi alhorytmiv doslidzhennia zadachi liniynoho prohramuvannia. Zhurnal obchysliuvalnoi ta prykladnoi matematyky, 1, 77–84.


GOST Style Citations


Kahaner D., Mouler K., Nesh S. Chislennye metody i programmnoe obespechenie. Moscow: Mir, 2001. 575 p.

Demmel' Dzh. Vychislitel'naya lineynaya algebra. Teoriya i prilozhenie. Moscow: Mir, 2001. 430 p.

Han D., Zhang J. A comparison of two algorithms for predicting the condition number // Sixth International Conference on Machine Learning and Applications (ICMLA 2007). 2007. doi: https://doi.org/10.1109/icmla.2007.8 

Ebrahimian R., Baldick R. State Estimator Condition Number Analysis // IEEE Power Engineering Review. 2001. Vol. 21, Issue 5. P. 64–64. doi: https://doi.org/10.1109/mper.2001.4311389 

Nishi T., Rump S., Oishi S. A consideration on the condition number of extremely ill-conditioned matrices // 2013 European Conference on Circuit Theory and Design (ECCTD). 2013. doi: https://doi.org/10.1109/ecctd.2013.6662260 

BLAS (Basic Linear Algebra Subprograms). URL: http://www.netlib.org/blas/sblat1

Li H., Yang H., Shao H. A note on the perturbation analysis for the generalized Cholesky factorization // Applied Mathematics and Computation. 2010. Vol. 215, Issue 11. P. 4022–4027. doi: https://doi.org/10.1016/j.amc.2009.12.009 

The GNU Multiple Precision Arithmetic Library. URL: https://gmplib.org/

Multiple Precision Integer Library (MPI). URL: https://github.com/servo/nss/tree/master/lib/freebl/mpi

OpenSSL Cryptographic Toolkit. URL: http://openssl.org

Large Integer Package. URL: https://github.com/luckyaibin/BigInt/tree/master/freelip

Denis T., Rose G. BigNum Math. Implementing Cryptographic Multiple Precision Arithmetic. Syngress, 2006. 291 p. doi: https://doi.org/10.1016/b978-1-59749-112-9.x5000-x 

Galovic Ya. C++17 STL. Standartnaya biblioteka shablonov. Sankt-Peterburg: Piter, 2018. 432 p.

Analiz svoystv lineynoy sistemy metodom iskusstvennyh bazisnih matric / Kudin V. I., Lyashko S. I., Hritonenko N. M., Yacenko Yu. P. // Kibernetika i sistemniy analiz. 2007. Issue 4. P. 119–127.

Bohaienko V. O., Kudin V. I., Skopetskyj V. V. Analysis of computational schemes for basic matrix method // Komp'yuternaya matematika. 2009. Issue 2. P. 3–13.

Bogaenko V. A., Kudin V. I., Skopeckiy V. V. Analiz vychislitel'nyh skhem modelirovaniya processov geogidrodinamiki // Probl. upr. i informatiki. 2009. Issue 4. P. 62–72.

Bogaenko V. A., Kudin V. I., Skopeckiy V. V. Ob osobennostyah organizacii vychisleniy na osnove metoda bazisnyh matric // Kibernetika i sistemniy analiz. 2012. Vol. 48, Issue 4. P. 146–155.

Bogainenko V., Kudin V. Building preconditioners using basis matrix method // International journal Information Content and Processing. 2014. Vol. 1, Issue 2. P. 182–187.

Knut D. Iskusstvo programmirovaniya. Vol. 2. 3-e izd. Moscow: Izdatel'skiy dom «Vil'yams», 2000. 788 p.

Krendall R., Pomerans K. Prostye chisla: Kriptograficheskie i vychislitel'nye aspekty. Moscow: URSS, 2011. 664 p.

Straustrup B. Yazyk programmirovaniya C++. Special'noe izdanie. Sankt-Peterburg-Moscow: «Nevskiy dialekt» - «BINOM», 2006. 1104 p.

Kudin V. I., Onotskyi V. V. Rozvynennia tekhnolohiyi dovhoi aryfmetyky pry pobudovi alhorytmiv doslidzhennia zadachi liniynoho prohramuvannia // Zhurnal obchysliuvalnoi ta prykladnoi matematyky. 2011. Issue 1. P. 77–84.







Copyright (c) 2019 Volodymyr Kudin, Viacheslav Onotskyi, Ali Al-Ammouri, Lyudmyla Shkvarchuk

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061