Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов

В статье предлагаются новые коллокационные блочные методы решения жестких систем обыкновенных дифференциальных уравнений с автоматическим управлением размером шага, которые изначально ориентированы на параллельную архитектуру. Основная идея, на которой базируется конструирование предлагаемых методов...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автор:	Дмитриева, О.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2012
Назва видання:	Штучний інтелект
Теми:	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/57699
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов / О.А. Дмитриева // Штучний інтелект. — 2012. — № 4. — С. 77-88. — Бібліогр.: 15 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-57699
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-576992025-02-23T18:25:46Z Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов Високоефективні алгоритми управління кроком на основі паралельних колокаційних блокових методів High-Performance Algorithms of Step Control Based on the Parallel Collocation Block Methods Дмитриева, О.А. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем В статье предлагаются новые коллокационные блочные методы решения жестких систем обыкновенных дифференциальных уравнений с автоматическим управлением размером шага, которые изначально ориентированы на параллельную архитектуру. Основная идея, на которой базируется конструирование предлагаемых методов, заключается в одновременном получении приближений точного решения во всех расчетных точках блока. У статті пропонуються нові колокаційні блокові методи розв’язання жорстких систем звичайних диференціальних рівнянь із автоматичним управлінням розміром кроку, які орієнтовані на паралельну архітектуру. Основна ідея, на якій базується конструювання пропонованих методів, полягає в одночасному одержанні наближень точного розв’язку у всіх розрахункових точках блоку. In this paper, we propose the new block collocation methods for solving stiff systems of ordinary differential equations with automatic step size, which initially are focused on the parallel architecture. The basic idea, which underlies the development of the proposed methods, is to obtain simultaneously the approximation of the exact solution in all the estimated points of the block. 2012 Article Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов / О.А. Дмитриева // Штучний інтелект. — 2012. — № 4. — С. 77-88. — Бібліогр.: 15 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/57699 004.272.2:519.63 ru Штучний інтелект application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
spellingShingle	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Дмитриева, О.А. Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов Штучний інтелект
description	В статье предлагаются новые коллокационные блочные методы решения жестких систем обыкновенных дифференциальных уравнений с автоматическим управлением размером шага, которые изначально ориентированы на параллельную архитектуру. Основная идея, на которой базируется конструирование предлагаемых методов, заключается в одновременном получении приближений точного решения во всех расчетных точках блока.
format	Article
author	Дмитриева, О.А.
author_facet	Дмитриева, О.А.
author_sort	Дмитриева, О.А.
title	Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов
title_short	Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов
title_full	Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов
title_fullStr	Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов
title_full_unstemmed	Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов
title_sort	высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2012
topic_facet	Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/57699
citation_txt	Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов / О.А. Дмитриева // Штучний інтелект. — 2012. — № 4. — С. 77-88. — Бібліогр.: 15 назв. — рос.
series	Штучний інтелект
work_keys_str_mv	AT dmitrievaoa vysokoéffektivnyealgoritmyupravleniâšagomnaosnoveparallelʹnyhkollokacionnyhbločnyhmetodov AT dmitrievaoa visokoefektivníalgoritmiupravlínnâkrokomnaosnovíparalelʹnihkolokacíjnihblokovihmetodív AT dmitrievaoa highperformancealgorithmsofstepcontrolbasedontheparallelcollocationblockmethods
first_indexed	2025-11-24T10:09:04Z
last_indexed	2025-11-24T10:09:04Z
_version_	1849665985720614912
fulltext	«Штучний інтелект» 4’2012 77 2Д УДК 004.272.2:519.63 О.А. Дмитриева Донецкий национальный технический университет МОНМС Украины, г. Донецк Украина, 83000, г. Донецк, ул. Артема, 58 Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов О.А. Dmitrieva Donetsk National Technical University MESYS of Ukraine and MAS of Ukraine, c. Donetsk Ukraine, 83000, c. Donetsk, Artema st., 58 High-Performance Algorithms of Step Control Based on the Parallel Collocation Block Methods О.А. Дмитрієва Донецький національний технічний університет МОНМС України, м. Донецьк Україна, 83000, м. Донецьк, вул. Артема, 58 Високоефективні алгоритми управління кроком на основі паралельних колокаційних блокових методів В статье предлагаются новые коллокационные блочные методы решения жестких систем обыкновенных дифференциальных уравнений с автоматическим управлением размером шага, которые изначально ориентированы на параллельную архитектуру. Основная идея, на которой базируется конструирование предлагаемых методов, заключается в одновременном получении приближений точного решения во всех расчетных точках блока. Ключевые слова: задача Коши, параллельные вычисления, точки коллокации, порядок аппроксимации. In this paper, we propose the new block collocation methods for solving stiff systems of ordinary differential equations with automatic step size, which initially are focused on the parallel architecture. The basic idea, which underlies the development of the proposed methods, is to obtain simultaneously the approximation of the exact solution in all the estimated points of the block. Key Words: Cauchy problem, parallel computing, collocation points, the order of approximation. У статті пропонуються нові колокаційні блокові методи розв’язання жорстких систем звичайних диференціальних рівнянь із автоматичним управлінням розміром кроку, які орієнтовані на паралельну архітектуру. Основна ідея, на якій базується конструювання пропонованих методів, полягає в одночасному одержанні наближень точного розв’язку у всіх розрахункових точках блоку. Ключові слова: задача Коші, паралельні обчислення, точки колокації, порядок апроксимації. Введение Основные усилия при параллельном моделировании динамических объектов большой размерности, описываемых системами обыкновенных дифференциальных уравнений (СОДУ), в настоящее время концентрируются на распараллеливании последовательных алгоритмов и программ [1], [2]. Дмитриева О.А. «Искусственный интеллект» 4’201278 2Д При этом исследуются только информационные взаимодействия смежных час- тей алгоритма, и не уделяется должного внимания общей информационной структуре задачи, что не позволяет создать масштабируемые параллельные программы [3], [4]. Еще одной проблемой при моделировании динамических объектов, особенно тех, которые формализуются жесткими системами ОДУ, является необходимость изменения шага интегрирования [5], [6]. Также актуальными являются вопросы соотнесения погрешностей результатов и времени, затрачиваемого на получение решения. Практически все известные в настоящее время численные методы с автома- тическим выбором шага интегрирования основаны на вычислении главного члена локальной ошибки и последующем выборе такого размера для очередного шага, который является максимальным для заданного предела локальной точности [5-8]. Но при этом возникает необходимость повторных вычислений в каждой точке, что приводит к значительному увеличению вычислительных затрат. Кроме того, жестко регламентируются пропорции сокращения шага [9], [10]. В статье предлагаются новые блочные методы решения систем обыкновенных дифференциальных уравнений, которые изначально ориентированы на параллельную архитектуру [11]. Основная идея, на которой базируется конструирование блочных методов для решения СОДУ на параллельных компьютерах, заключается в одновременном получе- нии приближений точного решения в точках, образующих блок. Поскольку точки внутри блока расположены регулярно, есть возможность опреде- ления и сопоставления локальных погрешностей во всех точках блока, в отличие от стадийных методов, где стадии, как правило, не совпадают, и сравнение ведется только по одной конечной расчетной точке 1nt  . Также непривлекательным является использование в компьютерах с распределен- ной памятью мелкозернистого параллелизма стадийных методов. Алгоритмы управления шагом, предлагаемые в статье, базируются на исполь- зовании коллокационных блочных одношаговых и многошаговых методов. Парал- лельный счет осуществляется в пределах одного цикла для всех точек блоков с размерностями s и s+1. Две нити вычислений проходят независимо, а необходимость в обменах возникает только после получения конечных результатов для блоков расчетных точек. Цель данной статьи состоит в создании коллокационных блочных расчетных схем, позволяющих обеспечивать автоматическое управление шагом интегрирования при моделировании динамических объектов в параллельных вычислительных системах. Генерация коэффициентов расчетных схем коллокационных блочных методов Для параллельной реализации численного решения задачи Коши 00 x)t(x)),t(x(,t(f'x  (1) можно обобщить подходы, предложенные в [12], [13], и основанные на одношаговом и многошаговом блочных методах. При этом не обязательным является требование, связанное с совпадением размерностей опорного и расчетного блоков. Будем счи- тать, что схема одношагового коллокационного блочного метода содержит s узлов в Высокоэффективные алгоритмы управления шагом... «Штучний інтелект» 4’2012 79 2Д рассчитываемом блоке (рис. 1) и одну опорную точку, многошагового – s узлов в рассчитываемом блоке при использовании вычисленных значений приближенного решения в m предшествующих блоку точках (рис. 2). Рисунок 1 – Шаблон разностной схемы одношагового s-точечного блочного метода Рисунок 2 – Шаблон разностной схемы m-шагового s-точечного коллокационного блочного метода Уравнения многошаговых разностных методов для блока из s точек при использовании вычисленных значений приближенного решения в m предшествующих блоку узлах, с учетом введенных выше обозначений, можно записать в виде: …1,2,=ns,,…1,2,=ifbua 1 s m1-j s m1-j j,nji,j,nji,      (2) Для одношаговых методов, представляющих частный случай (2), если m=1, разностные уравнения имеют вид …1,2,=ns,,…1,2,=ifbua 1 s 0j s 0j j,nji,j,nji,      (3) Формулы (3) определяют одношаговый s-точечный разностный метод. Обозначим матрицы коэффициентов системы уравнений (2) через s....,2),-(m-1),--(mjs,,…1,2,=i},b{B},a{A ji,ji,  Разобьем каждую из матриц на две части 0....,2),-(m-1),--(mjs,,…1,2,=i},b{B},a{A ji,1ji,1  s....,1,2,js,,…1,2,=i},b{B},a{A ji,2ji,2  Дмитриева О.А. «Искусственный интеллект» 4’201280 2Д Введем соответствующие вектора 0,...,2),-(m-1),--(mj},u{U jn,n  s,...,1,2,j,…1,2,=n},u{V j1,n1n   0,...,2),-(m-1),--(mj},f{F jn,n  s....,1,2,j,…1,2,=n},f{F j1,n1n   В векторной форме уравнение (2) будет иметь вид …1,2,=),( 121121 nFBFBVAUA nnnn    (4) Чтобы система однородных разностных уравнений, соответствующая (4), была линейно независима, потребуем, чтобы матрица 2A была невырожденной, и разрешим ее относительно 1nV  ),( 11   nnnn GFDFQUV  (5) где .BAG,BAD,AAQ 2 1 21 1 21 1 2   Задав стартовые значения, полученные, например, с помощью явных стадийных схем, необходимо на каждом последующем этапе решить нелинейное уравнение (5), определив последовательно вектора ...,V,V 21 . Представление блочных разностных многошаговых многоточечных уравнений в виде (5) будем называть канонической формой их записи. Получим коэффициенты уравнений, позволяющие представлять методы (2) в канонической форме (5). Каждое i-е разностное уравнение s,…1,2,=i),fgfd(uqu 0 m-1=j s 1=j j,nji,j,nji, 0 m-1=j j,nji,i,n     (6) содержит 2m+s неизвестных коэффициентов jn,ji, d,q , 0),...,2m(),1m(j  .s,...,2,1j,g jn,  Для их определения следует использовать 2m+s уравнений условий аппроксимации. Выражения для невязок на решении x(t) исходного дифференциаль- ного уравнения имеют вид ,'g'd)q( 1 0 m-1=j s 1=j ,ji,,ji, 0 m-1=j ,ji,,,    jnjnjninin xxxxr  (7) где ),jt(xx ni,n  ,xx ,nm,n 01  ),jt(f)jt('x'x nni,n   .'x'x ,nm,n 01  Для каждого i-го уравнения потребуем его аппроксимации в точке 0,nt ),jt(xx 0,nj,n  ).x,jt(f)jt('x'x j,n0,n0,nj,n   Раcкладывая )jt(xx 0,nj,n  и )jt('x'x 0,nj,n  в ряды Тейлора в окрест- ности точки 0,nt , подставляя эти разложения в выражение (7), группируя члены с одинаковыми степенями по  , а затем приравнивая нулю коэффициенты при l , получим систему уравнений Высокоэффективные алгоритмы управления шагом... «Штучний інтелект» 4’2012 81 2Д ,s,...,2,1i,1q 0 m-1=j ji,  ,ig)dq(j s 1=j ji, 0 m-1=j j,iji,   .,...,3,2,g)(q s 1=j 1 ji, 0 m-1=j 1 ,ji,    pl l i jjg l j l ll ji l (8) Поскольку каждое i-е разностное уравнение (6) содержит 2m+s неизвестных коэффициентов, то максимальный порядок аппроксимации рассматриваемого m-ша- гового s-точечного разностного метода равен p=2m+s-1. Каноническая форма одношаговых многоточечных уравнений будет иметь соответственно вид s.,…1,2,=i),fgfd(uu s 1=j j,nji,0,ni,00,ni,n   (9) Коэффициенты разностных уравнений (6) и (9) можно определить, решая систему (8) для общих многошаговых блочных методов, учитывая их частный вид, или интегро-интерполяционным методом. Для этого строится интерполяционный многочлен )t(L 1sm  с узлами интерполяции mj,nt  и соответствующими им значе- ниями сеточной функции s…,0,1,…2),-1),-(m--(m=j,u j,n . Находятся производные полученного интерполяционного многочлена в узлах сетки .s,...,2,1i,t i,n  Приравняв их соответствующим значениям правой части дифференциального уравнения, получим разностные уравнения для блока. Используя изложенный выше подход, можно сформировать каноническую систему уравнений для любых значений параметров m и s. В частности, для параметров m=3, s=2, p=7 и шаблона, приведенного на рис. 3, система будет выглядеть следующим образом                                                   85 f24 85 f144 1360 f9 170 f57 85 f806 85 f336 85 f36 170 f297 170 f207 1360 f141 v v 2,n1,n 2,n1,n 0,n1,n2,n 0,n1,n2,n 2,n 1,n  . 17 u199 17 u128 17 u54 136 u135 17 u27 136 u55 0,n1,n2,n 0,n1,n2,n                  Рисунок 3 – Шаблон разностной схемы коллокационного 3-шагового 2-точечного блочного метода Дмитриева О.А. «Искусственный интеллект» 4’201282 2Д Управление шагом при интегрировании блочными методами Рассмотрим решение задачи (1) одношаговым коллокационным блочным методом (9) с числом расчетных точек s. Выделим две системы процессорных узлов, на которых запустим параллельные процессы. Первая система узлов будет обеспечивать параллельную реализацию одношагового коллокационного блочного s-то- чечного метода, что потребует s процессорных элементов для получения значений s.,…1,2,=i,u i,1n На второй системе узлов будет осуществляться реализация одно- шагового коллокационного блочного s+1-точечного метода c получением значений 1.s,…1,2,=i,i,1n  Поскольку методы являются неявными, каждый временной шаг подразумевает проведение некоторого количества итераций, обеспечивающих требуемую локальную точность. Реализация обоих методов будет осуществляться автономно, что обеспечит крупнозернистость вычислений. Размерность вычислительного поля может быть представлена двумя вариантами. В первом случае это могут быть кольцевые топологии, количество процессорных элементов в которых совпадает с размерностью блоков s и s+1 соответственно, во втором случае вычислительные поля представляют собой решетки процессорных элементов (рис. 4). Первая решетка с s (количество точек в блоке) столбцами и N (количество уравнений в системе) строками, у второй решетки размерность процессорного поля – N1)s(  . Если используется кольцевое вычислительное поле, размерность которого совпадает с размерностью блока, каждый процессорный элемент закрепляется за рассчитываемой точкой блока для всех уравнений системы. Для осуществления итераций по (9) в каждом i-м процессорном элементе, обеспечивающем вычисления s-точечным методом, должны быть размещены соответствующие коэффициенты s1,2,...,js,,…1,2,=i,b,a ij,i  , а также значения элементов вектора правых частей системы в последней точке предшествующего блока, которые будут считаться начальными для следующего. Для группы процессорных элементов, которые обеспечивают решение s+1-то- чечным методом, соответствующие коэффициенты 1s1,2,...,j1,s,…1,2,=i,b,a ij,i  . В случае, если используется решетка процессорных элементов, позиция каж- дого элемента в строке определяет порядковый номер уравнения в системе, для которого ведется расчет, а номер элемента в столбце определяет рассчитываемую точку блока. Поскольку вычисления проводятся для блоков точек, которые расположены регулярно, есть возможность сопоставления решений, полученных методами c раз- ными порядками точности в s-совпадающих расчетных точках sn2n1n t,...,t,t  . Если норма вектора расхождений не превосходит заданную глобальную точность вычислений s,...,2,1i,tolu i,ii,i  , за основу берется решение, полученное коллокационным блочным s+1-точечным методом 1.s,…1,2,=i,i,1n  Рассчитывается новое значение шага new Высокоэффективные алгоритмы управления шагом... «Штучний інтелект» 4’2012 83 2Д                                   1s 1 i,ii,i 1nnew u min,faxmaxmax,faxmin    и по результатам расчета s+1-точечным методом формируется новый вектор опор- ных точек. Рисунок 4 – Алгоритм управления шагом интегрирования на решетке процессорных элементов Если норма вектора расхождений не превосходит заданную локальную точность вычислений, т.е. s,...,2,1i,utol i,ii,i   , за основу берется решение, Дмитриева О.А. «Искусственный интеллект» 4’201284 2Д полученное коллокационным блочным s-точечным методом, s.,…1,2,=i,u i,1n Рас- считывается новое значение шага new , и новый вектор опорных точек формируется по результатам расчета s-точечным методом. Если полученное решение не обеспе- чивает заданную локальную точность, от шага необходимо отказаться, сократив его на величину, задаваемую параметром faxmin. Параллельное управление шагом для задачи (1) многошаговым коллокационным блочным методом (6) с числом опорных точек m и расчетных s не будет иметь принципиальных различий с подходами, рассмотренными выше. Однако возникает необходимость в формировании начальных данных для расчета очередного блока значений. Для выполнения следующего шага нужно обеспечить доступ каждого про- цессорного элемента к значениям правых частей в опорных точках блока. Кроме того, для осуществления итераций по (6) в каждом i-м процессорном эле- менте, обеспечивающем вычисления s-точечным m-шаговым методом, должны быть раз- мещены соответствующие коэффициенты m1,2,...,ls,1,2,...,js,,…1,2,=i,b,a li,j,i  , а также значения элементов векторов правых частей системы в m точках предше- ствующего блока, которые будут считаться начальными для следующего. Для группы процессорных элементов, которые формируют решение s+1-точечным методом, со- ответствующие коэффициенты m1,2,...,l1,s1,2,...,j1,s,…1,2,=i,b,a li,j,i  . Поскольку максимальный порядок p аппроксимации рассматриваемого m-ша- гового s-точечного разностного метода, который равен p=2m+s-1, не обеспечивает абсолютной устойчивости метода [12], при генерации расчетных коэффициентов необходимо сократить предельное значение, введя параметр q<p. Тогда, в зави- симости от значения нормы вектора расхождений, будет изменяться расчетная схема определения шага интегрирования и новое значение шага new определяется с учетом поправки на порядок q аппроксимации. Реализация тестовых задач на основе алгоритмов управления размером шага Для экспериментов на мультиосновных машинах использовался программный интерфейс MathLink среды параллельных вычислений в Mathematica Wolfram Research, обеспечивающий возможность параллельного поиска решений как на локальной машине, так и в сетевом масштабе. Также параллельная реализация осуществлялась на кластере NeClus MIMD- архитектуры с распределенной памятью. Кластер состоит из 93-х вычислительных узлов, узла управления (Front Node), системы коммутации в составе двух гигабитных Ethernet-коммутаторов (Switch HP Procurve). В качестве тестовой выбрана жесткая задача из [9] ,xxt2'x 4 5 21  ,*10' 4 )1(5 2 3 xetx x  (10) ,xt2'x 43  44 xlnt2'x  c начальными условиями 1)0(x)0(x)0(x)0(x 4321  и с известными точными решениями ,e)t(x )tsin( 1 2  ,e)t(x )tsin(5 2 2  ,1)tsin()t(x 2 3  ).tcos()t(x 2 4  Высокоэффективные алгоритмы управления шагом... «Штучний інтелект» 4’2012 85 2Д Поиск решения проводился на интервале [0, 2.5]. Из-за разных масштабов решения, особенно в середине интервала интегрирования, потребовалось использовать проце- дуру управления шагом, основанную на рассмотренных коллокационных блочных методах (рис. 5а). Рассматривались реализации на основе одношаговых коллокационных блочных методов с числом расчетных точек 2 и 3, и многошаговых – с числом опор- ных точек 2 и расчетных 2 и 3. Шаги осуществлялись параллельно, продвижение вдоль оси времени проходило сразу на размерность блока, обеспечивающего задан- ную точность, к середине интервала интегрирования заметно сокращение шага. Вторая тестовая задача из [14] ,xx'x 211  ,xx100'x 212  (11) ,xx100'x 433  x100x10000'x 434  , c начальными условиями 0)0(x,1)0(x,0)0(x,1)0(x 4321  , имеет проблемы при численном интегрировании в начале отрезка (рис. 5б) а) б) Рисунок 5 – Управление шагом интегрирования для тестовых задач (10) и (11) Тестовые жесткие задачи третьего типа [15] возникают при дискретизации уравнения диффузии методом прямых. Количество уравнений в системе N может быть сколь угодно велико и определяется размерностью расчетной сетки, которая вводится для решения исходного уравнения в частных производных. Система (1) решалась на интервале [0, 4], правые части системы имеют вид                                            )t( 0 0 0 0 1Nx 2 1 1 2 0 0 0 0 0 0 0 0 00.1210 000121 000012 1N))t(x(,t(f 22         , (12) где        texp1sintexp2sin)t(   ,         2 1 cos2/2cos , Дмитриева О.А. «Искусственный интеллект» 4’201286 2Д                                  1N 1 cos11N2, 1N 2 cos11N2 22  . Точные решения     N,...,2,1i,texp 1N 1 sintexp 1N 2 sin)t(xi                 . На графиках приведены численные результаты решения (рис. 6а) и погрешности (рис. 6б), полученные для системы с N = 8, а также диаграмма параллельного управления шагом (рис. 7). 1 2 3 4 t  0.7  0.6  0.5  0.4  0.3  0.2  0.1 x1, x2, x3, x4, x5, x6, x7, x8 1 2 3 4 t  5. 10  7 5. 10  7 1. 10  6 Error x1, x2, x3, x4, x5, x6, x7, x8 а) б) Рисунок 6 – Численное решение и погрешности системы (12) Рисунок 7 – Управление шагом интегрирования для тестовой задачи (12) Выводы В статье рассмотрены вопросы разработки коллокационных блочных методов решения задачи Коши, ориентированных на использование в параллельных вычис- лительных системах с распределенной памятью. Основная идея, на которой базировалось конструирование блочных методов для решения СОДУ на параллельных компью- терах, заключалась в одновременном получении приближений точного решения в точках, образующих блок. Параллельный счет осуществлялся в пределах одного цикла для всех точек блоков с размерностями s и s+1. Две нити вычислений проходили независимо, и необходимость в обменах возникала только после получения конечных результатов для блоков расчетных точек. Структура предлагаемых методов позволила построить алгоритмы автоматического управления шагом интегрирования, что явля- ется особенно актуальным при моделировании объектов, которые описываются жесткими или плохо обусловленными системами уравнений. Поскольку точки внутри блока расположены регулярно, стало возможным определение и сопоставление локальных Высокоэффективные алгоритмы управления шагом... «Штучний інтелект» 4’2012 87 2Д погрешностей во всех точках блока, в отличие от стадийных методов, где стадии, как правило, не совпадают, и сравнение ведется только по одной конечной расчетной точке. На основе предложенных алгоритмов управления размером шага реализованы тестовые задачи, численное решение которых обеспечивает заданную точность с максимально возможным при этом шагом интегрирования. Для экспериментов на мультиосновных машинах использовался программный интерфейс MathLink среды параллельных вычислений в Mathematica Wolfram Research, обеспечивающий возможность параллельного поиска решений как на локальной ма- шине, так и в сетевом масштабе. Литература 1. Firsova A. Dynamic System Simulation. Robust algorithms of state estimation of dynamic lumped parameters systems / A. Firsova, O. Dmitrieva. – Lambert Academic Publishing, 2011. – 92 p. 2. Zanariah A.M. Solving Large Systems of Ordinary Differential Equations on Parallel Computer/ A.M. Zanariah, M.B. Suleiman // Journ. of Scientific Research. –2009. – Vol. 29, № 4. – P. 491-501. 3. Дмитриева О.А. Параллельное моделирование жестких систем на основе диагонализации полной матрицы / О.А. Дмитриева // Искусственный интеллект. – 2011. – № 4. – С. 46-53. 4. Feldman L.P. Embedded block parallel methods for initial Cauchy problem numerical solution / L.P. Feldman, I.A. Nazarova, O.A. Dmitrieva [et al.] // Proceedings of DNTU. – 2010. – № 1. –P. 12-17. 5. Soderlind G. Digital filters in adaptive time-stepping / G. Soderlind // ACM Trans. Math. Softwar. – 2003. – Vol. 29. – P. 1-26. 6. Дмитриева О.А Параллельное моделирование динамических объектов с автоматическим выбором шага на основе экстраполяционных методов / О.А. Дмитриева // Радіоелектронні і комп’ютерні системи. – 2012. – № 6 (58). – С. 312-317. 7. Дмитриева О.А. Параллельное моделирование жестких динамических систем диагонально- неявными методами с адаптацией шага / О.А. Дмитриева, Я.А. Куприй // Наукові праці ДонНТУ. ІКОТ-2010. Випуск 12(165). – Донецьк : ДонНТУ. – 2010. – С. 111-116. 8. Дмитриева О.А. Управление шагом в блочных диагонально-неявных методах решения обыкновенных дифференциальных уравнений / О.А. Дмитриева // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика та обчислювальна техніка» (ІКОТ-2010). Випуск 11(164). – Донецьк : ДонНТУ. – 2010. – С.14-18. 9. Хайрер Э. Решение обыкновенных дифференциальных уравнений. Жесткие задачи / Э. Хайрер, Г. Ваннер. - М. : Мир, 1999. – 685 с. 10. Burrage K. Parallel iterated method based on Variable stepsize Multistep Runge-Kutta methods of Radau type for stiff problems / K. Burrage, H. Suhartanto // Adv. Comput. Math. – 2000. – Vol. 13. – P. 257-270. 11. Дмитриева О.А. Упрощение итераций при параллельной реализации неявных методов решения систем обыкновенных дифференциальных уравнений / О.А. Дмитриева // Наукові праці Донецького національного технічного університету. Серія «“Інформатика, кібернетика та обчислювальна техніка» (ІКОТ-2011). Випуск 13(185). – Донецьк : ДонНТУ. – 2011. – С. 13-18. 12. Дмитриева О.А. Разработка обобщенных коллокационных блочных методов / О.А. Дмитриева // Сборник трудов конференции МОДЕЛИРОВАНИЕ – 2012. 16 -1 8 мая 2012, г. Киев. – Киев : Институт проблем моделирования в энергетике, 2012. – С. 434-437. 13. Дмитрієва О.А. Генерація стійких блокових методів для розв’язання жорстких диференційних рівнянь і їх систем / О.А. Дмитрієва // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика та обчислювальна техніка» (ІКОТ-2011). Випуск 14(188). – Донецьк : ДонНТУ. – 2011. – С. 36-43. 14. Enright W.H. Software for ordinary and delay differential equations: Accurate discrete approximate solutions are not enough / W.H. Enright //Applied Numerical Mathematics. – 2006. – Vol. 56, № 3-4. – P. 459-471. 15. Butcher J.C. ARK methods for stiff problems / J.C. Butcher, C.N. Rattenbury // Applied Numerical Mathematics. – 2005. – Vol. 53, № 1. – P. 165-181. Literatura 1. Firsova A, Dmitrieva O. Dynamic System Simulation. Robust algorithms of state estimation of dynamic lumped parameters systems. – Lambert Academic Publishing. 2011. 92 p. Дмитриева О.А. «Искусственный интеллект» 4’201288 2Д 2. Zanariah A. M., Journ. of Scientific Research. 2009. Vol. 29. № 4. P. 491-501. 3. Dmitrievа O. A. Iskusstvennyj intellect. 2011. № 4. S. 46-53. 4. Feldman L., Nazarova I., Dmitrieva O., Mikhaylova T. Proceedings of DNTU. 2010. №1. P.12-17. 5. Soderlind G. ACM Trans. Math. Softwar. 2003. Vol. 29. P. 1-26. 6. Dmitrieva O. A. Radіoelektronnye komp'yuternye systemy. 2012. № 6 (58). S. 312-317. 7. Dmitrieva O. A., Kupriy J.A. ІKOT. 2010. №12 (165). S. 111-116. 8. Dmitrievа, O. A. ІKOT-2010. № 11 (164). S.14-18. 9. Hayrer E. Wanner. G. Solution of ordinary differential equations. Tough task. - Springer-Verlag, 1999.685s. 10. Burrage, K. Adv. Comput. Math. 2000. Vol. 13. P. 257-270. 11. Dmitrieva O. A. ІKOT-2011. № 13 (185). S. 13-18. 12. Dmitrieva O.A. Sbornik trudov conferencii MODELIROVANIE. 2012. 16-18 May. Kiev. S.434-437. 13. Dmitrіeva O.A. ІKOT-2011. № 14 (188). S. 36-43. 14. Enright W.H. Applied Numerical Mathematics. 2006. Vol. 56. № 3-4. P. 459-471. 15. Butcher J. C. Applied Numerical Mathematics. 2005. Vol. 53. № 1. P. 165-181.. RESUME О.А. Dmitrieva High-Performance Algorithms for Step Control Based on the Parallel Collocation Block Methods The paper discussed the issue of the design of collocation methods for solving Cauchy problem, which are oriented for using in parallel computers with distributed memory. The main idea, which underlines the development of the block methods for solving SODE on parallel computers, was to obtain simultaneously the approximation of the exact solution at points forming the block. A parallel count was performed within one cycle for all points of blocks with dimensions of s and s +1. Two flows of computation were performed independently, and the need for exchanges occurred only after obtaining the final results for blocks of the estimated points. The structure of the proposed methods allowed us to design the algorithms for automatic control of integration step, which is particularly relevant for modeling objects, which are described by hard or ill-conditioned systems of equations. Since the points are located regularly inside the block, it became possible to identify and compare local errors at all points of the block, in contrast to the stage methods, where the stages are usually not the same, and the comparison is made only by one final design point. On the basis of the proposed algorithms of step size control the test problems were implemented, the numerical solution of which provides the required accuracy with the maximum possible integration step. For the experiments on multi-based machines, MathLink programming interface of parallel computing environment in Mathematica Wolfram Research was used, which provides the possibility of parallel search for solutions on the local machine as well as in the network scale. Статья поступила в редакцию 05.06.2012.

Высокоэффективные алгоритмы управления шагом на основе параллельных коллокационных блочных методов

Репозитарії

Схожі ресурси