|
This article is cited in 4 scientific papers (total in 4 papers)
MATHEMATICAL MODELING AND NUMERICAL SIMULATION
Direct multiplicative methods for sparse matrices. Unbalanced linear systems
A. B. Sviridenko FSEI of HPE ‘Kuban State University’ branch in Novorossiysk,
87 Geroev Desantnikov st., Novorossiysk, 353922, Russia
Abstract:
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.
Received: 08.04.2016 Revised: 28.10.2016 Accepted: 09.11.2016
Citation:
A. B. Sviridenko, “Direct multiplicative methods for sparse matrices. Unbalanced linear systems”, Computer Research and Modeling, 8:6 (2016), 833–860
Linking options:
https://www.mathnet.ru/eng/crm32 https://www.mathnet.ru/eng/crm/v8/i6/p833
|
|