Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zh. Vychisl. Mat. Mat. Fiz., 2009, Volume 49, Number 8, Pages 1369–1384 (Mi zvmmf4732)  

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

Parallel implementation of Newton's method for solving large-scale linear programs

V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, M. Kh. Nguen

Computing Center, Russian Academy of Sciences, ul. Vavilova 40, Moscow, 119333, Russia

Abstract: Parallel versions of a method based on reducing a linear program (LP) to an unconstrained maximization of a concave differentiable piecewise quadratic function are proposed. The maximization problem is solved using the generalized Newton method. The parallel method is implemented in C using the MPI library for interprocessor data exchange. Computations were performed on the parallel cluster MVC-6000IM. Large-scale LPs with several millions of variables and several hundreds of thousands of constraints were solved. Results of uniprocessor and multiprocessor computations are presented.

Key words: linear programming, generalized Newton's method, unconstrained optimization, parallel computations.

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

English version:
Computational Mathematics and Mathematical Physics, 2009, 49:8, 1303–1317

Bibliographic databases:

UDC: 519.658
Received: 24.02.2009

Citation: V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, M. Kh. Nguen, “Parallel implementation of Newton's method for solving large-scale linear programs”, Zh. Vychisl. Mat. Mat. Fiz., 49:8 (2009), 1369–1384; Comput. Math. Math. Phys., 49:8 (2009), 1303–1317

Citation in format AMSBIB
\Bibitem{GarGolEvt09}
\by V.~A.~Garanzha, A.~I.~Golikov, Yu.~G.~Evtushenko, M.~Kh.~Nguen
\paper Parallel implementation of Newton's method for solving large-scale linear programs
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2009
\vol 49
\issue 8
\pages 1369--1384
\mathnet{http://mi.mathnet.ru/zvmmf4732}
\zmath{https://zbmath.org/?q=an:1183.90297}
\transl
\jour Comput. Math. Math. Phys.
\yr 2009
\vol 49
\issue 8
\pages 1303--1317
\crossref{https://doi.org/10.1134/S096554250908003X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000269218300003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-70350590959}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf4732
  • http://mi.mathnet.ru/eng/zvmmf/v49/i8/p1369

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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. V. Panyukov, V. V. Gorbik, “Parallelnye realizatsii simpleks-metoda dlya bezoshibochnogo resheniya zadach lineinogo programmirovaniya”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 2011, no. 9, 107–118  mathnet
    2. Evtushenko Yu.G., Tret'yakov A.A., “Elementary proof of constructive versions of the tangent direction theorem and the implicit function theorem”, Dokl. Math., 85:1 (2012), 23–28  crossref  mathscinet  zmath  zmath  isi  elib  elib  scopus
    3. Yu. A. Kochetov, A. V. Plyasunov, “Genetic local search the graph partitioning problem under cardinality constraints”, Comput. Math. Math. Phys., 52:1 (2012), 157–167  mathnet  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    4. I. E. Kaporin, “Using Chebyshev polynomials and approximate inverse triangular factorizations for preconditioning the conjugate gradient method”, Comput. Math. Math. Phys., 52:2 (2012), 169–193  mathnet  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    5. A. I. Golikov, Yu. G. Evtushenko, “Generalized Newton method for linear optimization problems with inequality constraints”, Proc. Steklov Inst. Math. (Suppl.), 284, suppl. 1 (2014), 96–107  mathnet  crossref  mathscinet  isi  elib
    6. L. D. Popov, “Experience in organizing hybrid parallel calculations in the Evtushenko–Golikov method for problems with block-angular structure”, Autom. Remote Control, 75:4 (2014), 622–631  mathnet  crossref  isi
    7. A. I. Golikov, Yu. G. Evtushenko, “Regularization and normal solutions of systems of linear equations and inequalities”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 102–110  mathnet  crossref  mathscinet  isi  elib
    8. G. A. Amirkhanova, A. I. Golikov, Yu. G. Evtushenko, “On an inverse linear programming problem”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 21–27  mathnet  crossref  mathscinet  isi  elib
    9. Behboodi-Kahoo M., Ketabchi S., “Parallel Implementation of Augmented Lagrangian Method Within l-Shaped Method For Stochastic Linear Programs”, Filomat, 31:3 (2017), 799–808  crossref  mathscinet  isi  scopus
    10. A. B. Sviridenko, “Pryamye multiplikativnye metody dlya razrezhennykh matrits. Lineinoe programmirovanie”, Kompyuternye issledovaniya i modelirovanie, 9:2 (2017), 143–165  mathnet  crossref
    11. B. V. Ganin, A. I. Golikov, Yu. G. Evtushenko, “Projective-dual method for solving systems of linear equations with nonnegative variables”, Comput. Math. Math. Phys., 58:2 (2018), 159–169  mathnet  crossref  crossref  isi  elib
    12. V. I. Zabotin, Yu. A. Chernyaev, “Newton's method for minimizing a convex twice differentiable function on a preconvex set”, Comput. Math. Math. Phys., 58:3 (2018), 322–327  mathnet  crossref  crossref  isi  elib
    13. L. F. Petrov, “Search for periodic solutions of highly nonlinear dynamical systems”, Comput. Math. Math. Phys., 58:3 (2018), 384–393  mathnet  crossref  crossref  isi  elib
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:768
    Full text:321
    References:53
    First page:23

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022