авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 4 | 5 ||

«ЧИСЛЕННЫЕ МЕТОДЫ, ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ МОСКВА 2008 Российская академия наук Институт ...»

-- [ Страница 6 ] --

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

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

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

Зависимые от языка блоки анализа служат для определения тех свойств программы, для которых нужно знать специфику языка, на котором она написана. Например, для построения графа управления программы нужно уметь определять, в каком порядке передается 262 К. С. Стефанов управление между операторами. Определение того, какой оператор может быть выполнен после данного, является блоком, реализация которого зависит от языка анализируемой программы. В Фортране есть управляющие операторы GOTO, IF, оператор цикла DO. В язы ке Си набор управляющих операторов другой: goto, if, switch, break, continue и операторы цикла for, while, do... while. Наборы управ ляющих операторов различаются от языка к языку.

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

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

Некоторые преобразования программы можно делать более эф фективно, если не требовать сохранения корректности програм мы на промежуточных этапах (разумеется, полное преобразование должно сохранять корректность).

Например изменение размерности массива, используемое иногда для приведения программы к линей ному виду [3], может привести к тому, что операции доступа к эле ментам этого массива станут некорректными. Можно разработать последовательность преобразований, включающую введение нового массива и последовательную замену всех обращений к одному масси ву на обращения к другому, но проще временно отключить проверку полной корректности получаемой программы после каждого шага преобразования (если такая проверка вообще проводится). Поэтому необходимо иметь возможность отключения некоторых проверок на корректность. Естественно, что ответственность за полную кор ректность получаемой программы лежит на программисте, реали зующем преобразования в таком режиме. При этом синтаксическая корректность получаемой программы гарантируется средствами ге нерации программы уровня работы с внутренним представлением.

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

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

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

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

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

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

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

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

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

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

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

Таким образом может быть реализована, например, используе Системы анализа структур программ мая в системе V-Ray схема специальных комментариев [2]. Такие комментарии размещаются в тексте программы и сообщают анали зирующей системе о некоторых свойствах этой программы, напри мер, о границах изменений каких-либо переменных. В этом случае эксперт, использующий такую информацию в своей работе, запра шивает ее у вызывающего модуля. Этот модуль может быть другим экспертом, который просмотрит имеющиеся в программе коммента рии и сообщит требуемую информацию (либо о ее отсутствии).

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

У каждой системы, созданной при помощи инструментария, дол жен быть один основной блок интерфейса. Этот блок должен опре делить и сообщить другим блокам системы:

На каком языке написана анализируемая программа и какие файлы ей принадлежат.

Какие эксперты будут вызываться после загрузки анализиру емой программы.

Какие еще модули интерфейсов будут использоваться.

Куда будет записан текст сгенерированной программы и дру гие выходные файлы (если они есть).

Другую информацию, необходимую вызываемым экспертам.

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

266 К. С. Стефанов Другие используемые интерфейсные модули и блоки-эксперты скорее всего будут иметь различные программные интерфейсы, по этому их использование определяется программным кодом данно го модуля интерфейса. Для каких-то конкретных систем может ис пользоваться ровно один эксперт, собирающий какую-нибудь ста тистику по свойствам анализируемого программного комплекса. В этом случае модуль интерфейса будет достаточно простым без ис пользования других интерфейсов. Или наоборот, у сложной систе мы с графическим интерфейсом может быть предоставлен выбор по вызываемым экспертам, а для настройки каких-то экспертов могут привлекаться другие интерфейсные модули. Например, в рамках од ной системы могут одновременно присутствовать возможности рас параллеливания программы и под OpenMP, и под MPI, оформлен ные в виде разных экспертов. В этом случае основной блок интер фейса должен предоставить пользователю выбор, какой эксперт за пускать, а настройки разных экспертов будут производиться соот ветствующими интерфейсными модулями.

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

Как уже отмечалось выше, некоторым экспертам при работе мо жет потребоваться дополнительная информация. Она может позво лять провести более точный анализ или иногда указать эксперту про какие-то свойства программы, известные пользователю, но которые не удается получить при анализе текста программы. Если при этом эксперт вызывается напрямую из интерфейса (или через цепочку других экспертов, которым неоткуда взять эту информацию), экс перт делает запрос к вызвавшему его модулю о наличии требуемой информации, передавая сведения о каком объекте программы и что именно он хочет узнать. Интерфейс инициирует диалог с пользо вателем с запросом соответствующих сведений, если такая возмож ность предусмотрена, или сообщает, что данных у него нет. Также информация может быть получена не от пользователя а, например, из файла, описывающего задание для системы. Но в этом случае, Системы анализа структур программ особенно если таких сведений может быть много, целесообразно вы нести эту информацию в отдельный файл и создать еще один интер фейсный модуль, читающий данный файл и сообщающий сведения запрашивающему модулю.

При построении пользовательского интерфейса к объектамсвой ствам программы добавляются объекты-представления этих свойств.

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

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

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

В блоках уровня интерфейсов должна быть локализована зави симость от среды, в которой исполняется система. Именно блоки этого уровня знают о желательном расположении файлов, о вызо вах, требуемых для открытия этих файлов. Другим блокам при этом передаются объекты языка программирования, на котором они на писаны, представляющие открытый файл (например объект типа istream или ostream Си++).

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

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

10. Примеры блоков инструментария На рис. 2 приведена схема инструментария с примерами блоков, расположенных на каждом уровне.

На уровне внутреннего представления располагаются блоки, от вечающие за работу со всеми объектами, составляющими програм му: операторами, переменными, типами, комментариями и т.п.

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

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

В качестве эксперта может быть модуль, реализующий преобра зование последовательной программы в систему программирования OpenMP или DVM. Или же конструируемая система (и соответству ющий эксперт) может размечать программу в соответствии с имею щимся в ней потенциальным параллелизмом.

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

Список литературы [1] Shen Z., Li Z., Yew P.-C. An Empirical Study of Fortran Programs for Parallelizing Compilers// IEEE Transactions on Parallel and Distributed Systems. 1990. Vol. 1, no. 3. Pp. 356–364.

[2] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.

СПб.: БХВ-Петербург, 2002. 608 с.

[3] Хмелев Д.В. Восстановление линейных индексных выражений для сведения программ к линейному классу// ЖВМ и МФ.

1998. Т. 38, № 3. С. 532–544.

[4] Воеводин Вл.В. Теория и практика исследования параллелизма последовательных программ// Программирование. 1992. № 3.

С. 38–53.

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

Алгебраическая теория аппроксимаций Паде является по сути теорией подматриц бесконечной ганкелевой матрицы. Основные факты этой теории формулируются элегантно и просто. С ними можно познакомиться, например, по книге [1]. Однако приведенные там доказательства не только сложны, но и в некоторой степени дезориентируют читателя. Цель этой заметки дать полное, крат кое и ясное изложение теории Паде на основе метода скачков, возникшего при изучении ведущих подматриц ганкелевой матрицы [2, 6]. В качестве основного результата, помимо некоторого развития самого метода скачков, нужно рассматривать новые доказательства известных утверждений алгебраической теории Паде.

1. Ряды и матрицы Пусть задан формальный ряд a i xi.

f(x) = i= Его аппроксимацией Паде типа (m, n) называется пара много членов m n ui xi, vi xi u(x) = v(x) = i=0 i= ° Работа выполнена при поддержке грантов РФФИ 05-1-00721, 06-01-08052 и Программы приоритетных фундаментальных исследований Отделения матема тических наук РАН.

Институт вычислительной математики РАН 272 Е. Е. Тыртышников таких, что f(x)v(x) u(x) = O(xm+n+1 ) (1) при дополнительном условии (2) v(0) = 1.

Отсюда сразу же следует, что u(x) = O(xm+n+1 ).

f(x) v(x) Условие (1) равносильно системе линейных уравнений n aij vj = 0, m+1 m + n, i j= или, в матричной записи, am+1 am... amn+1 v am+2 v am+1... amn = 0.

......

.........

am+n am+n1... am vn С учетом равенства v0 = 1 получаем am... amn+1 v1 am+...... =....

......

am+n1... am vn am+n Для наглядности возьмем m = n = 3, тогда a3 a2 a1 v1 a a4 a2 v2 = a5.

a a5 a4 a3 v3 a В матрице этой системы каждый элемент определяется разностью строчного и столбцового индексов такие матрицы называются теплицевыми. Переставив в обратном порядке столбцы, получа ем матрицу, в которой элементы определяются суммой индексов Метод скачков и аппроксимации Паде такие матрицы называются ганкелевыми. Из нашей системы после такой перестановки получается равносильная система a1 a2 a3 v3 a a2 a3 a4 v2 = a5.

a3 a4 a5 v1 a В общем случае это будет система следующего вида:

amn+1... am vn am+...... =..., (3)......

am... am+n1 v1 am+n или, в краткой записи, Amn vn = amn. (4) Ганкелева матрица Amn составляется из коэффициентов формаль ного ряда f(x). При этом в ее левом нижнем углу помещается ко эффициент am, а порядок матрицы равен n. Если i 0, то счита ется, естественно, что ai = 0. Столбец правой части amn является последним столбцом расширенной прямоугольной ганкелевой мат рицы [Amn, amn ].

Таким образом, вопрос о существовании аппроксимации Па де типа (m, n) равносилен вопросу о разрешимости линейной системы (4). Последнее означает, что amn Amn, и, в силу теоремы Кронекера–Капелли, равносильно условию Amn = [Amn, amn ]. (5) 2. Метод скачков Рассмотрим полубесконечную ганкелеву матрицу A = [ai+j1 ], 1 i, j, и ее ведущие подматрицы. Пусть Ak ведущая подматрица поряд ка k, а последовательность натуральных чисел n1 n2...

274 Е. Е. Тыртышников определяет порядки тех и только тех ведущих подматриц, кото рые являются невырожденными. Метод скачков, предложенный в [2], представляет собой схему перехода от некоторого компактного представления матрицы A1 к аналогичному представлению для nk A1. Название объясняется тем, что при этом происходит ска nk+ чок через промежуточные вырожденные подматрицы.

С общими вопросами построения быстрых алгоритмов для ган келевых и теплицевых матриц можно познакомиться, например, по работам [4, 5, 7]. Алгебраические свойства ганкелевых матриц, поз воляющие сделать скачок, можно найти также в книге [6]. Они тесно связаны с изученными в [3] вопросами бесконечного продол жения ганкелевой матрицы с сохранением ранга.

Метод скачков базируется на следующем наблюдении. Пусть p = nk и q = nk+1. В силу невырожденности Ap система a1... ap s1 ap+...... =...

......

ap... a2p1 sp a2p имеет единственное решение. Другими словами, усеченные до p эле ментов столбцы с 1-го по p -й линейно независимы, а таким же обра зом усеченный p+ 1 -й столбец является их линейной комбинацией с коэффициентами s1,..., sp. Вполне возможно, что те же коэффици енты позволяют получить p + 1 -й столбец как линейную комбина цию предыдущих столбцов при усечении до p+1 или даже бльшего о числа элементов.

Теорема 1. Пусть r(p) p минимальный размер усечения, при котором p + 1 -й столбец не является линейной комбинацией преды дущих столбцов. Тогда nk+1 = r(nk ).

Доказательство. Пусть p = nk и r = r(p). Тогда a1... ap ap+1... s............

... ap... a2p1 a2p =, = 0.

sp...

............

ar1... ar+p2 ar+p1 1 ar... ar+p1 ar+p Метод скачков и аппроксимации Паде Отсюда получаем равенство s1 s...............

sp......

= Ar sp 1...

1......

......

... sp a1 a2... ap a2 a3... ap+............

ap ap+1... a2p =.

ap+1 ap+2... a2p..................

..................

......... ar ar+1... ar+p (6) При p = nk матрица Ap невырожденная. Поэтому ясно, что невы рожденность окаймляющей ее матрицы Ar равносильна условию = 0.

Следствие 1. При nk nk+1 имеет место равенсто n An = {n nk, nk+1 n}.

Доказательство. Непосредственно из (6) вытекает, что при умно жении An на невырожденную матрицу получается матрица, в ко торой имеется {n nk, nk+1 n} нулевых столбцов, а остальные столбцы линейной независимы.

^ Введем обозначение An для следующего расширения матрицы An :

a1... an an+ An =..........

^...

an... a2n1 a2n 276 Е. Е. Тыртышников Следствие 2. Если nk n nk+1, то равенство рангов An = An ^ (7) имеет место в том и только том случае, когда (8) n nk nk+1 n.

Доказательство. Согласно теореме Кронекера–Капелли, равенство (7) равносильно тому, что последний столбец расширенной матрицы ^ An является линейной комбинацией ее предыдуших столбцов. Пусть p = nk и q = nk+1.

Запишем p n = p + i q. Заметим,что p + 1 -й столбец матри цы Aq1 является линейной комбинацией предыдущих столбцов с коэффициентами s1,..., sp. То же верно в отношении p+ 1 -го столб ца ее ведущих подматриц, содержащих Ap+1. Если p + 2i q, то это верно для матрицы Ap+2i. Используя ганкелеву структуру матриц, отсюда легко вывести, что p + 1 + i -й (последний) столбец ^ расширенной матрицы Ap+i линейно выражается через предыду щие p столбцов (с теми же коэффициентами s1,..., sp ). Условие p + 2i q равносильно неравенству n p q n.

Остается доказать, что (7) влечет за собой (8). Согласно (7) по ^ следний столбец расширенной матрицы An линейно выражается через стобцы An. В этом случае при переходе от An к An+1 ранг может увеличиться не более чем на 1. От противного, допустим, что np q p.

Согласно следствию 1, An = n {n p, q n} = 2n q, An+1 = n + 1 {n + 1 p, q n 1} = 2n q + 2.

Следовательно, An+1 = An + 2, т. е. ранг должен вырасти больше, чем на 1.

Следствие 3. В случае nk n nk+1 неравенство (8) выполня ется тогда и только тогда, когда An+1 An 1.

Метод скачков и аппроксимации Паде 3. Детерминантное тождество Пусть A матрица порядка n, а Aij ее подматрица порядка n1, полученная вычеркиванием строки i и столбца j. Пусть Aik;

jl обозначает поматрицу порядка n 2, полученную из A вычерки ванием пары строк с номерами i и k и пары столбцов с номерами j и l. Следующий результат известен как тождество Сильвестра.

Теорема 2. Пусть i k и j l. Тогда A Aik;

jl = Aij Akl Ail Akj.

Доказательство. Не ограничивая общности, можно считать, что i = j = n 1 и k = l = n. Пусть B = Aik;

jl. Тогда матрица A имеет вид Bvq A = u c d.

pgh Предположим сначала, что подматрица B невырожденная. Исклю чая по Гауссу u и p с помощью невырожденного блока B, находим I 00 Bvq Bv q uB1 1 0 u c d = 0 c1 d1, pB1 0 1 pgh 0 g1 h где h1 = hpB1 q, c1 = cuB1 v, g1 = gpB1 v, d1 = duB1 q.

Следовательно, Aij Akl Ail Akj = ( B)2 (h1 c1 g1 d1 ) = B A.

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

4. Таблица миноров Приступим к изучению бесконечной ганкелевой матрицы A = [ai+j ], составленной из коэффициентов формального ряда f(x) = 278 Е. Е. Тыртышников ai xi (если i 0, то ai = 0 ). Напомним, что через Amn обо i= значается ее ганкелева подматрица порядка n, содержащая в левом нижнем углу коэффициент am. Нас интересует полубесконечная матрица C = [cmn ], составленная из миноров матрицы A :

Amn, cmn = 0 m, n.

Условимся считать, что cm0 = 1.

Лемма 1.

cm,n+1 cm,n1 = cm+1,n cm1,n c2.

mn Доказательство. Данное равенство есть не что иное, как детерми нантное тождество Сильвестра (теорема 2), записанное для ганке левой матрицы Am,n+1 и ее подматриц, получаемых при вычерки вании первых и последних строк и столбцов и поэтому остающихся ганкелевыми.

Таблицу миноров C для ганкелевой матрицы A иногда назы вают C -таблицей [1]. Ее основное свойство заключается в особой структуре расположения нулей (нулевых миноров матрицы A ). Бу дем называть окном любую конечную или бесконечную подматрицу, составленную из подряд идущих строк и столбцов. Окно называется квадратным окном, если оно соответствует конечной квадратной подматрице или бесконечной подматрице, в которой бесконечно мно го как строк, так и столбцов. Все примыкающие к окну элементы будем называть его рамой это элементы более широкого окна на строках и столбцах, окаймляющих данное окно. Нас будут инте ресовать нулевые окна и ненулевые рамы в первом случае все элементы множества суть нули, во втором все они отличны от нуля.

В дальнейшем будем считать, что a0 = 0. Тогда c0n = 0 при n 1 (определители ганкелевых треугольных матриц с ненулевым элементом побочной диагонали). Кроме того, примем соглашение о том, что cm0 = 1 при m 0.

Теорема 3. Любой нулевой элемент таблицы миноров C принад лежит квадратному нулевому окну с ненулевой рамой.

Метод скачков и аппроксимации Паде Доказательство. Предположим, что cm,n1 = cm+1,n = 0 или cm,n+1 = cm+1,n = 0. Согласно лемме 1 находим cmn = 0. Таким образом, матрицы вида, непременно оказываются нулевыми. С учетом неравенств cm0 = и c0n = 0 отсюда следует, что любой нулевой элемент матрицы C принадлежит прямоугольному нулевому окну с ненулевой рамой.

Остается доказать, что любое такое окно является квадратным.

Пусть cmn = 0 элемент рамы, расположенный в ее левом верхнем углу. Предположим, что cm+r,n+r = 0 еще один элемент рамы того же окна, и докажем, что этот элемент находится в правом нижнем углу. Если это не так, то:

(1) cm+r,n+r1 = 0, либо (2) cm+r1,n+r = 0.

Случай (1). Заметим, что матрицы Amn и Am+r,n+r явля ются невырожденными ведущими подматрицами в ганкелевой мат рице Am+r,n+r и при этом промежуточные ведущие подматрицы Am+i,n+i при 0 i r являются вырожденными. Согласно методу скачков (теорема 1), n + 1 -й столбец матрицы матрицы Am+r,n+r с вычеркнутой последней строкой является линейной комбинацией предыдущих столбцов.

В данном случае cm+1,n = 0 и cm+r+1,n+r = 0. Поэтому метод скачков можно применить к невырожденным ганкелевым матрицам Am+1,n и Am+1+r,n+r и сделать вывод о том, что n + 2 -й стол бец матрицы Am+r,n+r с вычеркнутой последней строкой является линейной комбинацией предыдущих столбцов, начиная со 2-го. Вы читая данные линейные комбинации из n+1 -го и n+2 -го столбцов, мы не изменим определитель матрицы Am+r,n+r и получим в нем два столбца с нулевыми элементами, кроме элементов последней строки. Следовательно, cm+r,n+r = Am+r,n+r = 0, что противо речит сделанному ранее предположению. Поэтому с необходимостью cm+r,n+r1 = 0.

Случай (2). Заметим, что cm+r,n+r+1 = 0 (иначе в силу леммы cm+r,n+r = 0 ). Таким образом, матрицы Am,n+1 и Am+r,n+r+ 280 Е. Е. Тыртышников невырожденными ведущие подматрицы с вырожденными промежу точными подматрицами. Согласно методу скачков, n + 2 -й столбец в Am+r,n+r+1 с вычеркнутой последней строкой является линейной комбинацией предыдущих столбцов. Отсюда находим, что n + 2 -й столбец матрицы Am+r,n+r с вычеркнутой последней строкой явля ется линейной комбинацией предыдущих столбцов. Как и раньше, то же верно в отношении n+1 -го столбца той же матрицы. Опять при ходим к противоречию с невырожденностью матрицы Am+r,n+r.

Следовательно, cm+r1,n+r = 0.

Таким образом, в каждом из случаев (1) и (2) мы получаем про тиворечие. Значит, одновременно имеем cm+r,n+r = 0, cm+r,n+r1 = 0, cm+r1,n+r = 0.

Это означает, что элемент cm+r,n+r находится в правом нижнем углу рамы нулевого окна. Поскольку в левом верхнем углу разме щается элемент cmn, то окно является квадратным. Если оказалось, что cm+r,n+r = 0 при всех r 0, то из леммы 1 сразу же вытекает, что данное нулевое окно является бесконечным квадратным окном.

5. Теория Паде Теория Паде дает необходимое и достаточное условие существо вания аппроксимации Паде типа (m, n) в терминах структуры ну лей в таблице миноров, ассоциированной с формальным рядом f(x).

Как мы уже знаем, необходима и достаточна совместность системы (4). Очевидно, условие cmn = Amn = 0 является достаточным для разрешимости этой системы. Основной результат для случая cmn = 0 формулируется следующим образом.

Теорема 4. Пусть cmn = 0 принадлежит нулевому окну матрицы C с ненулевой рамой, имеющей в левом верхнем углу элемент ckl = 0, а в правом верхнем углу элемент ck+r,l+r. Тогда аппроксимация Паде типа (m, n) существует в том и только том случае, когда k+l m + n k + l + r.

Доказательство. Пусть cst и cs+p,t+p принадлежат ненулевой ра ме данного нулевого окна и при каком-то h 0 получается m = s+h Метод скачков и аппроксимации Паде и n = t + h. Матрица Ast является невырожденной ведущей под матрицей в невырожденной ганкелевой матрице As+p,t+p, причем подматрицы As+i,t+i вырождены при всех 0 i p. Из метода скачков вытекает (следствие 2), что условие совместности (5) рав носильно неравенству (t + h) t (t + p) (t + h) h p/2.

Оно выполняется в том и только случае, когда m + n k + l + r.

Теорема 5. Пусть ckl и ck+r,l+r угловые элементы ненулевой рамы нулевого окна таблицы миноров, и предположим, что k m, l n. Тогда аппроксимация Паде типа (k, l) является также аппроксимацией типа (m, n), если k + l m + n k + l + r.

Если ckl является угловым элементом ненулевой рамы беско нечного нулевого окна, то в случае k m, l n аппроксимация Паде типа (k, l) будет также аппроксимацией Паде типа (m, n), ес ли k + l m + n.

Доказательство. Пусть k m и l n. Достаточно заметить, что если vl есть решение системы Akl vl = akl, то при условии k+l m+n k+l+r выполняется также равенство = amn.

Amn vl В случае бесконечного окна это верно при всех r 0.

Список литературы [1] Дж. Бейкер, П. Грейвс-Моррис, Аппроксимации Паде, Мир, 1986.

[2] В. В. Воеводин, Е. Е. Тыртышников, Вычислительные процес сы с теплицевыми матрицами, Наука, 1987, 320 с.

282 Е. Е. Тыртышников [3] И. С. Иохвидов, Ганкелевы и теплицевы матрицы и формы, Наука, 1974, 264 с.

[4] Е. Е. Тыртышников, Теплицевы матрицы, некоторые их ана логи и приложения, ОВМ РАН, 1989.

[5] Е. Е. Тыртышников, Методы численного анализа, Издатель ский центр Академия, 2007.

[6] G. Heinig, K. Rost, Algebraic Methods for Toeplitz-like Matrices and Operators, Academie-Verlag, Berlin, 1984.

[7] E. E. Tyrtyshnikov, Euclidean Algorithm and Hankel Matrices / Numerical Analysis and Applied Mathematics, AIP Conference / Proceedings. 2007. V. 936, Melville, New York. P. 27–30.

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

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

Известны задачи, в которых возникают дополнительные ограни чения, связанные с аппроксимацией множественных внутренних ° Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (гранты РФФИ №№05-01-00721 и 06-01-08052) и программы фундаментальных исследований отделения математических наук РАН Вычислительные и информационные проблемы решения больших задач по проекту Матричные методы и технологии для задач со свербольшим числом неизвестных, а также исследовательского гранта ExxonMobil Corp.

Институт вычислительной математики РАН (119333, Москва, ул. Губкина, д.8) e-mail: vadim@bach.inm.ras.ru 284 В. Н. Чугунов границ. Примером может служить двумерная подзадача, возника ющая при моделировании трехмерных течений в пористых средах, обладающих слоистой структурой. Для решения последней задачи удобно использовать призматические сетки с основаниями призм, лежащими на границах геологических слоев. Сами геологические слои, связанные с различными породами, имеют переменную тол щину и могут сужаться вплоть до полного исчезновения на лини ях вырождения, а также менять толщину скачкообразно в районе вертикальных разломов земной коры. Для успешного решения за дач моделирования необходимо, чтобы призматическая сетка отра жала эти особенности, а именно, линии вырождения и поверхности вертикальных разломов были аппроксимированы ребрами и граня ми призм. Одним из способов построения желаемой сетки является проектирование разломов и линий вырождения на двумерную об ласть и задание их ломаными. Имея двумерную сетку со сторона ми треугольников, лежащими на ломаных, можно путем дублиро вания двумерной сетки для каждого геологического слоя получить трехмерную сетку, учитывающую имеющиеся особенности структу ры пористой среды. Построение сетки с внутренними множествен ными ограничениями может быть также использовано как при ре шении других сложных задач, так и само по себе.

Набор условий, накладываемых на алгоритм, определяется сле дующими математическими требованиями, предъявляемыми к сет ке. Во-первых, хотелось иметь возможность использовать получае мую сетку при реализации многосеточных методов [2], являющих ся наиболее эффективными методами решения краевых задач. Это приводит к условию, чтобы полученная сетка была заключитель ным звеном некоторой последовательности логически вложенных друг в друга сеток, для которой задано правило перехода от одной сетки к другой. Во-вторых, требования устойчивости аппроксима ции краевых задач ограничивает класс двумерных сеток триангу ляциями с треугольниками регулярной формы [7, 9]. Наряду с удо влетворением этим математическим условиям, цель алгоритма за ключается в том, чтобы результирующая сетка подчинялась также набору физических требований. А именно, построенная двумерная сетка должна обладать небольшим числом треугольников в силу ограничений, накладываемых возможностями вычислительной тех О сетке, слабо -аппроксимирующей ломаные ники при решении задач, использующих треугольную сетку. Кроме этого, так как данные о внутренних границах не могут быть точ ными из-за погрешностей измерений, всегда существует некоторый порог для точности аппроксимации заданных ломаных, что допуска ет их незначительную локальную модификацию. Вышеприведенные соображения определяют рассматриваемый класс сеток и ограниче ний.

Существует несколько методов генерации треугольных сеток [7, 9, 10], удовлетворяющей множественным ограничениям, а также це лый ряд их программных реализаций [15, 16]. Первый алгоритм при надлежит Бейкеру, Гроссе и Рафферти [3]. Они предложили метод триангуляции области, являющейся множеством многоугольников с углами не менее 13o. В итоговой сетке углы всех треугольников не превосходят 90 градусов и наименьший угол не меньше 13o. Од нако, получающаяся сетка является равномерной и, поэтому, имеет очень много сеточных элементов.

Проблема большого числа треугольников при решении рассмат риваемой задачи позднее была устранена Берном, Эпштейном и Гильбертом [5]. Они создали сеточный генератор с треугольника ми, имеющими ограничения на форму и размер, подчиняющиеся начальным данным. Кроме того, авторы показали, что строящаяся ими сетка имеет треугольники с отношением сторон, не превосхо дящим числа 5. Их алгоритм основан на идее предварительного рекурсивного разбиения области на квадраты различной формы.

Другим способом решения поставленной задачи является триан гуляция Делонэ. Обзор адекватных методов для построения триан гуляций Делонэ с множественными ограничениями можно найти в [1, 13]. Наиболее известные результаты представлены в работах Чью и Рапперта. Чью [8] представил триангуляцию Делонэ, в которой все треугольники имеют углы между 30 и 120 градусов, для области с наименьшим углом, образованным границами, не меньше 30 граду сов. Его алгоритм производит равномерную сетку.

Рапперт [12] расширил идеи Чью, предложив алгоритм триангу ляции планарного прямолинейного графа такой, что все треуголь ники выходной сетки имеют углы между и 2 ( 0 20 ), где зависит от входных ограничений. Сетка является неравно мерной. Алгоритм Рапперта, получая на вход некоторую триангуля 286 В. Н. Чугунов цию Делонэ, точно аппроксимирующую ребра графа, выдает сетку с треугольниками, удовлетворяющими ограничениям на форму. При этом начальная аппроксимация сохраняется. Таким образом, дан ный алгоритм лишь улучшает имеющуюся триангуляцию. В статье [12] доказывается, что число треугольников в выходной сетке полу чается из начального числа, умножением на константу, зависящую от.

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

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

В разделе 5 приведены примеры работы представляемого алгорит ма.

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

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

Для каждого треугольника определены две численные характе ристики качество формы и качество аппроксимации (множества ломаных). Под качеством формы Qi треугольника i понимается величина, определяемая по формуле [6, 14]:

P0 Si Si 2 = 12 3 2, Qi = (1) S0 Pi Pi где Si площадь, Pi периметр треугольника i, P0, S0 пе риметр и площадь любого равностороннего треугольника. Отметим, что Qi 1, причем Qi = 1 только для равностороннего треуголь ^ ника. Для вычисления качества аппроксимации Qi треугольника ^ (l,j) по отноше i сначала определяется качество аппроксимации Qi нию к каждому звену j каждой ломаной l : eсли звено j ломаной l пересекает треугольник i, то ^ (l,j) = 1 2 min(S1, S2 ), (2) Qi S где S площадь треугольника, а S1 и S2 площади фигур, на которые звено j ломаной l разбивает треугольник i ;

в противном случае (пересечения нет) положим ^ (l,j) = 1. (3) Qi 288 В. Н. Чугунов ^ (l,j) = 1 для треугольника i, не разбиваемого зве Таким образом, Qi ^ (l,j) опре ном j ломаной l. Как только качество аппроксимации Qi делено для каждого звена j каждой ломаной l, качество аппрокси ^ мации Qi треугольника i берется как минимум среди найденных ^ (l,j) Qi ^ (l,j) Qi = Qi.

^ (4) l j Для всей сетки также введено качество формы сетки Q и ка ^ чество аппроксимации сетки Q как минимум из соответствующих качеств треугольников Q = Qi, i (5) Q = Qi.

^ ^ i В оптимизационной задаче точной аппроксимации лома ных квази-иерархическими сетками требуется для заданного числа 0 q0 1 построить конформную квази-иерархическую треуголь ную сетку 0 на, удовлетворяющую условию = arg nt( ), (6) ^ :Q q0,Q = где nt( ) число треугольников в сетке. Другими словами, цель задачи для заданного числа q0 построить конформную треуголь ную сетку, удовлетворяющую условиям: сетка квази-иерархична;

за данные ломаные аппроксимируются сторонами треугольников, т.е.

ломаные лежат на ребрах треугольников;

треугольники имеют хо рошее качество формы;

число треугольников минимально.

Однако, оптимизационная задача точной аппроксимации лома ных достаточно сложна для решения. Заменим ее менее трудной: бу дем считать, что заданные ломаные могут аппроксимироваться сто ронами треугольников с некоторой заранее задаваемой точностью. Пусть d(i) диаметр треугольника i. Определим для каждого ^ треугольника -качество аппроксимации Q i ^ если d(i), Qi, ^i Q = (7) в противном случае, 1, ^ а для сетки -качество аппроксимации Q Q = Q.

^ ^ (8) i i О сетке, слабо -аппроксимирующей ломаные То есть, ломаная может пересекать треугольник i по линии, не сов падающей с ребром, если d(i).

Оптимизационная задача -аппроксимации ломаных состо ит в том, чтобы для заданных чисел 0 q0 1, 0 1 постро ить конформную квази-иерархическую треугольную сетку 0 на такую, что = arg nt( ). (9) ^ q0,Q = :Q Предлагаемый ниже алгоритм предназначен для решения еще более упрощенной задачи, называемой в дальнейшем задачей сла бой -аппроксимации ломаных. В этой задаче разрешается сдви гать ломаные на расстояние не больше. Как будет показано ни же, это обеспечивает построение приближенного решения задачи в некотором классе сеток. Фактически, мы рассматриваем построение квази-иерархической сетки 0, удовлетворяющей условиям Q q0, ^ Q 0 = 1 и получающейся из заданной путем как можно меньшего числа действий с узлами сетки и треугольниками. Приближенность решения обусловлена заменой условия строгой минимизации чис ла треугольников на желание получить сетку лишь с небольшим, по-возможности, числом сеточных элементов.

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

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

Структура алгоритма позволяет дополнительно локально измельчать по строенную сетку.

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

Данную задачу будем решать при следующих предположениях:

число ломаных и число звеньев в одной ломаной не больше некото рых заданных значений;

любая ломаная не имеет самопересечений;

каждая ломаная лежит в замыкании ;

ни одна из внутренних то чек любой ломаной не лежит на границе области.

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


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

При описании процесса построения сетки мы будем использовать две вспомогательные процедуры.

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

О сетке, слабо -аппроксимирующей ломаные применение к данной сетке любого числа уровней бисекций не ухуд шит качество формы сетки более, чем в два раза [11].

Также нам будет необходима операция проверки возможности сдвига S(J, R, j0, r0, q) одного узла из заданного подмножества J то ^ чек сетки в одну из точек предписанного множества R. Если все узлы в J неподвижны, процедура выдает информацию о невозмож ности сдвига, иначе она сначала строит подмножество J из всех по движных узлов в J и моделирует сдвиг каждого элемента j J в каждую из точек r R с целью найти такую пару элементов j0 J и r0 R, что при перемещении j0 в r0 треугольники не налегают друг на друга и не выворачиваются, а качество формы q(j0 ) узла j0 будет равным q(j0 )|j0 r0 = q(j)|jr, rR jJ для всех пар j, r, обеспечивающих конформность получаемой сетки.

Если такая пара нашлась, и получаемое качество формы q(j0 ) узла j0 после сдвига не ниже q, то процедура выдает на выходе пару ^ j0, r0, в противном случае выдается информация о невозможности сдвига. Заметим, что если вершина подвижна только вдоль границы, то для нее сдвиг должен моделироваться только для тех точек R, которые находятся на границе. Отметим важное свойство SD опе рации сдвига. Для любого треугольника, пересекаемого некой пря мой, содержащей его вершину, сдвиг ближайшей из других вершин (j) на прямую не ухудшит качество формы сдвигаемого узла q(j) более чем в (q) раз.

Теперь можно перейти к описанию алгоритма решения нашей задачи, который будет использовать процедуры бисекции и сдвигов узлов. Пусть начальная сетка имеет качество формы q. Будем пред полагать, что порог q0 из (9) не превосходит q/4, что необходимо для обеспечения возможности совершать бисекции и сдвиги.

3.2. Описание алгоритма. Рассматриваемый алгоритм постро ения треугольной конформной квази-иерархической сетки 0 с небольшим числом треугольников, имеющей -качество аппрок ^ симации Q 0 = 1 и качество формы Q 0 q0, на предваритель ном этапе может сдвинуть сами ломаные на величину не более.

Это обеспечивает разрешимость задачи слабой -аппроксимации ломаных для заданного q0. Алгоритм включает в себя три этапа, 292 В. Н. Чугунов дальнейшее описание каждого из которых, при необходимости, бу дет заканчиваться обоснованием возможности совершения действий, составляющих основу изложенного этапа.

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

Шаг 1-1. Строим множество Z, состоящее из точек излома, граничных точек ломаных и точек пересечения заданных ломаных (рис. 1).

Шаг 1-2. Удаляем из Z точки, которые лежат в узлах сетки, объявив соответствующие узлы сетки неподвижными. Для каждого треугольника i находим подмножество точек Zi Z, принадлежа щих этому треугольнику. Если треугольник имеет непустое множе ство Zi, формируем множество Li из трех его вершин и выполняем процедуру проверки возможности сдвига S(Li, Zi, l0, z0, 4 q0 ). Ес ли она дает положительный результат, то совершаем сдвиг l0 в z0, объявляем вершину l0 неподвижной и исключаем z0 из Z, иначе, в случае если d(i), метим данный треугольник для разбиения (рис. 2). После просмотра всех треугольников при наличии помечен ных выполняем процедуру бисекции, которая дает дополнительные степени свободы. Если множество Z пусто, то переходим к этапу 2, иначе повторяем шаг 1-2 до тех пор, пока не получим сетку, в которой любой треугольник i либо не содержит точек из Z, либо содержит только одну точку и d(i) (рис. 3).

Шаг 1-3. Для каждой точки из Z совершаем процедуру сдвига самой точки из Z на величину не более, что приводит к сдви гу ломаных не более, чем на. Для этого на треугольнике, ее со держащем, строим локальную сетку, включающую сами вершины треугольника, и из них формируем множество Ri. Определив мно жество Li из трех вершин треугольника, выполняем процедуру про верки возможности сдвига S(Li, Ri, l0, r0, 2 q0 ), которая дает поло жительный результат в силу того, что сами вершины треугольника уже принадлежат локальной сетке и их качество формы не ниже 2 q0, так как начальная сетка имела качество не хуже 4 q0, а на шаге 1-2 подвергалась лишь бисекции и сдвигам S с качеством О сетке, слабо -аппроксимирующей ломаные 4 q0. Передвигаем точку Z в эту выбранную точку локальной сетки r0. Если точка из Z точка пересечения двух или более ло маных, то находим в этих ломаных звенья, содержащих эту точку и добавляем точку из Z в упорядоченные списки точек, задающих эти ломаные. Теперь в точку Z мы можем сдвинуть вершину тре угольника l0 (рис. 4) и зафиксировать ее.

На этом первый этап алгоритма завершен. В результате получаем конформную сетку c узлами, содержащими все элементы множества Z, и качеством формы, не хуже 2 q0.

Отметим, что шаг 1-2 может производить сетку, сгущающуюся к некоторому конечному числу точек, не большему чем мощность изначального множества Z.

Достичь условия, чтобы все точки Z лежали в узлах сетки при заданном q0 возможно лишь благодаря шагу 1-3. Если q0 достаточ но велико, то в результате работы только шагов 1-1 и 1-2 совместить все точки Z с узлами сетки не в любом случае возможно, так как большое q0 не всегда дает возможность сдвига узла, а значит, про цесс из шагов 1-1 и 1-2 без ограничения на диаметр треугольников может зациклиться. Шаг 1-3 двигает сами точки Z так, чтобы для заданного q0 можно было осуществить сдвиг. В этих случаях точ ка из Z сама передвигается в узел сетки, обеспечивая требуемый результат.

Если важно гарантированно сохранить взаимное расположение ломаных, необходимо выбрать меньше четверти. Действитель но, перед шагом 1-3 точки, еще неаппроксимированные узлами сет ки, принадлежат треугольникам с диаметром не более. Поэтому сдвиг точек Z может их сблизить, но лишь до расстояния 2 = /2, что обеспечит отсутствие возможного слияния разных звеньев раз личных ломаных.

Из описания шага 1 видно, что величина сдвига ломаных зави сит от геометрии ломаных и от ;

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

Поэтому любая точка новой ломаной будет находиться на расстоя нии не более от своего прообраза на старой ломаной даже для 294 В. Н. Чугунов Рис. 1. Начальная сетка (а) Начальная сетка и за- (б) Начальная сетка данные ломаные вблизи точки сближе ния ломаных суперпозиции нескольких сдвигов.

Этап 2 приближение сторон треугольников к звеньям лома ных с иcпользованием лишь допустимых операций.

Шаг 2-1. Если все треугольники имеют -качество аппрокси мации равное единице, то переходим к этапу 3.

Шаг 2-2. Рассмотрим каждый треугольник i с -качеством ап проксимации, отличным от единицы. Если его качество аппроксима ции отлично от единицы для некоторого звена j некоторой ломаной l, и хотя бы одна из его вершин, не лежащая на l, неподвижна, то метим треугольник i для разбиения.

Шаг 2-3. Если есть помеченные треугольники, совершаем про цедуру бисекции и переходим к шагу 2-1.

Шаг 2-4. Если все треугольники имеют -качество аппрокси мации равное единице, то переходим к этапу 3.

Шаг 2-5. Для каждого треугольника i, имеющего -качество О сетке, слабо -аппроксимирующей ломаные Рис. 2. В процессе работы (а) В процессе работы (б) В процессе работы шага 1-2 шага 1-2 вблизи точки сближения ломаных аппроксимации, отличное от единицы, находим вершину, ближай шую к одному из звеньев ломаных, которое пересекает данный тре угольник не по ребру, и формируем из нее множество Li. На соот ветствующем звене строим локальную сетку на той части, которая пересекает все три суперэлемента для трех вершин треугольника, образуем из нее множество Ri и вызываем процедуру проверки воз можности сдвига S(Li, Ri, l0, r0, 2 q0 ). Если она дает отрицатель ный результат и d(i), то метим этот треугольник для последу ющего разбиения. Если она дает пару l0 и r0, то сносим l0 в r0, фиксируем l0.


Шаг 2-6. Если на шаге 2-5 произошла сдвижка хотя бы одного узла, то считаем, что нет помеченных треугольников, и переходим к шагу 2-4. В противном случае совершаем процедуру бисекции и переходим к шагу 2-4.

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

Про сдвиги S узлов мы требуем, чтобы качество было не хуже 2 q0, так как треугольники, которые уже аппроксимировали лома ные, при выполнении алгоритма могут подвергаться бисекциям для обеспечения конформности сетки. Но по свойству KBS их качество не ухудшиться более чем в два раза, то есть их качество будет не меньше q0. Из описания видно, что второй этап это повторяю щиеся процедуры выполнения шагов 2-1 2-3 и шагов 2-4 2-6.

В качестве примера на (рис. 5 6) приведены сетки после второго и четвертого повторений шагов 2-4 2-6.

Этап 3 улучшение качества формы сетки за счет сдвижки подвижных узлов, если это возможно.

О сетке, слабо -аппроксимирующей ломаные Рис. 4. После этапа (а) После этапа 1 (б) После этапа 1 вбли зи точки сближения ло маных 4. Анализ алгоритма.

В этом разделе опишем основные свойства алгоритма и сделаем некоторые важные замечания.

Свойство I. Представленный алгоритм строит треугольную конформную квази-иерархическую сетку 0, которая имеет -качество ^ аппроксимации Q 0 = 1 и качество формы Q 0 q0, предвари тельно при необходимости сдвинув ломаные на величину не более.

Отметим, что в случае /4 расстояние между любыми двумя непересекающимися звеньями остается меньше /2. Таким образом, взаимное расположение ломаных сохраняется после сдвига.

Свойство II. Алгоритм построения конформной треугольной квази-иерархической сетки, слабо аппроксимирующей ломаные с точностью, конечен.

Действительно, поскольку диаметр треугольника не меньше, 298 В. Н. Чугунов Рис. 5. После двух повторений шагов 2-4 2- (а) После двух повторе- (б) После двух повторе ний шагов 2-4 2-6 ний шагов 2-4 2-6 вли зи точки сближения ло маных то число уровней разбиения не превышает 2 2 1, т. е. конечно.

Свойство III. Пусть сетка после шага 2-3 имеет качество фор мы q. Шаги 2-5 2-6 алгоритма могут ухудшить качество формы не больше, чем в 22 (q) раз, где (q) константа из свойства SD опе рации сдвига. Поэтому порог качества формы должен выбираться с ограничением q0 q/22 (q). Действительно, рассмотрим отрезок звена ломаной, который еще не аппроксимирован ребрами треуголь ников, не содержит внутри узлов сетки, и не является частью дру гого большего отрезка, также не аппроксимированного ребрами тре угольников. Отметим, что концы этого отрезка лежат в узлах сетки, а в силу окончания шагов 2-1 2-3 любой треугольник, пересекаю щий данный отрезок, не имеет неподвижных вершин, не лежащих на рассматриваемом отрезке.

Рассмотрим следующую последовательность действий для ап О сетке, слабо -аппроксимирующей ломаные Рис. 6. После четырех повторений шагов 2-4 2- (а) После четырех повто- (б) После четырех повто рений шагов 2-4 2-6 рений шагов 2-4 2- влизи точки сближения ломаных проксимации данного отрезка. Возьмем треугольник i, пересекаю щийся с данным отрезком не по ребру, и содержащий один из концов отрезка (рис. 7).

При данном малом q0 мы можем сдвинуть на ломаную ближай шую из вершин j0 данного треугольника. По свойству SD качество формы сдвинутого узла ухудшится не более, чем в раз ( q/ ).

При этом сдвиг j0 сразу ставит на ломаную целое ребро, изменяя качество формы только у треугольников из суперэлемента j0, но улучшая до единицы качество аппроксимации для треугольника i относительно звена, содержащего рассматриваемый отрезок. После сдвига j0 в суперэлементе j0 появляется лишь один треугольник (скажем i0 ) с плохим качеством аппроксимации относительно ис следуемого звена, и содержащий узел j0 (рис. 8). Его качество фор мы не хуже q/.

300 В. Н. Чугунов Рис. 7. Начальное расположение треугольников и звена ломаной   f  f %%   f %%   d %% f  id % f   % rr d%% f r j0 %d f rr %% d j f %   e%     % %e     %% e     %%  e    %%  e    %%rr i rr r Далее, алгоритм сдвинет на ломаную узел j1, ближайшую вер шину треугольника i0. Несмотря на возможно новое ухудшение ка чество формы треугольника i0 до q/2 после сдвига узла j1 (со гласно свойству SD ), он начинает аппроксимировать ломаную. По этому далее суперэлемент j0 не будет подвергаться сдвигам.

По аналогии с узлом j0 после сдвига узла j1 у нас появится треугольник i1 с качеством аппроксимации, отличным от едини цы, и содержащий вершину j1. Этот треугольник имеет качество формы не меньше q/ (свойство SD ), так как он не принадлежит суперэлементу j0 и до сдвига j1 имел качество формы не меньше q, поэтому для него можно применить операцию сдвига узла. Зна чит, возможен последовательный процесс аппроксимации ломаных, который не приведет к цепочке наращиваемого ухудшения качества формы каких-нибудь треугольников, а будет поддерживать качество формы аппроксимирующих треугольников не ниже q/2. Последу ющие возможные бисекции аппроксимирующих треугольников для сохранения конформности сетки могут ухудшить их качество фор мы не более чем в два раза (до q/22 ) по свойству KSD.

Поскольку любая последовательность действий в шагах 2-5 2 О сетке, слабо -аппроксимирующей ломаные Рис. 8. Расположение треугольников и звена ломаной после сдвига узла.

  f  f %%   f %%    d %% f  d % f    i0 % d%% i1 f e  e %%d j1 f  e % d f $  % $ %$$$$     e j0  %$ e%%$     $$  %rr     % %% rr     % r    %r i % rr rr 6 представляется как совокупность последовательностей, аналогич ных только что рассмотренной последовательности, оценки качества формы переносятся на случай произвольного выполнения сдвигов.

Это и доказывает свойство III.

Теперь перейдем к вопросу об оценке числа треугольников в за висимости от величины. Рассмотрим сетку, получающуюся рав номерным измельчением исходной. Диаметр любого треугольника в полученной сетке меньше, а поэтому имеет площадь меньше O(2 ). Следовательно, число треугольников в результирующей сет ке O(2 ).

Оценим число треугольников для сетки, которая имеет сгущение к линиям. Рассмотрим любое звено заданной ломаной. Пусть его длина l, а число треугольников, которое оно пересекает (включая пересечение по стороне) n. Тогда l пропорционально n, т. е. n пропорционально l/. Следовательно, число треугольников в такой сетке O(1 ).

Теперь проанализируем алгоритм, описанный в предыдущем па раграфе. Вопрос об оценке числа треугольников зависит от взаим 302 В. Н. Чугунов Рис. 9. Расположение треугольников, приводящее к возможному сгу щению сетки rr Y  r% r% %%   %   %   %%   %   % %d e g % g %% d e d e %% g e d %% g d % %dg %%  d g % g d % $$$  X %% rr  $$$ r$ % $ r ного расположения заданных ломаных. Если, то алгоритм ре шения задачи слабой -аппроксимации ломаных около точек сбли жения непересекающихся звеньев может порождать сетку, сгуща ющуюся к линии. В частности, если существуют два звена, распо ложенные параллельно на расстоянии, то алгоритм произведет сетку со сгущением к звену, и поэтому имеющую число треуголь ников порядка O(1 ). Поэтому в дальнейшем будем считать, что.

Свойство IV. Алгоритм, описанный в предыдущем параграфе, будет иметь число треугольников не больше 2 1.

при Это следует непосредственно из следующей теоремы.

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

О сетке, слабо -аппроксимирующей ломаные Рис. 10. Начальная сетка и сетка после этапа 1, q0 = 0. Действительно, рассмотрим сетку, сгущающуюся к одной точке.

Для достижения условия, что диаметр треугольника вблизи точки сгущения стал меньше, необходимо совершить O( 2 1 ) бисек ций, а каждая бисекция порождает лишь ограниченное число тре угольников по свойству BS. Следовательно, сетка с одной точкой сгущения имеет O( 2 1 ) число треугольников. Если число то чек сгущения O( 2 1 ), то число треугольников в сетке имеет порядок ( 2 1 ).

Доказательство.

Из описания алгоритма легко видеть, что смысл первого эта па заключается в аппроксимации только лишь точек множества Z.

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

Так как третий этап алгоритма вообще не производит бисекций, то для доказательства теоремы достаточно показать, что именно второй этап алгоритма при достаточно малом производит сетку, сгущающуюся к числу точек порядка O( 2 1 ).

Так как, число повторений шагов 2-1 2-3 не зависит от. Действительно, поскольку расстояние от любой неподвижной точки до любого звена, не содержащего эту точку, не меньше 0.9, 304 В. Н. Чугунов Рис. 11. Сетки после этапов 2 и 3, q0 = 0. то измельчение треугольников, пересекающих звено, до диаметра 0.5 обеспечит отсутствие у них неподвижных вершин. Получаем, что число повторений шагов 2-1 2-3 определяется лишь располо жением задаваемых ломаных и не зависит от. Поэтому проана лизируем лишь шаги 2-4 2-6. Пусть после шага 2-3 сетка имела качество формы q, а q0 = 0.1 q.

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

Начав работу с этим отрезком, алгоритм станет сносить на него вершины. В силу малости q0 шаги 2-4 2-6 будут проходить без бисекций до тех пор, пока среди m пересекающих XY треугольни ков не выделится m1 пар треугольников, имеющих общее ребро, пересекающее XY, и противоположные общему ребру вершины, ле жащие на XY (рис. 9). Получив множество таких пар, алгоритм О сетке, слабо -аппроксимирующей ломаные Рис. 12. Сетки после этапов 2 и 3, q0 = 0.21. Сгущения порождены шагами 2.4-2. попытается снести на ломанную ближайшую общую вершину двух треугольников. Это не всегда возможно, так как сносимая вершина принадлежит суперэлементам сразу двух вершин, уже снесенных на XY в результате последовательных процессов аппроксимации лома ной, происходящих по разные стороны от рассматриваемой пары треугольников. Ограничение снизу на качество формы этих супер элементов может воспрепятствовать сносу вершины, обеспечиваю щей аппроксимацию ломаной. В этом случае начнется процесс би секций, который будет порождать сетку с сгущением к точке пе ресечения общего ребра исследуемой пары треугольников и отрез ка XY. Поэтому в результате работы алгоритма мы получим сетку, сгущающуюся не более к m1 точкам, число которых не более, чем O( 2 1 ).

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

306 В. Н. Чугунов 5. Примеры сеток, построенных с помощью алго ритма.

Рассмотрим два примера работы нашего алгоритма, в которых иллюстрируется свойство IV. Напомним, что оценка числа треуголь ников в теореме является оценкой сверху: появление точек сгуще ния на этапах 1 и 2 зависит от взаимного расположения заданных ломаных и начальной сетки и от порога качества формы треуголь ников q0. Как правило, при умеренных значениях q0 сгущения не происходит ни на этапе 1, ни на этапе 2 даже при малых, как это продемонстрировано на рис. 10 11 для = 0.008 и q0 = 0.15. Более высокий порог качества формы приводит к появлению точек сгуще ния, см. рис. 12. Отметим, что малость влияет лишь на глубину сгущения, но не на появление точек сгущения.

6. Заключение В работе рассмотрено несколько постановок оптимизационных задач по генерации сеток, удовлетворяющих множественным огра ничениям. Для одной из них предложен и проанализирован алго ритм построения квази-иерархической сетки, которая может рас сматриваться как некоторое приближение к решению в соответству ющем классе сеток. Характерной особенностью алгоритма являет ся его робастность, что достигается аппроксимацией ограничений с точностью и возможностью локального -возмущения заданных ограничений. Улучшение аппроксимации ломаных ( 0 ) приво дит к росту числа элементов сетки, не превышающем 2 1.

Список литературы [1] Скворцов A. Триангуляция Делонэ и ее применение. Томск, Издательство Том. ун-та. 2002.

[2] Шайдуров В. В. Многосеточные методы конечных элементов.

Москва, Наука. 1989.

[3] Baker B., Grosse E., Raerty C. S. Nonobtuse triangulation of polygons / Disc. and Comput. Geom. 1998. V. 3. P. 147–168.

/ [4] Bnsch E. Local mesh renement in 2 and 3 dimensions / IMPACT a / of Computing in Science and Engrg. 1991. V. 3. P. 181–191.

О сетке, слабо -аппроксимирующей ломаные [5] Bern M., Eppstein D., Gilbert J. R. Provably good mesh generation / Proceedings of the 31st Annual Symposium on Foundations of / Computer Science. 1990. IEEE. P. 231–241.

[6] Buscaglia G., Dari E. Anisotropic mesh optimization and its application in adaptivity / Inter. J. Numer. Meth. Engng. 1997.

/ V. 40. P. 4119–4136.

[7] Carey G. Computational grids. Generation, adaptation, and solution strategies. London. Taylor and Francis. 1997.

[8] Chew L. P. Guaranteed-quality mesh generator for curved surfaces / Proceedings of the Ninth Annual Symposium on / Computational Geometry. 1993. ACM. P. 274–280.

[9] Frey P., George P.-L. Maillages: applications aux lment nis.

ee Paris. Herms Science Publications. 1999.

e [10] Liseikin V. Grid generation methods. Springer. Berlin Heidelberg.

1999.

[11] Rivara M. Mesh renement processes based on the generalized bisection of simplexes / SIAM J. Numer. Anal. 1984. V. 21. P.

/ 604–613.

[12] Ruppert J. A Delaunay renement algorithm for quality 2 dimensional mesh generator / Journal of Algorithms. 1995. V. 18.

/ N. 3. P. 548–585.

[13] Shewchuk J. Delaunay renement algorithms for triangular mesh generation / Computational Geometry: theory and / applications. 2002. V. 22 (1-3). P. 21–74. См. также http://www 2.cs.cmu.edu/ jrs/jrspapers.html#cdt [14] Vassilevski Yu., Lipnikov K. Adaptive algorithm for generation of quasi-optimal meshes / Comp. Math. Math. Phys.. 1999. V. 39.

/ P. 1532–1551.

[15] http://www-users.informatic.rwth-aachen.de/ roberts/meshgeneration.html [16] http://www.engr.usask.ca/ macphed/finite/fe_resources/mesh.html СОДЕРЖАНИЕ Предисловие..................................................... Вл. В. Воеводин НИВЦ МГУ: широким фронтом совместных дел......... А. В. Адинец, Н. А. Сахарных О системе программирования вычислений общего назначения на графических процессорах................... А. С. Антонов Влияние характеристик программно-аппаратной среды на производительность приложений...................... Г. А. Бочаров, Н. А. Медведева Численные алгоритмы анализа чувствительности и сложности описания в задачах идентификации моделей математической иммунологии Вад. В. Воеводин, С. И. Соболев, А. В. Фролов Архитектура и принципы реализации коллективного банка тестов в сети Интернет........................... П. А. Гаврилушкин Структура и производительность подсистем памяти современных вычислительных платформ....... С. А. Горейнов Об оценке сходимости метода бидиагонализации........ А. А. Данилов Построение тетраэдральных сеток для областей с заданными поверхностными триангуляциями........... С. А. Жуматий Комплексный подход к обслуживанию вычислительных кластеров................................. С. А. Жуматий, С. И. Соболев Оценка загруженности компьютера в различных UNIX-системах............................... О. С. Лебедева, Е. Е. Тыртышников Размерности коммутативных матричных алгебр....... Д. А. Никитенко Топ50. Рейтинг наиболее производительных вычислительных систем СНГ.............................. К. Д. Никитин Технология расчета течений со свободной границей с использованием динамических гексаэдральных сеток.. Д. В. Савостьянов Алгоритмы слепого разделения источников в пакетном режиме......................................... Д. В. Савостьянов, С. Л. Ставцев, Е. Е. Тыртышников Об использовании мозаично-скелетных аппроксимаций при решении гиперсингулярных интегральных уравнений.................................... С. И. Соболев Эффективная работа в распределенных вычислительных средах..................................... К. С. Стефанов Технологический инструментарий для построения систем анализа и преобразования структуры программ.......... Е. Е. Тыртышников Метод скачков и аппроксимации Паде..................... В. Н. Чугунов Об алгоритме построения конформной квази-иерархической треугольной сетки, слабо -аппроксимирующей заданные ломаные............................................ Научное издание Численные методы, параллельные вычисления и информационные технологии Сборник научных трудов под ред. Вл. В. Воеводина и Е. Е. Тыртышникова Оригинал-макет изготовлен в ИВМ РАН Подписано в печать 28.01.2008 г.

Формат 60 84 1 16. Печать офсетная. Бумага офсетная № / Усл. печ. л. 20,0. Уч.-изд. л. 21,5. Тираж 250 экз. Заказ №1.

Ордена Знак почета Издательство Московского университета 125009, Москва, ул. Б. Никитская, 5/7.



Pages:     | 1 |   ...   | 4 | 5 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.