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

Ващенко Геннадий Васильевич

РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ОДНОШАГОВЫХ МЕТОДОВ И КОМПЛЕКСА ПРОГРАММ ДЛЯ РЕШЕНИЯ ЗАДАЧ ХИМИЧЕСКОЙ КИНЕТИКИ И БИОЛОГИИ

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 2 [;]др 20:2

Красноярск 2012

005015372

Работа выполнена в Институте вычислительного моделирования СО РАН и Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Сибирский государственный технологический университет» (г. Красноярск)

Ведущая организация: ФГБОУ ВПО «Тюменский государственный университет»

Защита диссертации состоится 9 марта 2012 г. в 14:00 часов на заседании диссертационного совета ДМ 212.099.06 при Сибирском федеральном университете по адресу: г. Красноярск, ул. Киренского, д. 26, в ауд. УЛК-115

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета.

Автореферат разослан «6» февраля 2012 г.

Научный руководитель: доктор физико-математических наук,

профессор

Новиков Евгений Александрович

Официальные оппоненты: доктор физико-математических наук,

профессор

Добронец Борис Станиславович

доктор физико-математических наук, профессор

Задорин Александр Иванович

Ученый секретарь диссертационного совета

Р.Ю. Царев

Общая характеристика работы

Работа относится к актуальной проблематике применения параллельных вычислительных систем в научных исследованиях.

Актуальность темы обусловлена необходимостью эффективного численного решения жестких и не жестких задач большой размерности, возникающих при математическом моделировании биологических и химических процессов. Данная проблема возникает при изучении процессов функционирования генной сети и проникновения радиоактивных меток в ткань живого организма. Для решения таких задач необходимо использование многопроцессорных вычислительных систем и применение в расчетах экономичных и надежных численных методов. В настоящей работе эффективность алгоритмов интегрирования достигается построением методов с экономичным способом оценки аналога глобальной ошибки и дополнительным контролем устойчивости явных методов. Контроль устойчивости позволяет применять явные методы для решения больших задач умеренной жесткости. Сейчас параллельные алгоритмы с контролем точности и устойчивости, а также на основе ¿-устойчивых (ш,&)-методов с контролем аналога глобальной ошибки отсутствуют. Это обстоятельство делает разработку подобных алгоритмов для моделирования биологических и химических процессов актуальной задачей.

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

1. Построение и реализация параллельных алгоритмов явных методов типа Рунге-Кутты с первого по третий порядок с контролем точности вычислений и устойчивости численной схемы для решения задачи многостадийного синтеза вещества без ветвления и стоков. Анализ эффективности алгоритмов, разработка тестовых задач и исследование комплекса параллельных программ на многопроцессорной вычислительной системе кластерной архитектуры. Исследование комплекса программ на задаче типа реакции-диффузии, возникающей в химической кинетике.

2. Разработка и реализация параллельного алгоритма переменного шага на основе 1-устойчивого (2,1)-метода второго порядка, в котором для контроля точности используется оценка аналога глобальной ошибки. Анализ эффективности алгоритма и проверка программного комплекса на тестовых задачах, сравнение с вариантом алгоритма с постоянным шагом.

3. Применение комплекса параллельных программ на основе явных и Ь-устойчивого методов для моделирования процесса функционирования генной сети и решения задачи проникновения помеченных радиоактивными метками антител в пораженную опухолью ткань живого организма.

Научная новизна. На основе явных методов типа Рунге-Кутты с первого по третий порядок точности созданы параллельные алгоритмы интегрирования переменного шага для решения задачи синтеза вещества, включая задачу моделирования функционирования генной сети. Разработаны параллельные алгоритмы на основе Z-устойчивого (2,1)-метода второго порядка с оценкой аналога глобальной ошибки применительно к решению задачи проникновения антител в ткань живого организма. Проведен анализ эффективности созданных параллельных алгоритмов. Создан комплекс параллельных программ для решения жестких и не жестких задач на вычислительных системах кластерной архитектуры.

Теоретическая значимость. Построены и обоснованы параллельные алгоритмы интегрирования переменного шага на основе схем типа Рунге-Кутты с первого по третий порядок и i-устойчивого (2,1)-метода второго порядка для решения жестких и не жестких задач. Получены оценки эффективности, ускорения и соотношения изоэффективности, связывающие размерности исходной задачи и параллельной вычислительной системы.

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

Методы исследования. Применяется теория разностных схем и дифференциальных уравнений, используются методы математического анализа, теории графов, параллельного программирования, линейной алгебры, вычислительного эксперимента и математического моделирования. Эффективность параллельных алгоритмов интегрирования проверяется с помощью численных экспериментов.

Апробация работы. Результаты диссертации докладывались на Всероссийской конференции "Проблемы информатизации региона" (Красноярск, 2009); на XI Международной конференции "Информационно-вычислительные технологии и их приложения" (Пенза, 2009); на IV Международной конференции "Параллельные вычислительные технологии ПаВТ'2010" (Уфа, 2010); на XV Всероссийской конференции "Информационные и математические технологии в науке и управлении" (Иркутск, 2010); на V Международной конференции "Аналитические и численные методы моделирования естественнонаучных и социальных проблем"( Пенза, 2010); на I Международной конференции "Computer Technology and Applications" (Vladivostok, 2010); на VII Межрегиональной школе-семинаре "Распределенные и кластерные вычисления»" (Красноярск, 2010); на ежегодной Международной научной конференция "Приоритетные

направления развития науки, технологий и техники "(Хургада, Египет, 2010); на семинарах ИВМ СО РАН и СибГТУ (Красноярск).

Работа поддержана грантами РФФИ (проекты 08-01-00621 и 11-0100106) и грантом Президента (проект НШ-3431.2008.9).

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

На защиту выносится: •Параллельные алгоритмы интегрирования с контролем точности вычислений и устойчивости численных формул на основе схем типа Рунге-Кутты с первого по третий порядок точности, а также параллельный алгоритм на основе ¿-устойчивого (2,1)- метода второго порядка с выбором шага на основе оценки аналога глобальной ошибки.

• Комплекс параллельных программ для вычислительных систем кластерной архитектуры.

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

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

Публикации. Основные публикации по теме диссертации включают 18 работ, из них 5 в журналах по списку ВАК, 5 в Российских рецензируемых изданиях и 8 в сборниках трудов Всероссийских и Международных конференций.

Общая характеристика диссертации. Работа состоит из введения, четырех глав, заключения, библиографического списка из 92 наименований. Общий объем работы составляет 132 стр.

Содержание работы

Во введении сформулирована цель работы, обоснованы актуальность темы, приведено краткое описание содержания работы по главам.

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

Вторая глава посвящена построению и реализации параллельных алгоритмов интегрирования переменного шага на основе явных методов типа Рунге-Кутты с применением схем с первого по третий порядок точности. В первом параграфе сформулирован параллельный по пространству алгоритм интегрирования.

Для численного решения задачи Коши

y' = f{t,y),y{t0) = y*\t0<t<tk, (1)

y' = f(y),y{t0) = /°\t0<tïtk, (2)

где у и / - гладкие N- мерные вектор - функции на [f0, применяются явные методы типа Рунге-Кутты вида

m /-1

/=1 у=1

m i-1

+ К?), (4)

/ = 1 7=1

где hn - шаг интегрирования, К]"', 1 <i<m- стадии метода, m - число стадий. Коэффициенты dmi, у,, Ду, 1 <i<m, 1 < j < i -1 определяют свойства

точности и устойчивости (3) и (4). Для упрощения выкладок все исследования проводились для методов (4), но все построенные численные схемы можно использовать для решения неавтономных систем. Для этого достаточно в (3) подставить у„ 1 < г < m, определенные следующим образом,

7=1

При распараллеливании по s уравнениям (4) записывается в виде

2<i<m, (5)

j'i

y("+1) = y^ + hYd K["\ym=u ,

i=I

yf\ , < e 1<7<р; 0" -1) ■ 5 +1 < < j ■ s , s=[N/p],

N - размерность системы (2), p - число процессоров или размерность вычислительной системы.

Алгоритм 1. Пусть для численного решения задачи (2) используется метод (4). Если известно решение У"' в точке tm то каждый процессор proc(j), 1 <j<p, будет содержать у-ю часть компонент вектора ,

после выполнения следующего алгоритма.

Шаг 1. В каждомproc(j), 1 <j <р\ (j'-l)-s +1 < sj < j-s:

а) выполнить recv(y(^,h\ 1,...,р); б) вычислить /}"\ум);

в) вычислить (7^ =ySjin) ; г) выполнить send{a["]Sj; 1, 2,...,р)\

д) выполнить recv(aj"^ ;1,2,...,р).

Шаг 2. а) вычислить = (ст,(п)); б) вычислить ;

в) выполнить er!;"}; 1,2,... ,р); г) выполнить recv(er™ ;1, 2,...,р).

Шаг /я. Вычислить .

т

Шаг/я+1. а) вычислить = У^ + й^^Д^;

Ы1

б) сохранить у^ = y{s"*l); в) выполнитьsend(yls"+i); 1, 2,...,р).

Шаг т+2. Если необходимо, то из proc( 1) вывести решение У"+1). Шаг ш+3. Выполнить следующий шаг интегрирования.

Во втором параграфе на основе одностадийной формулы (4) построен метод первого порядка точности с неравенством для контроля точности вычислений. Сформулирован параллельный алгоритм интегрирования. Приближенное решение задачи (2) определяется по формуле

+ (6) Показано, что для контроля точности на шаге имеет место неравенство

0.5h\]f„+l-fJ<£, (7)

где £ - требуемая точность расчетов, ||-|| - некоторая норма в RN, f„ и /„+) -значения правой части системы (1) или (2) соответственно в точках t„ и t„+\. Параллельный аналог схемы (6) с контролем точности имеет вид

Н = uSsJ У11 /(1 ^ 1 +Г)}' ^11 = - f' (8)

\ijüpt(j-\ys+\<.sj<.j-s, где s = N/p, если N кратнор и s-[N/p]+q в противном случае.

Алгоритм 2. Пусть для решения (2) используется метод (8), и известно решение У"' в точке t„ с шагом hn. Тогда для получения значения У"+1) в точке i„+1 справедлив параллельный алгоритм, в котором на каждом процессоре proc(j) формируется своя j-я часть у["*1) вектора решения.

Шаг 1. В каждомproc(j), 1 <j<p; (M)-s +1 < Sj < j-s: а) выполнить recv( У"', h\ l,...,p); б) вычислить

в) вычислить yl"+l) = у1* + Ж,(">; г) выполнитьsend{y{s"+1); 1,2,...,р);

д) выполнить гесу(у{"*^; \,...,р)\ е) вычислить /^+,)(У"+1>);

ж) определить =1 /,<"+1) - /*> І /(I І+Г);

з)определить ¡¿(л)||. =шах{|^,).1+1|,|^;_\).1+2|,...,|(5'<;)|};

и) ВЫПОЛНИТЬ 5ЄИС?(|5(я)| , 1).

Шаг 2. В ргос{\):

а) выполнить ассиг_соп1:го1 (); б) вывести вектор у{п+1). Шаг 3. Выполнить следующий шаг интегрирования.

Получены показатели ускорения и эффективности параллельного алгоритма.

В третьем параграфе на основе двухстадийной численной формулы построен метод второго порядка точности с неравенством для контроля точности и устойчивости вычислений. Сформулирован параллельный алгоритм интегрирования. Численные формулы имеют вид

/»'> =уч+о.5(АГ1м + К™), К\п)=кЛу(л)), КУ=ЬпДум + К[п)). (9) Получены неравенство для контроля точности вычислений

0.5^"'-^"'¡^ в (10)

и оценка максимального собственного числа матрицы Якоби ул = /гЯи тах. Неравенство для контроля устойчивости имеет вид

у„ = 2шах(| - I /1 - к}? |) < 2, (11)

где числу 2 примерно равна длина интервала устойчивости схемы (9), к^ и компоненты векторов А",'"', К{2"} и вспомогательного вектора

= Стадия К™ совпадает с вектором К\п) для следующего

шага, и поэтому не приводит к увеличению вычислительных затрат. Параллельный аналог метода (9) с контролем точности вычислений и устойчивости численной схемы записывается в виде

^/'"'(Л +Кк£], *£> =/,«), є™ =|к\"1 -

И=и-ії^ < I V I Ц • N=Н) *£' <12>

/=і

1/1^ І}- КІ^шахН»'} <2, (13) ергові і<т

Алгоритм 3. Пусть для решения системы (1) используется метод (9). Если известно решение У"' в точке і„, то каждый ргосЦ), 1 </<р будет

содержать j-ю часть вектора численного решения, ys"*\ (f-l)-s+l<Sj<j-s,

после выполнения алгоритма.

Шаг 1. В каждомprocij), \<j <р\ (j-l)-s +1 <Sj< j-s:

а) выполнить recv{y"^, hn\ 1 ,...,p)\ б) вычислить f^\y{"])\

в) вычислить сг'2"^ =ySjln)+hnk; г) выполнитьsend(<j\n)^; 1,2,...,/?); д) выполнить recv( CTj"^ ; 1,2,..., p). Шаг 2. Вычислить Шаг3. Вычислить =|к™

Шаг 4. а) определить ¡£-л|. = ^ ^ max || е| /(| у'"' | +r)J;

б) выполнить 5еш/(||£я|| ; 1);

Шаг 5. В proc{ 1) выполнить accur_control ():

а) выполнить recv(\\sn ||у;2,...,р)\ б) определить ||г„| = 0.5ЛЛтах||£/,||^|;

в) вычислить значение q\ по формуле q( = (г/||^„||),/2.

г) qi < 1, то есть точность не выполняется, то перевычислить hn по формуле 7z„ = q\hnyipr=Q\

д) выполнить send(h„,pr;2,...,p); е) при q\ > 1 шаг hn прежний, pr= 1; ж) выполнить send (hn,pr; 2,...,/?);

Шаг 6. а) выполнить recv(h„, pr, 1);

б) если рг = 0, то переходим в пункт в) шага 1, иначе на шаг 7.

2

Шаг 7. а) вычислить = >/п,+ ;

' w

б) выполнитьsend(y{"*V]; 1,2,...,р); в) выполнить recv(^°+1);l, 2,...,р). Шаг 8. Вычислить = hJs{y{"+>)). Шаг 9. Вычислить у™ =

Шаг 10. а) определить lv I. = max jv'"11; б) выполнить send(|v„|.; 1);

1 U-l)S+l£Sj<J S I J ) ' J

Шаг 11. Вproc(l) выполнить accur_control () и stable_control(). Шаг 12. а) выполнить recv(hn,pr\ 1);

б) если pr = 0, то переходим в пункт в) шага 1, иначе на шаг 13. Шаг 13. Выполнить следующий шаг интегрирования.

В четвертом параграфе на основе трехстадийной численной формулы построен метод третьего порядка точности с неравенством для контроля точности вычислений и устойчивости численной схемы. Сформулирован параллельный алгоритм интегрирования. Численные формулы имеют вид

/"+1> =у>+(*,<"> + (14)

к[п) =ИЛУ(") ), к? = /¡„/(У"' +0.5/Г1(")) Хъп) = А„ЛУ"' - +2К1"}). Построены неравенство для контроля точности вычислений

и оценка максимального собственного числа = ИпХп тах матрицы Якоби. Неравенство для контроля устойчивости имеет вид

у„ = 0.5шах(| *,<;> - 2+ *£> | /1 *£> - |) < 2.5, где числом 2.5 ограничен интервал устойчивости схемы (14), к(2"' и к компоненты векторовЛ^"', А^и ^"'соответственно. Параллельный вариант метода (14) с контролем точности и устойчивости записывается в виде

-О. <=/;,«).

< Н*£! 1Ы1/|+4

|К|| = й„тах{|К|у)<б5, 1 К '

Параллельный алгоритм формулируется аналогично алгоритму для двухстадийной схемы (алгоритм 3).

Проанализирована эффективность построенных алгоритмов. Прогнозируемый шаг /¡л+, вычисляется по формуле

К+\ =шах[/г„,тт(/г°с,/г11)], (15)

где Ип - последний успешный шаг интегрирования, 1гас - прогнозируемый шаг по точности, И" - прогнозируемый шаг по устойчивости. Формула (15) показывает, что контроль устойчивости используется как ограничитель на рост шага, что позволяет сгладить последствия грубости оценок собственных чисел матрицы Якоби. Если шаг по устойчивости меньше последнего успешного, то он не будет уменьшен в силу возможной грубости оценки максимального собственного числа. В то же время шаг не будет и увеличен, потому что не исключается возможность неустойчивости численной схемы.

Если шаг по устойчивости должен быть уменьшен, то в качестве следующего шага будет применяться последний успешный шаг hn. Данная формула позволяет стабилизировать поведение шага на участке установления решения, где определяющую роль играет устойчивость.

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

Третья глава посвящена построению параллельных алгоритмов интегрирования на основе ¿-устойчивого (2,1)-метода второго порядка точности. В первом параграфе приводятся основные сведения о (т,к)-методах. Во втором конструируются последовательный и параллельный алгоритмы на равномерной сетке. В третьем параграфе построены последовательный и параллельный алгоритмы переменного шага. Изучаются (от,£)-методы при к= 1 и т=2, то есть

У"+,) =/° +PlK\"4PlK?, DnK^=hJn, (16)

Показано, что при значениях коэффициентов а=1-0.5^2,р\=а ир2-\-а схема (16) является L-устойчивой и имеет второй порядок. Покомпонентная форма записи (16) при найденных значениях для а,р\-цр2 имеет вид

j=1 j=i Параллельный вариант формул (16) записывается в виде

' 1 J ' m=1 1 1 т=1 J J

1 <j<P, (j-l)-S + \<Sj<j-S.

Матрица D„ размещается строчными блоками размером s, причем s = N/p, если N кратно р и s=[N/p]+q в противном случае.

Во втором параграфе сформулирован параллельный алгоритм на равномерной сетке w„. Построены функции Par_LU_Decompos{) и Par_LU_Solution(), в которых реализованы параллельные версии декомпозиции матрицы D„ и нахождения векторов К\п) и К2{"\

В третьем параграфе получено неравенство Ц^,1"' -^л>|<£ для

контроля точности вычислений и построен параллельный алгоритм переменного шага.

Алгоритм 4. Пусть для численного решения системы (2) используется (2,1)-метод с контролем точности, и известно решение У"' в точке 1„ с шагом кп. Тогда для получения значения У"+1) в точке ¡п+\ справедлив параллельный алгоритм, в котором на каждом процессоре ргосЦ) формируется своя /-я часть вектора решения .

Шаг 1. В каждомргос(/'), 1 <у <р\ +1 < Sj <

а) выполнить г ее у( , к, 1,..., р)\ б) вычислить ;

в) вычислить матрицу Якоби1 <]<р; Шаг 2. Сформировать матрицу Оп = Е - ак /п'. Шаг 3. Разложить матрицу Д,, Д, = Раг_Ьи_Оесотроз§. Шаг 4. Вычислить АГ/"^ Раг_Ш_Бо1иНопО. Шаг 5. Вычислить Кг("\ К2м=Раг_Ш_8о1Шюп() Шаг 6. В каждом ргос{)'), 1 <] <р\ (/'-1)-^ +1 < 5,- < у-5: д) определить I =| ^ _ ^ <■> | /(| ^ | +г);

ж) определить II Ц,.= тах{| 1,| 1,...,| |};

з) выполнить 5м ||у, 1).

Шаг 7. В ргос(1)\

а) выполнить ассиг_со1йго1 (); б) вывести вектор У"+1). Шаг 8. В каждомргос(/), 1 <у <р; (/'—+1 < < j■s:

а) вычислить + А*^;

б) выполнить зепй{У"+1); \,...,р).

Шаг 9. Выполнить следующий шаг интегрирования.

В четвертом параграфе построены оценки ускорения, эффективности и соотношение изоэффективности.

Реализации параллельных вариантов алгоритма зависят от свойств и размерности исходной задачи, сложности правой части исходной системы, способов организации вычисления матрицы Якоби и факторизации (выбора ведущих элементов) матрицы £)„, но строго последовательный характер вычисления коэффициентов К\(п) и останется неизменным. Построенное соотношение изоэффективности, связывающее размерность исходной системы и размерности параллельной вычислительной системы может быть использовано, как инструмент сравнения различных параллельных алгоритмов решения одной и той же задачи Коши (2,1)-методом, и подходов к выбору и построению алгоритмов вычисления матрицы Якоби, факторизации Ц, и нахождения стадий.

В четвертой главе описан комплекс программ рагСЮЕ для численного моделирования задач, описываемых жесткими и не жесткими системами дифференциальных уравнений. Приводятся результаты моделирования двух

практических задач. В первом параграфе описан комплекс параллельных программ. Структурная схема комплекса приведена на рис. 1.

Рисунок 1- Состав комплекса параллельных программ

На рис. 1. приведены параллельные реализации алгоритмов: рагИК1 - с постоянным шагом на основе явной схемы 1-го порядка; рагШОАС - с переменным шагом на основе явной схемы 1-го порядка; рагКК2 - с постоянным шагом на основе явной схемы 2-го порядка; раг1*К2АС - с переменным шагом на основе явной схемы 2-го порядка с контролем точности;

рагШС2АС8Т - с переменным шагом на основе явной схемы 2-го порядка с контролем точности и устойчивости;

рагГОКЗ - с постоянным шагом на основе явной схемы 3-го порядка; рагШСЗАС - с переменным шагом на основе явной схемы 3-го порядка с контролем точности;

рагМСЗАСБТ - с переменным шагом на основе явной схемы 2-го порядка с

контролем точности и устойчивости;

раг21 - с постоянным шагом на основе (2,1)-схемы;

раг21АС — с переменным шагом на основе (2,1)-схемы;

рагМ_1асоЫ - формирование матрицы Якоби в (2,1)-схеме;

рагЬи_Бесотро8 - параллельная ¿{/-факторизация;

рагЬи_8о1ийоп - для нахождения стадий в (2,1)-схеме;

11_раг^п, I, у, 1) - для вычисления правой части системы дифференциальных

уравнений; разрабатывается пользователем для каждой конкретной задачи.

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

Здесь х„ 1<г'<Д^, - концентрации промежуточных стадий синтеза вещества; хы - концентрация конечной формы вещества (продукт синтеза); функции Х^) и ^хц) определяют законы инициации синтеза вещества и его утилизацию. Решение задачи определялось при условиях: к^г(М-\)/г, т -

суммарное время протекания из первого состояния в 7У-е; ,где а>0, /3>0, у>\ и в>0 -параметры.

Наиболее эффективным на данной задаче является параллельный алгоритм на основе одностадийной формулы с неравенством для контроля точности вычислений и реализованный в программе рагМС1АС для расчетов на кластере ИВМ СО РАН. Ниже для нее приведены детальные результаты расчетов. Временные затраты приведены в табл. 1, показатели ускорения Бр -в табл. 2, поведение нормы локальной погрешности при требуемой точности е= 10"2 и размерности N=500 и N=10000 -на рис. 2 и 3.

Таблица 1

Временные затраты на шаге выполнения рагИЮАС_

Число процессоров N=500 1,сек 1 000 1,сек Ы= 10000 1,сек ^ 100 000 1,сек N° 1 000 000 1,сек

1 7.86-10"6 1.63-10'5 1.84-10"4 4.8-10"3 5.1-10"2

2 3.81-10*4 3.42-10"4 7.41 -10"4 3.5-10"3 2.43-10"2

4 6.63104 4.87-10"4 1.37-10'3 2.32-10"3 1.32-Ю-2

8 1.19-10"3 9.17-10"4 1.64-10'3 2.12-10"3 6.18-10"3

10 2.02-10"3 1.52-10"3 1.97-10'3 2.52-10"3 9.74-10"3

20 2.34-10*3 1.91-10"3 2.32-10'3 , 2.83-10"3 5.4-10'3

Таблица 2 Показатели ускорения ^ выполнения рагИК! АС

Ускорение, N=500 1 000 № 10000 100 000 К= 1 000 000

& 0.022 0.05 0.25 1.4 2.1

Я» 0.012 0.03 0.12 2.07 3.9

& 0.0063 0.019 0.61 1.85 4.51

0.004 0.01 0.1 1.9 5.2

Зго 0.003 0.009 0.08 1.8 9.4

' Лихошвай В. А., Матушкин Ю. Г., Фадеев С. И. Задачи теории функционирования генных сетей // Сиб. журн. индустр. математики. -2003.- Т. 6.- №2(14).-С. 64-80.

S 0.04 : У 0.031 0 02 "

fr 0.01 ■ о

с о-

1

6 7 8 9 временные узлы сетки

10 11 12

2854

Рисунок 2- Поведение нормы локальной погрешности при заданной е = 10 и размерности системы N=500. Минимальное значение 5.9-10'6

S.« I 0 03 S § g 0.02

S I I 0.01 -

v..

временные узлы сетки

Рисунок 3- Поведение нормы локальной погрешности при заданной е = 10" и размерности системы 10000. Минимальное значение 1.4-10'2

Анализ результатов расчетов показал, что коммуникационные затраты составляют значительную часть общего времени решения. Увеличение числа процессоров не всегда приводит к уменьшению временных затрат.

В третьем параграфе приводятся результаты численного моделирования проникновения антител в ткань живого организма. Модель описывается системой одномерных уравнений реакции-диффузии2

ди д2и , ду

— = —1г-кт, — = -кш,

д,X дх2 Э/

которые возникают из химической реакции А+В—>С с константой скорости реакции к, где А - антитело с радиоактивной меткой, реагирующее с субстратом В - тканью, пораженной опухолью. Концентрации А и В обозначены через и и V соответственно. Изучается полубесконечная пластина, внутри которой субстрат В равномерно распределен. Реагент А, попадая на поверхность пластины, начинает проникать в нее. Для моделирования проникновения исходные уравнения рассматриваются в полосе 5У={(х,г): 0<х<со, 0<КТ] с начальными и(х, 0)=0, у(х, 0)=уо, х>0, и граничными и(О,*)=0(г), 0<«Т, условиями, где у0 константа. После

2 Mazzia F., Magherini C. Test Set for Initial Value Problem Solvers II Department of Mathematics, University of Bari and INdAM, Research Unit of Bari, release 2.4,2008.

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

= у), А0) = *, уеЛ™, 0<^<20, (17)

си

где N - задаваемый параметр. Функция/ определяется формулами г -а Уг»\~Уц-г . п Уу-ъ ~ 2Уц-\ + Уг)+\ , ,

~ ' 2д!£ 3 ^у-Лу. Л/ - ^гу^уч.

где агу = 2(/А^- 1)3с2, Р) = - 1)4с2,1 < у < Л^, = \Ш, у.,(() = ф(0,

Угы+1 = = (0,у0,0,у0) ...,0,у0)г. Функция <¿(0 = 2 при 0<?<5

и 0(г) = 0 при 5</<20, то есть ф{1) имеет разрыв первого рода в точке t=5. В качестве параметров к, Уо и с использовались £=100, Уо=1 и с-4. Задача о нахождении разрыва функции (¡5(0 при ?=5 возлагалась на алгоритм управления шагом. Интегрирование осуществлялось с точностью е=10-2 на промежутке [0,20] с начальным шагом 10"5. Наиболее эффективным на данной задаче является программа рагШОАСвТ. Ниже для нее приведены детальные результаты расчетов. Временные затраты приведены в табл. 3, показатели ускорения - в табл. 4, поведение нормы локальной

погрешности при требуемой точности £=10~2 и размерности Л-400 и N=1200 - на рис. 4 и 5.

Таблица 3

Число N=400 N=800 1200 И= 2000

процессоров 1,сек 1:,сек 1,сек 1,сек

1 3.6-10'5 7.45-10'5 1.16-10"4 1.91-10"4

2 3.21-10'5 3.83-10"5 0.92-10"4 1.21-10"4

4 3.43-10"4 1.62-Ю-4 0.68-10"4 0.63-10"4

8 5.8-10"4 5.31-10"4 0.76-10"4 0.48-10"4

10 6.1-10"3 1.48-10"3 0.82-10^ 0.83-10"4

20 6.8-10"3 2.7-10"3 0.91-10"4 0.9-10"4

Таблица 4

Показатели ускорения 5Р выполнения рагШС2АС8Т

Ускорение, 5„ N=400 _ 800 № 1200 2000

0.49 0.65 0.9 1.57

¿4 0.1 0.45 1.7 2.93

& 0.04 0.14 1.52 3.9

0.01 0.05 1.41 2.3

5м 0.005 0.02 1.27 2.1

2. 3 п. О

§ е-

й « и О

г я

0.12 0.1 0.08 -0.06 • 0.04 ■ 0.02 -0

V'Г-Г-Г-Г-Г-

N «V <Ь Ь <э Ь А

• п'Ъ"

• .оГ

временные узлы сетки

Рисунок 4- Поведение нормы локальной погрешности при заданной е = 10" и размерности системы N=400. Минимальное значение 4.-10'6

3 ч. Е

О. 'К £

§ 1 ё

I § 1

X « о.

I % I

0.12 0.1 0.08 0.06 -0.04 -0.02 -, 0 <1

\ ^

\

►г?

временные узлы сетки

Рисунок 5- Поведение нормы локальной погрешности при заданной 8=10" и размерности системы N=1200. Минимальное значение 4.-10'6

Основные результаты

На основе явных методов типа Рунге-Кутты с контролем точности вычислений и устойчивости численной схемы, а также ¿-устойчивого (2,1)-метода разработаны и реализованы на языке С++ параллельные алгоритмы переменного шага для решения жестких и нежестких задач. Создан комплекс параллельных программ для многопроцессорных вычислительных систем кластерной архитектуры, которым проведено моделирование двух практических задач.

1. Построены параллельные явные численные методы с первого по третий порядок с неравенствами для контроля точности вычислений и устойчивости численной схемы, а также ¿-устойчивый метод второго порядка точности.

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

3. Создан комплекс параллельных программ, в состав которого включены программные реализации разработанных алгоритмов. Работоспособность и эффективность комплекса исследована на общепринятых тестовых задачах.

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

Публикации в журналах из списка ВАК:

1. Ващенко, Г.В. Последовательный (2,1)-метод и его параллельный аналог/ Г.В. Ващенко, Е.А. Новиков // Системы управления и информационные технологии. - 2009. - №4(38). - С. 8-11.

2. Ващенко, Г.В. Параллельный алгоритм (2,1)-метода решения жестких задач/Г.В. Ващенко, Е.А. Новиков//Естественные и техническиенауки-2009. -№6,- С. 550-554.

3. Ващенко, Г.В. Параллельная реализация явных методов типа Рунге-Кутты/ Г.В. Ващенко, Е.А. Новиков//Вестник КрасГАУ. -2010. -Вып. №2. -С. 14-18.

4. Ващенко, Г.В .Параллельная столбцовая схема и алгоритм (2,1)-метода для решения жестких задач/ Г.В. Ващенко, Е.А. Новиков // Вестник Ижевского государственного технического университета.-2010.-Вып. 1(45). —С. 150—153

5. Ващенко, Г.В. Параллельная реализация явного метода Эйлера с контро лем точности вычислений/Г.В. Ващенко, Е.А. Новиков/Журнал Сибирского федерального университета. Математика и физика. - 2011. - Т.4. - №1. - С. 70-76.

Публикации в других изданиях:

6. Ващенко, Г.В. Параллельные алгоритмы явных методов Рунге-Кутты/ Г.В. Ващенко, Е.А. Новиков //Сб. науч. тр. IX Всероссийской конф. "Проблемы информатизации региона". Красноярск, 2009. -С. 334-336.

7. Ващенко, Г.В. О параллельных алгоритмах явных методов типа Рунге-Кут ты/Г .В. Ващенко//Сб.ст. XI Междунар. конф."Информационно -вычислитель ные технологии и их приложения". Пенза, РИО ПГСХА. - 2009. - С. 73-77.

8. Ващенко, Г.В.Параллельная строчноориентированная схема (2,1)-метода решения жестких задач/ Г.В. Ващенко //Альманах современной науки и образования.-2009.-№12(31).-4.1.-С. 13-16.

9. Ващенко, Г.В. Параллельный алгоритм Ь-устойчивого метода второго порядка для решения жестких задач/ Г.В. Ващенко, Е.А. Новиков // Вестник КрасГАУ: Ресурсосберегающие технологии механизации с/х.—2010.—Вып.б.— С.151-156.

10. Ващенко, Г.В.Параллельный алгоритм явного метода Эйлера с контролем точности вычислений/Г.В. Ващенко, Е.А.Новиков//Вестник КрасГАУ: Ресурсосберегающие технологии механизации с/х.-2010.-Вып.6.-С. 156-160.

11. Ващенко, Г.В. Параллельный алгоритм Ь - устойчивого метода второго порядка для численного решения жестких задач/Г.В. Ващенко, Е.А. Новиков //Сб. ст. XV Всерос. конф. "Информационные и математические технологии в науке и управлении ".— Т. 3. - Иркутск. - 2010. - С. 233-237.

12. Ващенко, Г.В. Параллельный явный метод первого порядка с контролем точности/ Г.В. Ващенко // Сб. ст. V Междунар. конф. "Аналитические и численные методы моделирования естественнонаучных и социальных проблем". Пенза: Приволжский Дом знаний. - 2010. - С. 61-63.

13. Ващенко, Г.В. Параллельные алгоритмы (2,1)-метода решения жестких задач/ Г.В. Ващенко, Е.А. Новиков //Сб. науч. тр. IV Междунар. конф. "Параллельные вычислительные технологии ПаВТ'2010". - Уфа. - 2010. -С. 679.

14. Novikov Е.А., Vashchenko G.V. Parallel Algorithm for Explicit Runge-Kutta Method 2nd Order on Accuracy and Stability Control // In.: Proc. I Conf.: Computer Technology and Applications. - Vladivostok. - 2010. - P. 202-204.

15. Novikov E.A., Vashchenko G.V. Parallel explicit Runge-Kutta method 2nd order: implementation of accuracy and stability control: Сб. науч. тр. VII Межрегион, шк.-семинара "Распределенные и кластерные вычисления»". -Красноярск: ИВМ СО РАН. - 2010. - С. 40-43.

16. Ващенко, Г.В. Параллельные явные одношаговые методы для численного решения жестких систем обыкновенных дифференциальных уравнений/ Г.В. Ващенко //Успехи современного естествознания. -2011. — №1. - С. 75-76.

17. Ващенко, Г.В. Параллельный алгоритм явного трехстадийного метода типа Рунге-Кутты для численного решения жестких систем обыкновенных дифференциальных уравнений/ Г.В. Ващенко// Международный журнал прикладных и фундамент, исследований. - 2011. - №3- С. 96-97.

18. Novikov Е.А, Vashchenko G.V. Parallel explicit Runge-Kutta method 2nd order: accuracy and stability control // J. of Appl. and Fundamental research. -2011.-№1.-P. 101-102.

Подписано в печать 27.01.2012 Формат 60x84/16. Усл. печ. л. 1,0 Тираж 100 экз. Заказ 6132

Отпечатано полиграфическим центром Библиотечпо-издательского комплекса Сибирского федерального университета 660041 Красноярск, пр. Свободный, 82а Тел/факс (391)206-26-58,206-26-49 E-mail: print_sfu@mail.ru; http://lib.sfu-kras.ru

61 12-1/1033

Институт вычислительного моделирования СО РАН Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный

технологический университет»

РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ ОДНОШАГОВЫХ МЕТОДОВ И КОМПЛЕКСА ПРОГРАММ ДЛЯ РЕШЕНИЯ ЗАДАЧ ХИМИЧЕСКОЙ

КИНЕТИКИ И БИОЛОГИИ

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

На правах рукописи

Ващенко Геннадий Васильевич

Диссертация на соискание ученой степени кандидата физико-математических наук

Красноярск 2012

Содержание

Введение.......................................................................................................................3

Глава 1. Контроль точности и устойчивости. Последовательный и параллельный алгоритмы...........................................................................................8

1.1 Основные определения.....................................................................................9

1.2 Контроль точности вычислений.....................................................................16

1.3 Контроль устойчивости...................................................................................24

1.4 Реализация методов с контролем точности и устойчивости.......................27

1.5 Параллельные вычислительные системы и параллельные вычисления.... 30

1.6 Оценки эффективности параллельных алгоритмов.....................................31

1.7. Параллельный вариант явного метода с контролем точности

вычислений и устойчивости численной схемы..................................................35

1.8 Заключение к главе 1.......................................................................................44

Глава 2. Параллельная реализация явных методов с контролем точности и устойчивости..............................................................................................................45

2.1. Явные т-стадийные методы типа Рунге-Кутты.........................................45

2.2. Одностадийный метод....................................................................................52

2.3. Двухстадийный метод....................................................................................59

2.4. Трехстадийный метод....................................................................................69

2.5. Заключение к главе 2......................................................................................81

Глава 3. Параллельная реализация ¿-устойчивого метода...................................83

3.1. Класс (т,к)-методов.......................................................................................83

3.2. Алгоритм постоянного шага на основе (2,1)-метода..................................84

3.3. Параллельный алгоритм переменного шага................................................91

3.4. Анализ эффективности...................................................................................94

3.5. Заключение к главе 3......................................................................................96

Глава 4. Комплекс параллельных программ и результаты численного моделирования..........................................................................................................97

4.1. Комплекс параллельных программ...............................................................97

4.2. Численное моделирование генной сети.......................................................99

4.3. Численное моделирование проникновения антител в ткань живого организма..............................................................................................................115

Заключение..............................................................................................................123

Литература...............................................................................................................124

Введение

Численное решение обыкновенных дифференциальных уравнений вида

y' = f{t,y\ y(t0) = y0, tQ<t<tk, (1)

где у и/- вещественные TV-мерные вектор-функции, t - скалярная величина является одной из наиболее часто встречающихся задач научно-технических исследований в химической кинетики, биологии, радиоэлектроники и в других практических приложениях. Во многих случаях задача усложняется жесткостью и большой размерностью системы (1). В результате возможностей обычных последовательных вычислительных машин уже оказывается недостаточным. Поэтому актуальной проблемой является создание алгоритмов интегрирования на современных параллельных вычислительных машинах с распределенной памятью. Для этого необходимо разработать параллельный алгоритм разбиения данных на блоки, каждый из которых обрабатывается отдельным процессором, а так же организовать межпроцессорные взаимодействия с учетом архитектуры и программного обеспечения многопроцессорной вычислительной машины.

При численном решении систем дифференциальных уравнений одношаговыми методами на основе схем типа Рунге-Кутты и ¿-устойчивых методов возникает необходимость построения численных формул с автоматическим выбором величины шага интегрирования, обеспечивающего требуемую точность вычислений. Критерии выбора шага основываются на оценках локальной или глобальной погрешности, а для явных методов дополнительно требуется контролировать устойчивость численной схемы. Поэтому разработка параллельных явных методов переменного шага с выбором величины шага по точности и устойчивости является актуальной задачей. При построении параллельных алгоритмов и программ интегрирования требуется разрешить ряд вопросов, которым посвящена данная работа. Сначала нужно выбрать методы, которые соответствовали бы классу решаемых задач. Здесь в основу алгоритмов интегрирования

положены одношаговые безытерационные численные схемы вида

Уп+1=У« + ¥А*п>Уп>к)> (2)

которые обладают определенными преимуществами перед многошаговыми. В частности, многошаговые формулы приводят в некотором смысле к осреднению решения (срезание экстремумов), что при моделировании некоторых динамических объектов делает их неприемлемыми. Кроме того, если правая часть дифференциальной задачи разрывная, то применение многошаговых методов является малоэффективным. Достаточно полный обзор работ по многошаговым методам содержится в [1-5], и поэтому ниже на этом вопросе останавливаться не будем.

Требование безытерационности (2) позволяет оценить затраты на шаг интегрирования до проведения расчетов и упрощает программную реализацию как последовательных, так и параллельных алгоритмов интегрирования. Важность указанных задач породила за последнее время огромное количество методов интегрирования жестких и не жестких систем. Однако для того, чтобы от идеи метода перейти к его алгоритмической реализации, необходимо решить проблему изменения величины шага интегрирования и оценки точности получаемых численных результатов, что и делает метод экономичным и надежным. Современные способы управления шагом основаны, как правило, на контроле точности численной схемы. Такой подход представляется наиболее естественным, поскольку основным критерием при проведении практических расчетов является точность нахождения решения. Многие алгоритмы интегрирования для выбора величины шага используют оценку локальной ошибки (погрешности аппроксимации). Это оправдано тем, что если на каждом шаге контролировать некоторый минимальный уровень локальной ошибки, то глобальная ошибка будет ограничена. В настоящее время можно выделить три практических способа оценки данной ошибки [1,с.59-65]. Классическим способом оценки локальной ошибки является экстраполяция Ричардсона [1011]. Его иногда еще называют правилом Рунге, и он заключается в

следующем. В каждой сеточной точке интервала интегрирования решение вычисляется с шагом /г и 0.5/г, а искомая оценка определяется через разность приближений к решению. Недостатком такого способа является необходимость дважды вычислять решение в каждой точке, что приводит к значительному увеличению вычислительных затрат. В последнее время все большую популярность получает способ оценки локальной ошибки с помощью вложенных методов. В этом случае приближение к решению в каждой точке вычисляется двумя методами вида (2) р-то и (р+1)-го порядка точности, а затем локальная ошибка метода р-то порядка оценивается через разность полученных приближений. Такой способ эффективен, если для вычисления по методу р-го порядка не требуется дополнительных вычислений правой части и матрицы Якоби задачи (1). Следует отметить оперативность и относительную дешевизну оценки локальной ошибки с помощью вложенных методов. По затратам на шаг она лежит между оценкой ошибки с помощью правила Рунге и многошаговой оценкой. В то же время, по отношению к многошаговой оценке, в ней при вычислении ошибки используется информация только с данного шага, что повышает ее надежность. Данный способ успешно применялся в работах [6-7, 9] и ниже будет использоваться здесь.

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

(3)

где дп - оценка локальной ошибки, ||-|| - некоторая норма в Як\ е - требуемая точность расчетов. В [12] используется другое неравенство

которое получено в предположении, что при интегрировании устойчивыми методами вклад начальных возмущений убывает по мере продвижения по сетке. Здесь через р обозначен порядок точности метода, а через ср -некоторая вычисляемая постоянная. Обоснование (4) для линейной скалярной задачи приведено в ([14], с. 43-45). Еще один способ оценки основан на интегрировании дополнительной линейной системы дифференциальных уравнений, описывающей поведение главного члена глобальной ошибки (см., например, [4], с. 40-45). Однако это связано с вычислением матрицы Якоби и дополнительными затратами на интегрирование. Поэтому такой способ применяется достаточно редко.

В последнее время при численном исследовании некоторых жестких задач все большее внимание привлекают явные методы (см. библ. [14]). При решении ряда задач А-устойчивыми методами возникает проблема с размещением элементов матрицы Якоби в оперативной памяти ЭВМ и, что более существенно, с ее обращением. Явные методы не нуждаются в вычислении матрицы Якоби и, если жесткость задачи не слишком велика, то они будут предпочтительнее. Более того, появление многопроцессорных вычислительных систем позволяет взглянуть иначе на явные методы. Здесь следует отметить, что для многопроцессорных вычислительных систем основным требованием к алгоритму является наличие внутреннего параллелизма - алгоритм должен состоят из частей, которые могут выполняться одновременно и независимо друг от друга. Следующий принципиальный факт во многом определяет возможность эффективной параллельной реализации алгоритмов - время обмена сообщениями между процессорами существенно превышает время доступа к своей локальной памяти и время выполнения арифметических операций. Отсюда возникает условие локальности алгоритма, т.е. на каждом процессоре обращение к локальной памяти и выполнение арифметических операций должны происходить значительно чаще, чем обмены данными с другими процессорами. Желательно требование масштабируемости, т.е способности

алгоритма работать на произвольном числе процессоров. На практике это обеспечивает высокую эффективность параллельной реализации и для конкретного набора процессорных элементов [13,15-17].

Работа состоит из введения, четырех глав, заключения и списка цитированной литературы. Во введении дан краткий обзор научной литературы по теме работы, обоснована актуальность исследований, приведено краткое содержание диссертации по главам. Глава 1 посвящена вопросам нахождения приближенного решения одношаговыми методами, а также последовательной и параллельной реализации алгоритмов интегрирования. Приведены сведения о параллельных вычислительных системах, моделях параллельных вычислений и способах оценки эффективности на таких вычислительных системах. В главе 2 разработаны параллельные алгоритмы интегрирования переменного шага на основе явных т-стадийных методов типа Рунге-Кутта с применением схем с первого по третий порядок точности. Построены оценки ошибки и неравенства для контроля точности вычислений и устойчивости численной схемы. Получены оценки ускорения и эффективности. Глава 3 посвящена параллельной реализации численных схем с неограниченной областью устойчивости. На основе ¿-устойчивого (2,1)-метода решения жестких задач созданы параллельные алгоритмы интегрирования с постоянным и переменным шагом интегрирования. Особое внимание уделяется параллельной декомпозиции матрицы Якоби, потому что при большой размерности время декомпозиции фактически полностью определяет общие вычислительные затраты. Построены оценка ошибки и неравенство для контроля точности вычислений. Получены оценки ускорения и эффективности. В главе 4 описан комплекс параллельных программ численного решения задачи Коши для жестких и нежестких систем дифференциальных уравнений. Приведены результаты моделирования генной сети и численного решения задачи проникновения радиоактивных меток в ткань живого организма. В заключении сформулированы основные результаты исследований.

Глава 1. Контроль точности и устойчивости. Последовательный и параллельный алгоритмы

Глава 1 посвящена вопросам нахождения приближенного решения одношаговыми методами, а также последовательной и параллельной реализации алгоритмов интегрирования. Приведены сведения о параллельных вычислительных системах, моделях параллельных вычислений и способах оценки эффективности на таких системах.

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

При применении явных методов для решения жестких задач шаг интегрирования ограничен в основном устойчивостью численной схемы. Поэтому соответствующие алгоритмы на основе явных формул обладают малой эффективностью. Ниже описан способ получения неравенства для контроля устойчивости методов с ограниченной областью устойчивости, что повышает надежность расчетов. Сформулированы последовательный и параллельный алгоритмы интегрирования с контролем точности вычислений и устойчивости численной формулы.

1.1 Основные определения

Ниже будет рассматриваться задача Коши для неавтономной системы обыкновенных дифференциальных уравнений

= = (1-1) где у и/- гладкие вещественные Л^-мерные вектор-функции, / - независимая переменная, изменяющаяся на заданном отрезке [¿о,4]- Предположение о гладкости правой части системы (1) влечет выполнение условий локальной теоремы Коши-Пикара, откуда, в свою очередь, следует существование единственного решения задачи (1), [¿0,4] - область определения решения. Ниже это условие особо оговариваться не будет. Введением дополнительной переменной систему (1.1) можно привести к автономному виду. Определив

ГГ-1 ГТ1 ГП П1

х={иу ) , £=0 /) , Хо=^о,уо ) , и переходя к обозначениям _у,/и у0, получим

/ = = (1-2)

Поэтому часть рассуждений будем проводить для автономной системы. Случаи, когда различие (1.1) и (1.2) принципиально, будут оговариваться отдельно. Ниже будем предполагать, что задача (1.2) является жесткой.

Определение 1.1. Задача Коши (1.2) называется жесткой на некотором интервале I а , если для ? е / имеет место

(1) Яе(Я.) <0, 1</<7У, (2) шах Яе(-/1.)/тш Яе(-^.)»1,

где Х1, 1 < I < N - собственные числа матрицы Якоби д/ / ду на решении у (?).

Класс жестких задач разнообразен, и поэтому в литературе встречаются другие определения жесткости, отличающиеся степенью строгости. Поясним, в чем заключается суть жесткости [10,24-26]. Речь идет в основном об устойчивых задачах, что следует, по крайней мере, для автономных систем, из первой части определения 1.1. В определении [25] допускается наличие небольших по величине положительных собственных чисел матрицы Якоби, что достаточно существенно расширяет класс решаемых практических задач. В жестких задачах длина интервала интегрирования связана с медленно меняющимся решением, в то время как существуют быстро затухающие

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