ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ НАХОЖДЕНИЯ ОБЩЕГО РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ* |
5 | |
2009 |
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ |
научная статья | 519.852.2 | ||
193-199 | полиэдр, многогранный конус, параллельный алгоритм, метод двойного описания |
Предлагается параллельная модификация метода двойного описания многогранного конуса. Приводятся результаты вычислительного эксперимента на многопроцессорной машине с общей памятью и сравнение с другими реализациями алгоритмов, решающих данную задачу. Эксперименты показали близкие к линейным результаты по масштабируемости. |
1 . Черников С.Н. Линейные неравенства. М.: Наука, 1968 2 . Stelling J., Klamt S., Bettenbrock K. et al. Metabolic network structure determines key aspects of functionality and regulation // Nature. 2002. V. 420. P. 190-193 3 . Cousot P., Halbwachs N. Automatic discovery of linear restraints among variables of a program // Conference Record of the Fifth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Tucson, Arizona. New York: ACM Press, 1978. P. 84-97 4 . Motzkin T.S., Raiffa H., Thompson G.L., Thrall R.M. The double description method // Contributions to the Theory of Games. Princeton: Princeton University Press, 1953 5 . Fukuda K., Prodon A. Double description method revisited // Lecture Notes in Computer Science. V. 1120. Springer-Verlag, 1996. P. 91-111 6 . Cdd Home Page: http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html. 7 . Avis D. lrs: A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm // Polytopes - Combinatorics and Computation. DMV Seminar Band 29, Birkhauser-Verlag, 2000. P. 177-198 8 . Barber C.B., Dobkin D.P., Huhdanpaa H.T. The Quickhull algorithm for convex hulls // ACM Trans. on Mathematical Software. 1996. V. 22. N. 4. P. 469-483 9 . Агафонов Е.А., Земскова Е.Л., Золотых Н.Ю. Параллельный алгоритм построения остова многогранного конуса и его программная реализация // Информационный бюллетень Ассоциации математического программирования № 10. Конференция «Математическое программирование и приложения» (тезисы докладов). Екатеринбург: УрО РАН, 2003. С. 15-16 10 . Золотых Н.Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // III Всероссийская конференция «Проблемы оптимизации и экономические приложения». Тезисы докладов. Омск, 2006. С. 108 11 . Skeleton 2 Home Page: http://www.uic. nnov.ru/~zny/skeleton. 12 . Золотых Н.Ю., Лялин С.С. Оптимизация одной модификации алгоритма двойного описания для многогранного конуса // Технологии Microsoft в теории и практике программирования. Материалы конференции. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2007. С. 333-336 13 . Лялин С.С. Параллельная модификация алгоритма двойного описания для многогранного конуса // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы Седьмой Международной конференции-семинара. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2007. С. 240-243 14 . Лялин С.С. Skeleton 3 - реализация параллельного алгоритма построения остова многогранного конуса // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы Восьмой Международной конференции-семинара. Казань: Изд-во КГТУ, 2008. С. 167-171 15 . Skeleton 3 Home Page: http://www. arageli.org/skeleton 16 . GNU Multiple Precision Arithmetic Library Home Page: http://gmplib.org 17 . Arageli Home Page: http://www.arageli.org. 18 . Skeleton 3 on-line demonstration: http://www. arageli.org/skeletondemo |