Институт вычислительной математики
и математической геофизики

The International Conference on Computational Mathematics


Parallel numerical algorithms

Parallel algorithms for some discrete optimization problems

Zabinyako G.I.

Institute of Computational Mathematics and Mathematical Geophysics (Sib. div) (Novosibirsk)

Parallel algorithms for solution of problems of large dimensionality with sparse matrices of the integer linear and quadratic programming are considered. The algorithms are realized in FORTRAN, employing the parallel programming system MPI.

Parallelization is carried out by asynchronous execution on the processor elements of the algorithm with branching and boundaries with one-sided branching, for either linear or quadratic integer problems, respectively. Parallel algorithms enable us to decrease computer costs of solution (the total number of iterations in estimation problems carried out on all the processors) as compared to the subsequent ones, thus providing acceleration exceedind the the linear one. When carrying out, the processes are exchanging with brief messages against the background of execution of a large number of arithmetic operations.

The efficiency of parallel and sequential algorithms is compared on test problems using the computer MVS-1000/M.

Note. Abstracts are published in author's edition

Mail to Webmaster
|Home Page| |English Part| [SBRAS]
Go to Home
© 1996-2000, Siberian Branch of Russian Academy of Sciences, Novosibirsk
    Last update: 06-Jul-2012 (11:52:06)