Computer Research and Modeling
General information
Latest issue

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Computer Research and Modeling:

Personal entry:
Save password
Forgotten password?

Computer Research and Modeling, 2017, Volume 9, Issue 5, Pages 679–703 (Mi crm92)  

This article is cited in 2 scientific papers (total in 2 papers)


Direct multiplicative methods for sparse matrices. Newton methods

A. B. Sviridenko

FSEI of HPE Kuban State University, branch in Novorossiysk, Geroev Desantnikov st. 87, Novorossiysk, 353922, Russia

Abstract: We consider a numerically stable direct multiplicative algorithm of solving linear equations systems, which takes into account the sparseness of matrices presented in a packed form. The advantage of the algorithm is the ability to minimize the filling of the main rows of multipliers without losing the accuracy of the results. Moreover, changes in the position of the next processed row of the matrix are not made, what allows using static data storage formats. Linear system solving by a direct multiplicative algorithm is, like the solving with $LU$-decomposition, just another scheme of the Gaussian elimination method implementation.
In this paper, this algorithm is the basis for solving the following problems:
Problem 1. Setting the descent direction in Newtonian methods of unconditional optimization by integrating one of the known techniques of constructing an essentially positive definite matrix. This approach allows us to weaken or remove additional specific difficulties caused by the need to solve large equation systems with sparse matrices presented in a packed form.
Problem 2. Construction of a new mathematical formulation of the problem of quadratic programming and a new form of specifying necessary and sufficient optimality conditions. They are quite simple and can be used to construct mathematical programming methods, for example, to find the minimum of a quadratic function on a polyhedral set of constraints, based on solving linear equations systems, which dimension is not higher than the number of variables of the objective function.
Problem 3. Construction of a continuous analogue of the problem of minimizing a real quadratic polynomial in Boolean variables and a new form of defining necessary and sufficient conditions of optimality for the development of methods for solving them in polynomial time. As a result, the original problem is reduced to the problem of finding the minimum distance between the origin and the angular point of a convex polyhedron, which is a perturbation of the $n$-dimensional cube and is described by a system of double linear inequalities with an upper triangular matrix of coefficients with units on the main diagonal. Only two faces are subject to investigation, one of which or both contains the vertices closest to the origin. To calculate them, it is sufficient to solve $4n-4$ linear equations systems and choose among them all the nearest equidistant vertices in polynomial time. The problem of minimizing a quadratic polynomial is $NP$-hard, since an $NP$-hard problem about a vertex covering for an arbitrary graph comes down to it. It follows therefrom that $P=NP$, which is based on the development beyond the limits of integer optimization methods.

Keywords: NP-hard problem, sparse matrices, Newton methods, direct multiplication algorithm, the direction of descent, a new mathematical formulation, necessary and sufficient conditions of optimality, minimization pseudo Boolean functions, pseudo Boolean programming, linear programming.


Full text: PDF file (1660 kB)
Full text:
References: PDF file   HTML file

UDC: 519.85
Received: 20.02.2017
Revised: 22.09.2017

Citation: A. B. Sviridenko, “Direct multiplicative methods for sparse matrices. Newton methods”, Computer Research and Modeling, 9:5 (2017), 679–703

Citation in format AMSBIB
\by A.~B.~Sviridenko
\paper Direct multiplicative methods for sparse matrices. Newton methods
\jour Computer Research and Modeling
\yr 2017
\vol 9
\issue 5
\pages 679--703

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. B. Sviridenko, “Pryamye multiplikativnye metody dlya razrezhennykh matrits. Kvadratichnoe programmirovanie”, Kompyuternye issledovaniya i modelirovanie, 10:4 (2018), 407–420  mathnet  crossref
    2. A. B. Sviridenko, “O proektirovanii nulya na lineinoe mnogoobrazie, mnogogrannik i vershinu mnogogrannika. Nyutonovskie metody minimizatsii”, Kompyuternye issledovaniya i modelirovanie, 11:4 (2019), 563–591  mathnet  crossref
  • Computer Research and Modeling
    Number of views:
    This page:107
    Full text:54

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021