Параллельные алгоритмы сжатия результатов численного моделирования трехмерных задач гидродинамики тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Муравьев, Сергей Владимирович

• Муравьев, Сергей Владимирович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Муравьев, Сергей Владимирович

Введение.

Глава 1. Обтекание усеченной сферы.

Постановка задачи и математическая модель.

Численная реализация.

Глава 2. Сжатие сеточных данных.

Особенности входных и выходных данных.

Обзор существующих методов сжатия.

Аппроксимация сеточных данных.

Общая схема многоэтапного сжатия.

Глава 3. Визуализация трехмерных скалярных данных.

Изоповерхности и сечения.

Сжатие триангулированных поверхностей.

Однопроцессорное сжатие.

Параллельное сжатие.

Интерактивная система распределенной визуализации.

Сжатие трехмерных скалярных данных.

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

Глава 4. Результаты.

Моделирование обтекания усеченной сферы.

Сжатие поверхностей.

Однопроцессорное сжатие.

Параллельное сжатие.

Сжатие трехмерных скалярных данных.

Введение диссертации (часть автореферата) на тему «Параллельные алгоритмы сжатия результатов численного моделирования трехмерных задач гидродинамики»

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

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

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

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

Моделирование трехмерных газодинамических течений. В современной науке широко используется метод математического моделирования [3,4]. Его сущность состоит в замене исходного объекта его «образом» - математической моделью, отражающей его основные свойства, -и дальнейшем исследовании полученной модели. Работа с моделью объекта (явления, процесса) дает возможность относительно быстро и без существенных затрат исследовать его свойства и поведение в различных ситуациях. До появления ЭВМ изучение математических моделей выполнялось в основном аналитическими методами. С появлением компьютеров для исследования математических моделей большое распространение получил вычислительный эксперимент [5]. В современном математическом моделировании используются новейшие численные методы, реализуемые на быстродействующих вычислительных машинах. Вычислительные (компьютерные) эксперименты с моделями объектов позволяют, опираясь на мощь современных вычислительных методов и технических инструментов, подробно и глубоко изучать объекты в достаточной полноте, недоступной чисто теоретическим подходам. В отличие от аналитических методов, где зачастую для каждой задачи разрабатываются свои самостоятельные приемы решения, численные методы отличаются большой универсальностью и применимы для исследования широкого класса явлений.

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

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

В работе рассматривается задача вязкого газодинамического обтекания (рисунок 1). Обтекаемая поверхность, выбранная для исследования, представляет собой усеченную сферу. Какое-либо вращение обтекаемого тела не рассматривается. В качестве математической модели для исследования газодинамических течений используется система уравнений Навье-Стокса.

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

Рис. 1. Обтекание усеченной сферы газовым потоком.

Пространственная дискретизация уравнений Навье-Стокса выполнялась на нерегулярных тетраэдральных сетках [6,7]. Заметим, что аппроксимация на нерегулярных сетках обычно уступает по точности аппроксимации с использованием регулярных сеток [8,9]. Кроме того, нерегулярная сетка требует явного описания всех ее элементов (например, тетраэдров или треугольников), чего можно избежать в случае со структурированными сетками (например, кубическими решетками). Однако подобные недостатки нерегулярных сеток компенсируются их полезными свойствами. Плотность узлов нерегулярной сетки может меняться по пространству в достаточно широких пределах. При этом при генерации сетки можно сосредоточить большинство узлов в подобластях, где необходимо исследовать более детальную картину процесса и получить решение с повышенной точностью. К указанным подобластям могут относиться участки с сильно меняющимся решением, а также любые другие области, • наиболее важные или интересные для исследователя. Кроме того, нерегулярные сетки дают возможность с высокой точностью аппроксимировать поверхности сложной формы, в результате чего можно более точно задать границы геометрической области, внутри которой исследуются физические процессы.

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

В настоящее время существует большое число программных средств визуализации данных на персональном компьютере (ПК). Это такие программные пакеты как Tecplot [10-13], Origin [14], EasyPlot [15], IRIS Explorer [16] и ряд других. Данные пакеты обладают широким набором функциональных возможностей по визуализации и исследованию различного рода научных данных.

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

В течение последних нескольких лет появился ряд профессиональных программных средств параллельной визуализации (например, Visapult [17,18], ParaView [19], OpenDX [20], EnSight [21] и др. [22]) Большинство из них ориентировано на такие условия функционирования, при которых компьютер пользователя находится в непосредственной близости от суперкомпьютера или соединен с ним высокоскоростной сетевой средой. Кроме того, имеющиеся разработки проблематично, а иногда просто невозможно доработать или переделать под конкретные желаемые условия, если это окажется необходимым. По этим причинам необходимо создание специализированного средства для визуализации научных данных большого объема.

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

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

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

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

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

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

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

Четвертая задача - возможность различных манипуляций с отображаемыми данными, например:

• тран сформация, позволяющая осуществлять сдвиг, поворот, перемасштабирование, отражение и т.д.;

• цветов ые преобразования, изменение освещенности и теней;

• до полнительное сжатие и фильтрация в зависимости от текущего положения точки наблюдения;

• ото бражение дополнительных объектов, например, координатной сетки;

• базов ые операции статистического анализа: вычисление среднего, дисперсии, построение аналитических графиков;

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

Обычно результаты трехмерного моделирования задач гидродинамики представляют собой трехмерные скалярные данные. Для визуализации подобных данных можно использовать различные методы [26-30]. Например, можно выделять плоскость (или срез) из исследуемого объема. Полученная таким образом информация является уже двумерной и может быть непосредственно выведена на экран, «отражая» значение исследуемой функции, например - цветом. Рассматривая набор срезов между границами области, можно получить представление о распределении значений исследуемой функции в трехмерном объеме. Недостатком подобного подхода является то, что пользователь одновременно видит лишь небольшую часть данных - их плоский срез.

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

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

Таким образом, в качестве основных типов обрабатываемых данных рассматриваются «поверхности» (изоповерхности некоторого скалярного физического параметра) и трехмерные скалярные данные (непосредственно само распределение исследуемого физического параметра).

Сжатие данных. Современное моделирование различных задач гидродинамики обычно выполняется на высокопроизводительных МВС с распределенной памятью. Увеличение числа вычислительных модулей МВС позволяет выполнять расчеты на все больших сетках. В настоящее время обычным является использование сеток порядка 108-109 узлов. Результаты подобных вычислений - трехмерные сеточные данные - занимают объем, превышающий размер оперативной памяти персонального компьютера, который обычно используется для анализа результатов расчетов. Кроме того, крупномасштабные вычислительные эксперименты обычно проводятся на

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

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

Сжатие данных - процесс, обеспечивающий уменьшение объема данных путем сокращения их избыточности. Сжатие данных широко используется в программах архивации и системах управления базами данных, а также для хранения графической, аудио- и видеоинформации [32,33].

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

Различают сжатие данных без потерь (lossless compression) и сжатие с потерями (lossy compression).

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

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

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

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

К наиболее известным алгоритмам сжатия без потерь можно отнести алгоритм Хаффмана [34], алгоритм RLE (Run Length Encoding) [35], алгоритмы группы KWE (KeyWord Encoding) [36,37], арифметическое кодирование [38] и ряд других.

Примеры форматов сжатия без потери информации:

• GIF, TIFF - для графических данных;

• ZIP, ARJ, RAR, CAB, LH - для произвольного типа данных.

Среди широко используемых методов сжатия с потерями можно особо выделить алгоритм JPEG (Joint Photographie Expert Group) для сжатия растровых изображений [32], семейство алгоритмов MPEG (Moving Picture Experts Group) для сжатия видеоданных [39] и алгоритм МРЗ (MPEG Audio Layer-3) для сжатия аудиоданных [40]. Для сжатия данных иных типов обычно разрабатываются и применяются отдельные специальные методы.

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

Сжатие без потерь решает лишь проблему избыточности представления данных, но не избыточности самих данных. Подобное сжатие облегчает только хранение и передачу, но (в отличие от сжатия с потерями) не решает проблему использования (в частности визуализации) данных большого объема. Таким образом, для целей визуализации необходимо использовать методы сжатия с потерями.

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

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

Основной из разработанных алгоритмов сжатия используется в пакете моделирования задач механики сплошной среды [31], разрабатываемом в ИММ РАН в рамках государственного контракта отделения математических наук РАН.

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

Структура и краткое содержание диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем составляет 130 машинописных страниц, текст содержит 35 рисунков и 8 таблиц.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Муравьев, Сергей Владимирович

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

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

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

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

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

Заключение

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

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

2. Корнеев В.В. Параллельные вычислительные системы. М., Нолидж, 1999.-311 с.

3. Самарский А. А., Михайлов А. П. Математическое моделирование. Идеи. Методы. Примеры. 2-е изд., испр. - М.: Физматлит, 2001. - 316 с. -ISBN 5-9221-0120-Х.

4. Введение в математическое моделирование. Учебное пособие. Под ред. Трусова П. В. М.: Логос, 2005. - 439 с. - ISBN 5-98704-037-Х.

5. Самарский А.А. Математическое моделирование и вычислительный эксперимент // Вестник АН СССР. 1979. - №5. - с. 38-49.

6. Самарский А.А., Попов Ю.П. Разностные схемы газовой динамики. -М.: Наука, 1975.-350 с.

7. Самарский А.А., Колдоба А.В., Повещенко Ю.А., Тишкин В.Ф., Фаворский А.П. Разностные схемы на нерегулярных сетках. Минск, 1996. -276 с.

8. Tecplot ADK User's Manual, by Tecplot, Inc; co-published with On Demand Manuals a division of Trafford Holdings Ltd.

9. Tecplot CFD Analyzer Users Manual, by Tecplot; co-published with On Demand Manuals a division of Trafford Holdings Ltd.

10. Tecplot Reference Manual, by Tecplot , Inc; co-published with OnDemandManuals.com - a division of Trafford Holdings, Ltd.13. www.tecplot.com

11. Origin V75 User's Manual. OriginLab Corporation (www.originlab.corn). 2003.15. www.spiralsoftware.com/ep/eplot.html

12. IRIS Explorer™ Documentation (Windows NT®/2000) 2000 The Numerical Algorithms Group Ltd.17. www-vis.lbl.gov/Research/visapult2/

13. Д. Роджерс, Дж. Адаме. Математические основы машинной графики. М.: из-во "Мир", 2001. 603 с.

14. Блинова Т.А. Компьютерная графика: Учеб. пос./ Т.А. Блинова, В.Н. Порев; Под ред. В.Н. Порева. Киев: Изд-во "ЮНИОР", 2006. - 520с.: ил.+CD-ROM. - ISBN 966-7323-48-Х.

15. М. Ikits, J. Kniss, А. Е. Lefohn, С. Hansen. Volume Rendering Techniques. In GPU Gems: Programming Techniques, Tips and Tricks for RealTime Graphics, chapter 39. Edited by Randima Fernando, Addison Wesley, pp. 667-692, 2004.

16. David Kenwright. Visualization Algorithms for Gigabyte Datasets. Siggraph '97 course notes. ACM Siggraph, August, 1997.

17. T.T. Elvins. A survey of algorithms for volume visualization. Computer Graphics (ACM Siggraph Quarterly), 26(3): 194-201, Aug 1992.

18. W. Schroeder, K. Martin, B. Lorensen. The Visualization Toolkit: An Object Oriented Approach to 3D Graphics 3rd Edition. Kitware, Inc.; Feb, 2003, ISBN: 1 1-930934-07-6.

19. D. Bartz and M. Meiner. Voxels versus Polygons: A Comparative Approach for Volume Graphics. In Proc. of Volume Graphics, pages 33-48, 1999.

20. C.D. Hansen, C.R. Johnson. The Visualization Handbook. Edited by C.D. Hansen and C.R. Johnson, Elsevier, 2005. ISBN: 0-12-387582-X.

21. Четверушкин Б.Н., Гасилов В.А. и др. Пакет прикладных программ GIMM для решения задач гидродинамики на многопроцессорных вычислительных системах. Математическое моделирование, 2005, том 17, номер 6, стр. 58-74.

22. Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2003. - 384 с. - ISBN: 5-86404-170-Х.33. www.compression.ru

23. Huffman, D. A., "A Method for the Construction of Minimum Redundancy Codes", Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.

24. Golomb S.W. Run-length encoding. IEEE Tr. Inf. Theory IT-12, (1966), p. 399-401.

25. Ziv J., and Lempel, A. Compression of individual sequences via variablerate coding. // IEEE Trans. Inf. Theory IT-24, 5 (Sept. 1978), p. 530-536.

26. Welch Т.A. A technique for high-perfomance data compression. // IEEE Comput. 17, 6 (June 1984), p. 8-19.

27. Rubin F. 1976. Experiments in text file compression. Commun. ACM 19, 11,617-623.39. www.armosvstems.ru/system/compression mpeg.ahtm40. www.iis.fraunhofer.de/amrn/techinf/layer3/

28. Якобовский M.B. Распределенные системы и сети. Учебное пособие. М.: МГТУ «Станкин», 2000. - 118 с.

29. Dervieux A., Desederi J.A. Compressible Flow Solvers using Unstructured Grid, Rapport INRIA, No. 1732, 1992.

30. К.Флетчер. Численные методы на основе метода Галеркина. М.: Мир, 1988.-352 с.

31. Т. J. Barth and D. CJespersen , The Design and Application of Upwind Schemes on Unstructured Meshes, AIAA paper 89-0366, 1989.

32. Roe L. Approximate Riemann Solvers, Parameter Vectors, and Difference Schemes, J. Сотр. Phys.,1981,43, p.357-372.

33. Van Leer В., Towards the Ultimate Conservative Difference Scheme. V. A Second-Order Sequel to Godunov's Method, J. Сотр. Phys.,1979, 32, p.101-136.

34. Jameson A. Numerical Solution of the Euler Equations for Compressible inviscid Fluids, Numerical. Methods for the Euler Equations of Fluid Dynamics, 1985, SIAM,Philadelphia, p. 199.

35. Iakobovski M.V., Krinov P.S., Muravyov S.V. Large data volume visualization on distributed multiprocessor systems. // Book of Abstracts. Parallel Computational Fluid Dynamics. «Янус-К». 2003. p.301-304.

36. Муравьев C.B. Сжатие научных данных большого объема для обеспечения возможности их визуализации. Материалы 5 международного научно-практического семинара Нижний Новгород, 2005. УДК 681.3.012:51 ББК 32.973.26-018.2:22 стр. 182.

37. Hirsh С. Numerical computation of internal and external flows. Vol.2, Wiley Interscience, 1990.

38. Carl Erikson. Polygonal simplification: An overview. Technical Report TR96-016, Department of Computer Science, University of North Carolina -Chapel Hill, February 16, 1996.

39. J. Rossignac, editor. Geometric Simplification (ACM SIGGRAPH Course Notes No.35). ACM Press, 1996.

40. P. Heckbert and M. Garland. Survey of surface simplification algorithms. Technical report, Carnegie Mellon University Dept. of Computer Science, 1997.

41. P. Cignoni, C. Montani and R. Scopigno. "A comparison of mesh simplification algorithms". Computers and Graphics 22 (1998), pp.37-54.

42. E. Puppo and R. Scopigno. Simplification, LOD, and Multiresolution-Principles and Applications. Technical Report C97-12, CNUCE, C.N.R., Pisa (Italy), June 1997. (also in: EUROGRAPHICS'97 Tutorial Notes, Eurographics Association, Aire-la-Ville (CH)).

43. Josie Wernecke. The Inventor mentor: programming Object-oriented 3D graphics with Open Inventor. Addison Wesley, 1994.

44. The Virtual Reality Modeling Language Specification Version 2.0, August 1996.

45. Hoppe, H., DeRose, Т., Duchamp, Т., McDonald, J., Stuetzle, W. Surface Reconstruction from Unorganized Points. Proceedings of the 19th annual conference on Computer graphics, Pages 71-78, 1992.

46. Amenta, N., Bern, M., Kamvysselis, M. A new Voronoi-based surface reconstruction algorithm. Proceedings of the 25th annual conference on Computer graphics and interactive techniques. July 1998.

47. Bernardini, F.; Mittleman, J.; Rushmeier, H.; Silva, C.; Taubin, G. The ball-pivoting algorithm for surface reconstruction. Visualization and Computer Graphics, IEEE Transactions on, Volume: 5 Issue: 4, Oct.-Dec. 1999. Page(s): 349 -359.

48. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999.

49. Owen, Steven J. "A Survey of Unstructured Mesh Generation Technology", Proceedings, 7th International Meshing Roundtable, Sandia National Lab, pp.239-267, October 1998.

50. Borouchaki, H. and S.H. Lo. "Fast Delaunay triangulation in three dimensions", Computer methods in applied mechanics and engineering, Elsevier, Vol 128, pp.153-167, 1995.

51. Pav, Steven E. and Noel J. Walkington. "Robust Three Dimensional Delaunay Refinement", Proceedings, 13th International Meshing Roundtable, Williamsburg, VA, Sandia National Laboratories, SAND #2004-3765C, pp.145156, September 19-22 2004.

52. M.J. De Haemer and M.J. Zyda. Simplification of objects rendered by polygonal approximations. Computers & Graphics, 15(2): 175-184,1991.

53. P. Hinker and C. Hansen. Geometric optimization. In IEEE Visualization '93 Proc., pages 189-195, October 1993.

54. A.D. Kalvin and R.H. Taylor. Superfaces: Poligonal mesh simplification with bounded error. IEEE C.G.&A., 16(3):64-77, 1996.

55. William J. Schroeder, Jonathan A. Zarge, and William E. Lorensen. Decimation of triangle meshes. In Edwin E. Catmull, editor, ACM Computer Graphics (SIGGRAPH '92 Proceedings), volume 26, pages 65-70, July 1992.

56. R. Ronfard and J. Rossignac. Full-range approximation of triangulated polyhedra. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):67-76, 1996.

57. M.E. Algorri and F. Schmitt. Mesh simplification. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):78-86,1996.

58. P. Lindstrom and G. Turk. Fast and memory efficient polygonal simplification. In IEEE Visualization, pages 279-286, 1998.

59. B. Hamann. A data reduction scheme for triangulated surfaces. Computer Aided Geometric Design, 11 (2): 197-214, 1994.

60. Garland, M. and Heckbert, P. S. Surface Simplification using Quadric Error Metrics. Proceedings of SIGGRAPH 97. In Computer Graphics Proceedings, Annual Conference Series, 1997, ACM SIGGRAPH, pp. 209-216.

61. J. Cohen, A. Varshney, D. Manocha, G. Turk, H.Weber, P. Agarwal, F. Brooks, andW. Wright. Simplification envelopes. In Computer Graphics Proc., Annual Conf. Series (Siggraph '96), ACM Press, pages 119-128, Aug. 6-8 1996.

62. Marc Soucy and Denis Laurendeau. Multiresolution surface modeling based on hierarchical triangulation. Computer Vision and Image Understanding, 63(1):1—14, 1996.

63. A. Ciampalini, P. Cignoni, C. Montani, and R. Scopigno. Multiresolution decimation based on global error. The Visual Computer, 13(5):228-246, June 1997.

64. C. L. Bajaj and D.R. Schikore. Error bounded reduction of triangle meshes with multivariate data. SPIE, 2656:34-45,1996.

65. R. Klein, G. Liebich, and W. Strafler. Mesh reduction with error control. In R. Yagel and G. Nielson, editors, Proceedings of Visualization '96, pages 311318, 1996.

66. Greg Turk. Re-tiling polygonal surfaces. In Edwin E. Catmull, editor, ACM Computer Graphics (SIGGRAPH '92 Proceedings), volume 26, pages 5564, July 1992.

67. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. Mesh optimization. In ACM Computer Graphics Proc., Annual Conference Series, (Siggraph '93), pages 19-26, 1993.

68. H. Hoppe. Progressive meshes. In ACM Computer Graphics Proc., Annual Conference Series, (Siggraph '96), pages 99-108, 1996.

69. M. Reddy. Scrooge: Perceptually-driven polygon reduction. Computer Graphics Forum, 15(4): 191-203, 1996.

70. K.L. Low and T.S Tan. Model simplification using vertex clustering. In 1997 ACM Symposium on Interactive 3D Graphics, pages 75-82, 1997.

71. M. Garland, "Multiresolution Modeling: Survey & Future Opportunities", State of the Art, Eurographics, pp.111-131,1999.

72. Lori Scarlatos and Theo Pavlidis. Hierarchical triangulation using cartographic coherence. CVGIP: Graphical Models and Image Processing, 54(2):147-161, March 1992.

73. C. Andujar, D. Ayala, P. Brunet, R. Joan-Arinyo, and J. Sole'. Automatic generation of multiresolution boundary representations. Computer Graphics Forum (Eurographics'96 Proc.), 15(3):87-96,1996.

74. David Luebke and Carl Erikson. View-dependent simplification of arbitrary polygonal environments. In SIGGRAPH 97 Proc., August 1997.

75. Enrico Puppo, Larry Davis, Daniel DeMenthon, and Y. Ansel Teng. Parallel terrain triangulation. Intl. J. of Geographical Information Systems, 8(2): 105-128,1994.

76. Michael Garland and Paul S. Heckbert. Fast polygonal approximation of terrains and height fields. Technical Report CMU-CS-95-181, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA, September 1995.

77. Delingette H. Simplex Meshes: a General Representation for 3D Shape Reconstruction. INRIA research report no. 2214. March 1994.

78. Якобовский M.B. Обработка сеточных данных на распределенных вычислительных системах. // Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2004. Вып.2. с. 4053.

79. Добеши И. Десять лекций по вейвлетам. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2004,464 стр.

80. М.Н. Gross, O.G. Staadt, and R. Gatti. Efficient triangular surface approximations using wavelets and quadtree data structures. IEEE Trans, on Visual, and Сотр. Graph., 2(2): 130-144, June 1996.

81. D.J. Hebert and H.-J. Kim. Image encoding with triangulation wavelets. Proceedings SPIE, (2569(l)):381-392,1995.

82. A. Certain, J. Popovic, Т. DeRose, Т. Duchamp, D. Salesin, and W. Stuetzle. Interactive multiresolution surface viewing. In Сотр. Graph. Proc., Annual Conf. Series (Siggraph '96), ACM Press, pages 91-98, Aug. 6-8 1996.

83. Lounsbery, M., DeRose, T.D., Warren, J. Multiresolution analysis for surfaces of arbitrary topological type. ACM Transactions on Graphics (TOG). January 1997. Volume 16, Issue 1.

84. Natarajan V., Edelsbrunner H.: Simplification of three-dimensional density maps. IEEE Transactions on Visualization and Computer Graphics 10, 5 (2004), 587-597.

85. Chiang, Y.-J., and Lu, X. Progressive simplification of tetrahedral meshes preserving all isosurface topologies. Computer Graphics Forum (Special Issue for Eurographics *03) 22, 3 (2003), 493-504.

86. Келли Дж. JI. Общая топология. М.: Наука, 1968. - 384 с.

87. Francine Evans, Steven S. Skiena, and Amitabh Varshney. Optimizing triangle strips for fast rendering. In IEEE Visualization '96. IEEE, October 1996. ISBN 0-89791-864-9.

88. W.E. Lorensen and H.E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. Computer Graphics, 21(4):163-169, July 1987.

89. Han-Wei Shen and Christopher Johnson. Sweeping simplices: A fast iso-surface extraction algorithm for unstructured grids. In IEEE Visualization '95, pages 143-150. IEEE CS Press, 1995.

90. P. Cignoni, C. Montani, E. Puppo, and R. Scopigno. Optimal isosurface extraction from irregular volume data. In Proceedings of IEEE/ACM 1996 Symposium on Volume Visualization, pp.31-38. ACM Press, October 28-29 1996.

91. В. Hendrickson, R. Leland. A Multilevel Algorithm for Partitioning Graphs. // Supercomputing '95 Proceedings. San Diego, CA, 1995.

92. G. Karypis, V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. Technical report CORR 95-035, University of Minnesota, Dept. Computer Science, Minneapolis, MN, 1995.

93. G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96-129, 1998.112. http://glaros.dtc.umn.edu/gkhome/views/metis

94. Jeong J., Hussain F, 1995, On the identification of a vortex, J. Fluid Mech., 285, 69.

95. Gushin V. A., Matyushin P. V. et al., 2003, Parallel Computing of 3D Separated Homogeneous and Stratified Fluid Flows around Bluff Bodies, Parallel Computational Fluid Dynamics, May 13-15, Abstracts, p. 100.