Method for parallelizing nonlinear tasks
he method of parallel solving of nonlinear equations bases on a realization of the solving by an information graph. The example for illustration of the method is considered.Problems in programming 2010; 2-3: 145-148
Збережено в:
| Дата: | 2026 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2026
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/885 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| _version_ | 1866844908795461632 |
|---|---|
| author | Paulin, O.N. Usova, T.I. |
| author_facet | Paulin, O.N. Usova, T.I. |
| author_institution_txt_mv | [
{
"author": "O.N. Paulin",
"institution": "Odessa National Polytechnic University"
},
{
"author": "T.I. Usova",
"institution": "Odessa National Polytechnic University"
}
] |
| author_sort | Paulin, O.N. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2026-06-01T06:02:58Z |
| description | he method of parallel solving of nonlinear equations bases on a realization of the solving by an information graph. The example for illustration of the method is considered.Problems in programming 2010; 2-3: 145-148 |
| first_indexed | 2026-06-02T01:00:42Z |
| format | Article |
| fulltext |
Паралельне програмування. Розподілені системи і мережі
© О.Н. Паулин, Т.И. Усова, 2010
ISSN 1727-4907. Проблеми програмування. 2010. № 2–3. Спеціальний випуск 145
УДК 519.688
МЕТОД РАСПАРАЛЛЕЛИВАНИЯ НЕЛИНЕЙНЫХ ЗАДАЧ
О.Н. Паулин, Т.И. Усова
Украина, г. Одесса, проспект Шевченко 1, а,
Одесский национальный политехнический университет, 65044
usovati@rambler.ru
Предлагается метод распараллеливания решения нелинейных уравнений (выражений), основанный на представлении процедуры
решения в виде информационного графа. Рассматривается пример, иллюстрирующий применение данного метода.
The method of parallel solving of nonlinear equations bases on a realization of the solving by an information graph. The example for
illustration of the method is considered.
Введение
Существует большое число задач, требующих выполнения объемных вычислений за приемлемое
расчетное время. Такие задачи возникают в следующих отраслях науки: физика, химия, биология, экономика,
математическая лингвистика и др. Использование последовательных алгоритмов не всегда эффективно и не
дает необходимой скорости вычислений. В связи с этим все больший упор в решении подобных задач делается
на распараллеливание существующих алгоритмов для их решения на многопроцессорных системах (кластерах).
Большинство задач, для решения которых разработаны параллельные алгоритмы, на данный момент
являются линейными. Решения нелинейных задач (несводящихся к линейным) на сегодня представлены
единичными случаями.
Таким образом, эти задачи требуют дополнительных исследований методов распараллеливания их
решений. Это можно осуществить, выполнив следующие этапы:
– выделение типовых структур нелинейных уравнений,
– построение методов распараллеливания для типовых структур нелинейных уравнений.
1. Известные виды нелинейных уравнений и методы их решений
В данной работе ограничимся алгебраическими и трансцендентными уравнениями.
Для того чтобы определиться с методами распараллеливания решений нелинейных задач, рассмотрим
сначала классификацию нелинейных уравнений [1]. На рис. 1 представлено все множество нелинейных
уравнений.
Известные следующие методы решений нелинейных уравнений:
– аналитические (полиномиальные уравнения невысоких степеней и частных видов уравнений) ;
– численные (локализация корней и их уточнение) .
К уравнениям, имеющим аналитическое решение, обычно относятся:
квадратные и сводящиеся к квадратным;
кубические;
уравнения четвертой степени;
уравнения пятой степени и выше, являющиеся однородными или возвратными;
некоторые виды трансцендентных уравнений.
При численном подходе задача о решении нелинейных уравнений разбивается на два этапа:
1. Локализация (отделение) корней, т. е. нахождение таких отрезков на оси аргумента, в пределах
которых содержится один единственный корень.
2. Уточнение корней, т. е. вычисление приближенных значений корней с заданной точностью.
Среди наиболее распространенных итерационных методов выделяют следующее: метод половинного
деления, метод хорд, метод простых итераций, метод Ньютона.
К итерационным методам решения нелинейных уравнений удобнее всего применять метод
пространственной декомпозиции расчетной области. Согласно ему распараллеливание производится путем
распределения вычислений на отрезках, по процессорам.
Отметим, что приведенная на рис. 1 классификация не отражает сложность нелинейных уравнений с
точки зрения возможности их распараллеливания. Более подходящим, по нашему мнению, является разделение
нелинейных уравнений по структурному признаку (рис. 2).
В этом случае все нелинейные уравнения по их структуре можно условно разбить на следующие виды:
аддитивные; мультипликативные; дробные; смешанные.
При этом функции φ(x), Q(x), P(x) могут быть как линейными, так и нелинейными. Их комбинации
позволяют получить любое нелинейное уравнение (выражение) из множества уравнений (выражений),
представленных на рис. 1.
mailto:usovati@rambler.ru
Паралельне програмування. Розподілені системи і мережі
146
Рис. 1. Виды нелинейных уравнений
Рис. 2. Разбиение нелинейных
уравнений по структуре
Рис. 3. Комбинированный метод решения нелинейного уравнения
2. Традиционное представление вычислительного процесса
Рассмотрим организацию вычислительного процесса при решении нелинейного уравнения
5sin)3( 2 xx , имеющего аддитивную структуру.
Для его решения применим комбинированный численный метод хорд-касательных [1].
Процедура заключается в попеременном уточнении левой и правой границ интервала локализации корня,
пока не получим значение, соответствующее заданной точности. При этом вычисление новой границы
осуществляется то методом хорд, то методом касательных (рис. 3).
Итак, в качестве исходных данных имеем нелинейное уравнение и отрезок [A, B] локализации корня Х.
С помощью метода хорд уточняется левая граница (точка С) отрезка локализации
)(
)(
i
i
i
Bf
Bf
BC
,
а с помощью метода касательных – правая (точка D)
)()(
)()(
ii
iiii
AfBf
AfBBfA
D
.
Можно было бы запустить итерационный процесс уже сейчас и осуществлять вычисления на отрезке
[D, C]. Чтобы ускорить вычисления, уменьшим отрезок в два раза, найдя его середину
2
CD
E
и определив,
на каком из отрезков [D, E] или [E, C] находится корень. Вычисление середины отрезка и определение, на
какой из половин находится корень, с помощью вычисления знаков функции на их концах, занимает меньше
времени, чем вычисления обычной итерации метода хорд-касательных. Выход из итерационного процесса
осуществляется при выполнении условия 1ii EE .
Паралельне програмування. Розподілені системи і мережі
147
3. Представление вычислительного процесса в виде информационного графа
К упомянутым методам решения нелинейных уравнений можно применить информационную модель
«операнд-операция» (рис. 4) в виде графа [2]. Здесь φ1, φ2, φ3, φ4 – компоненты нелинейного уравнения. Во
всех узлах выше самого нижнего уровня обычно расположены знаки операций. Это могут быть любые
операции, с помощью которых получается структура исходного уравнения.
Рис. 4. Пример информационного
графа для аддитивной структуры
уравнения
В частности, на рис. 4 представлена каскадная схема
суммирования. Соответственно удобнее всего такую
информационную модель применять для вычисления
числовых рядов. Но при вычислении числовых рядов, где
идет простое суммирование многих компонент, данная модель
может быть неэффективной при реализации ее, например, на
кластере, каждый узел которого делает одну операцию
сложения. Тогда время на пересылку промежуточных
результатов будет неизмеримо больше времени вычисления.
Применение кластера по такой схеме оказывается
нецелесообразным. Для вычисления числовых рядов на основе
данной информационной модели разработаны такие
модификации как каскадная схема с редукцией по сумме,
каскадно-последовательная, последовательно-каскадная и
каскадно-каскадная схемы [3]. Каскадная схема имеет вид
бинарного дерева, в листьях которого записаны компоненты
уравнения, а во всех остальных узлах – операции.
Использование подобной схемы возможно для распараллеливания численных алгоритмов решения
нелинейных уравнений. Исходя из этого, представим решение заданного нелинейного уравнения в виде
информационного графа (ИГ) (рис. 5).
Рис. 5. Информационный граф вычисления новых границ отрезка локализации
На самом нижнем уровне возможно параллельное вычисление значений функции в точках А и В и
производной в точке В. Для данного нелинейного уравнения вычисления функции 5)3(sin 2 xx в точке
p={Ai, Bi} и ее производной )3(2cos xx в точке Bi можно представить следующими информационными
графами (рис. 6).
Паралельне програмування. Розподілені системи і мережі
148
Рис. 6. Информационные графы вычисления значения заданной функции и ее производной
Для представления решения нелинейного уравнения в параллельной форме удобно использовать ИГ.
При этом предлагается следующий метод:
процесс решения представляется в виде процедуры;
операции, которые могут выполняться одновременно, представляются на ИГ на одном уровне;
проводятся связи между вершинами разных уровней по данным.
Идея информационного графа используется в существующей структурно-процедурной реализации
параллельных вычислений [4], которая предполагает разделение задачи на структурную и процедурную
компоненты. Структурная компонента реализуется в виде аппаратно реализуемых фрагментов вычислений –
кадров. Кадр – программно неделимый участок вычислений, представляющий собой структурно реализованный
подграф задачи, через который следует поток операндов. Вершины подграфа соответствуют элементарным
процессорам, настроенным на выполнение определенной арифметико-логической операции. Дуги подграфа
соответствуют информационным связям, реализованной в пространственной коммутационной системе.
Процедурная компонента задачи реализуется в виде единой программы, описывающей последовательность
смены кадров. Вычислительная система со структурно-процедурной организацией вычислений объединяет
достоинства традиционной фон-неймановской архитектуры (детерминизм программы) и архитектуры потока
данных (структурная реализация вычислений). Теперь, если обратиться к информационным графам,
представленным на рис. 5 и 6, то можно увидеть, что уровни, на которых располагаются узлы, представляют
собой кадры, внутри которых и должно осуществляться распараллеливание, т. е. это структурная компонента.
Прохождение всех уровней – процедурная компонента, которая должна быть реализована в качестве
последовательной программы.
Выводы
Предложенные структуры нелинейных уравнений (выражений) позволяют распараллеливать их решение
с помощью информационных графов, в виде которых должны быть представлены известные методы их
решения. Полученные результаты позволяют построить информационную технологию для автоматизации
распараллеливания решений нелинейных задач.
1. Бронштейн И. Н. Справочник по математике для инженеров и учащихся ВТУЗов / И.Н. Бронштейн, К.А. Семендяев – М.: Наука, 1981.
– 720 с.
2. Хокни Р. Параллельные ЭВМ. Архитектура, программирование и алгоритмы / Р. Хокни, К. Джессхоуп. Пер. с англ. Д.И. Абашкин. –
М.: Радио и связь, 1986. – 392 с.
3. Ефимов С.С. Обзор методов распараллеливания алгоритмов решения некоторых задач вычислительной дискретной математики /
С.С. Ефимов //Математические структуры и моделирование. – 2007. – Вып. 17. – С. 72–93
4. Левин И.И. Ресурсонезависимое параллельное программирование / И.И. Левин // Материалы междунар. научн.-техн. конф.
«Искусственный интеллект – 2002». – Таганрог: Изд-во ТРТУ, 2002. – С. 194–198.
|
| id | pp_isofts_kiev_ua-article-885 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2026-06-02T01:00:42Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/88/bfdfddbe1b8ef5f6b3e923fa078fb088.pdf |
| spelling | pp_isofts_kiev_ua-article-8852026-06-01T06:02:58Z Method for parallelizing nonlinear tasks Метод распараллеливания нелинейных задач Paulin, O.N. Usova, T.I. UDC 519.688 УДК 519.688 he method of parallel solving of nonlinear equations bases on a realization of the solving by an information graph. The example for illustration of the method is considered.Problems in programming 2010; 2-3: 145-148 Предлагается метод распараллеливания решения нелинейных уравнений (выражений), основанный на представлении процедуры решения в виде информационного графа. Рассматривается пример, иллюстрирующий применение данного метода.Problems in programming 2010; 2-3: 145-148 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-06-01 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/885 PROBLEMS IN PROGRAMMING; No 2-3 (2010); 145-148 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2010); 145-148 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2010); 145-148 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/885/938 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | UDC 519.688 Paulin, O.N. Usova, T.I. Method for parallelizing nonlinear tasks |
| title | Method for parallelizing nonlinear tasks |
| title_alt | Метод распараллеливания нелинейных задач |
| title_full | Method for parallelizing nonlinear tasks |
| title_fullStr | Method for parallelizing nonlinear tasks |
| title_full_unstemmed | Method for parallelizing nonlinear tasks |
| title_short | Method for parallelizing nonlinear tasks |
| title_sort | method for parallelizing nonlinear tasks |
| topic | UDC 519.688 |
| topic_facet | UDC 519.688 УДК 519.688 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/885 |
| work_keys_str_mv | AT paulinon methodforparallelizingnonlineartasks AT usovati methodforparallelizingnonlineartasks AT paulinon metodrasparallelivaniânelinejnyhzadač AT usovati metodrasparallelivaniânelinejnyhzadač |