Direct multiplicative methods for sparse matrices. Unbalanced linear systems.
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 attentio...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Institute of Computer Science
2016-12-01
|
| Series: | Компьютерные исследования и моделирование |
| Subjects: | |
| Online Access: | http://crm.ics.org.ru/uploads/crmissues/crm_2016_6/2016_08_02.pdf |
| _version_ | 1828544205271597056 |
|---|---|
| author | Anastasiya Borisovna Sviridenko |
| author_facet | Anastasiya Borisovna Sviridenko |
| author_sort | Anastasiya Borisovna Sviridenko |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T02:27:11Z |
| format | Article |
| id | doaj.art-ad42e4dbaebf4cb7934ec10a7d928947 |
| institution | Directory Open Access Journal |
| issn | 2076-7633 2077-6853 |
| language | Russian |
| last_indexed | 2024-12-12T02:27:11Z |
| publishDate | 2016-12-01 |
| publisher | Institute of Computer Science |
| record_format | Article |
| series | Компьютерные исследования и моделирование |
| spelling | doaj.art-ad42e4dbaebf4cb7934ec10a7d9289472022-12-22T00:41:31ZrusInstitute of Computer ScienceКомпьютерные исследования и моделирование2076-76332077-68532016-12-018683386010.20537/2076-7633-2016-8-6-833-8602518Direct multiplicative methods for sparse matrices. Unbalanced linear systems.Anastasiya Borisovna SviridenkoSmall 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.http://crm.ics.org.ru/uploads/crmissues/crm_2016_6/2016_08_02.pdfnumerically stable direct multiplicative methodsasymmetric linear systemssparse matrix storage formatparallel execution of matrix operations without unpackingminimization of fill the main rows of multiplierssparse matrices |
| spellingShingle | Anastasiya Borisovna Sviridenko Direct multiplicative methods for sparse matrices. Unbalanced linear systems. Компьютерные исследования и моделирование 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 |
| title | Direct multiplicative methods for sparse matrices. Unbalanced linear systems. |
| title_full | Direct multiplicative methods for sparse matrices. Unbalanced linear systems. |
| title_fullStr | Direct multiplicative methods for sparse matrices. Unbalanced linear systems. |
| title_full_unstemmed | Direct multiplicative methods for sparse matrices. Unbalanced linear systems. |
| title_short | Direct multiplicative methods for sparse matrices. Unbalanced linear systems. |
| title_sort | direct multiplicative methods for sparse matrices unbalanced linear systems |
| topic | 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 |
| url | http://crm.ics.org.ru/uploads/crmissues/crm_2016_6/2016_08_02.pdf |
| work_keys_str_mv | AT anastasiyaborisovnasviridenko directmultiplicativemethodsforsparsematricesunbalancedlinearsystems |