A parallel algorithm for solving strong separability problem on the basis of Fejer mappings

Authors

  • A.V. Ershova
  • I.M. Sokolinsky

Keywords:

strong separability
Fejer mappings
parallel programming
pseudoprojection
iterative process
pattern recognition

Abstract

An approach to solving the problem of separating two convex nonintersecting polyhedrons by the layer of maximum thickness is proposed. A parallel algorithm based on a method of using Fejer mappings is described. This algorithm admits an efficient implementation on the massively parallel multiprocessor systems. The results of computing experiments confirming the efficiency of the proposed approach are discussed. This work was supported by the Russian Foundation for Basic Research (project N 09-01-00546а).

New computational technologies

Downloads

Published

2011-11-03

Issue

Vol. 12 (2011): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biographies

A.V. Ershova

South Ural State University,
School of Electronic Engineering and Computer Science
• Lecturer

I.M. Sokolinsky

South Ural State University,
School of Electronic Engineering and Computer Science
• Associate Professor

References

  1. Боровкова В.А. Рынок ценных бумаг. СПб.: Питер, 2005.
  2. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Изд-во «Екатеринбург», 1999.
  3. Еремин И.И. Фейеровские методы сильной отделимости выпуклых полиэдральных множеств // Известия вузов. Сер. матем. 2006. N 12. 33-43.
  4. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979.
  5. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. 2009. N 1. 53-56.
  6. Ершова А.В., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Сер. «Матем. моделирование и программирование». 2011. N 37(254), вып.10. 12-21.
  7. Майоров С.И. Алгоритмическая торговля - за и против // Биржевое обозрение. 2010. N 1(73). 9-18.
  8. Boser B., Guyon I., Vapnik V. A training algorithm for optimal margin classifiers // Proc. of the 5th Annual ACM Workshop on Computational Learning Theory. Pittsburgh: ACM Press, 1992. 144-152.
  9. Dongarra J.J., Otto S.W., Snir M., Walker D. A message passing standard for MPP and workstations // Communications of the ACM. 1996. 39, N 7. 84-90.
  10. Forrest J.J. H., Tomlin J.A. Implementing the simplex method for the optimization subroutine library // IBM Systems Journal. 1992. 31, N 1. 11-25.
  11. Lampert A., Dale R., Paris C. Segmenting email message text into zones // Proc. of the 2009 Conference on Empirical Methods in Natural Language Processing: ACL and AFNLP. Singapore: World Scientific, 2009. 919-928.
  12. Markowitz H. Portfolio selection // J. of Finance. 1952. 7, N 1. 77-91.
  13. Zhang L., Zhu J., Yao T. An evaluation of statistical spam filtering techniques // Transactions on Asian Language Information Processing. 2004. 3, N 4. 243-269.