Direct multiplicative methods for sparse matrices. Unbalanced linear systems.

Sviridenko A.B.
 pdf (473K)  / List of references

Small practical value of many numerical methods for solving single-ended systems of linear equations with ill-conditioned matrices due to the fact that these methods in the practice behave quite differently than in the case of precise calculations. Historically, sustainability is not enough attention was given, unlike in numerical algebra ‘medium-sized’, and emphasis is given to solving the problems of maximal order in data capabilities of the computer, including the expense of some loss of accuracy. Therefore, the main objects of study is the most appropriate storage of information contained in the sparse matrix; maintaining the highest degree of rarefaction at all stages of the computational process. Thus, the development of efficient numerical methods for solving unstable systems refers to the actual problems of computational mathematics.

In this paper, the approach to the construction of numerically stable direct multiplier methods for solving systems of linear equations, taking into account sparseness of matrices, presented in packaged form. The advantage of the approach consists in minimization of filling the main lines of the multipliers without compromising accuracy of the results and changes in the position of the next processed row of the matrix are made that allows you to use static data storage formats. The storage format of sparse matrices has been studied and the advantage of this format consists in possibility of parallel execution any matrix operations without unboxing, which significantly reduces the execution time and memory footprint.

Direct multiplier methods for solving systems of linear equations are best suited for solving problems of large size on a computer — sparse matrix systems allow you to get multipliers, the main row of which is also sparse, and the operation of multiplication of a vector-row of the multiplier according to the complexity proportional to the number of nonzero elements of this multiplier.

As a direct continuation of this work is proposed in the basis for constructing a direct multiplier algorithm of linear programming to put a modification of the direct multiplier algorithm for solving systems of linear equations based on integration of technique of linear programming for methods to select the host item. Direct multiplicative methods of linear programming are best suited for the construction of a direct multiplicative algorithm set the direction of descent Newton methods in unconstrained optimization by integrating one of the existing design techniques significantly positive definite matrix of the second derivatives.

Keywords: numerically stable direct multiplicative methods, asymmetric linear systems, sparse matrix storage format, parallel execution of matrix operations without unpacking, minimization of fill the main rows of multipliers, sparse matrices
Citation in English: Sviridenko A.B. Direct multiplicative methods for sparse matrices. Unbalanced linear systems. // Computer Research and Modeling, 2016, vol. 8, no. 6, pp. 833-860
Citation in English: Sviridenko A.B. Direct multiplicative methods for sparse matrices. Unbalanced linear systems. // Computer Research and Modeling, 2016, vol. 8, no. 6, pp. 833-860
DOI: 10.20537/2076-7633-2016-8-6-833-860
URL: http://crm-en.ics.org.ru/journal/article/2518/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.
According to Crossref, this article is cited by:
  • Anastasiya Borisovna Sviridenko. Direct multiplicative methods for sparse matrices. Quadratic programming. // Computer Research and Modeling. — 2018. — V. 10, no. 4. — P. 407. DOI: 10.20537/2076-7633-2018-10-4-407-420
  • Anastasiya Borisovna Sviridenko. Direct multiplicative methods for sparse matrices. Newton methods. // Computer Research and Modeling. — 2017. — V. 9, no. 5. — P. 679. DOI: 10.20537/2076-7633-2017-9-5-679-703
Please note that citation information may be incomplete as it includes data from Crossref cited-by program partners only.
Views (last year): 20. Citations: 2 (RSCI).

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science