Библиографическое описание:

Яворук С. О. Программная реализация метода оценки погрешностей результатов картирования в рамках сплайн-аппроксимационного подхода // Молодой ученый. — 2015. — №11. — С. 204-207.

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

Ключевые слова: сплайн-аппроксимация, картирование, карты дисперсий, вычислительный эксперимент.

 

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

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

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

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

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

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

Наиболее перспективными [3] в рамках данного подхода представляются полиномиальные сплайны, ввиду некоторых особенностей:

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

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

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

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

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

Алгоритм построения карт дисперсий для локальных уравнений можно представить в виде следующего набора последовательных шагов:

1.                   Определение точек, на которые локальные уравнения оказывают влияние.

2.                   Вычисление элементов вектора, который будет использован в роли правой части при решении системы уравнений.

3.                   Решение системы уравнений, для которой в роли левой части выступают данные, использованные для построения исследуемой карты, а в роли правой части — полученный ранее вектор.

4.                   На основе решения системы уравнений вычисляются значения элементов матрицы ковариации.

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

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

Алгоритм построения карт дисперсий для глобальных уравнений может иметь следующий вид:

1.                   Вычисление элементов вектора, который будет использован в роли правой части при решении системы уравнений.

2.                   Решение системы уравнений, для которой в роли левой части выступают данные, использованные для построения исследуемой карты, а в роли правой части полученный ранее вектор.

3.                   На основе решения системы уравнений вычисляются значения в узлах равномерной прямоугольной сетки описывающей дисперсий исследуемой карты.

Приведенные выше алгоритмы были реализованы в рамках вычислительного модуля для программного продукта GST [4]. В качестве языка программирования был выбран С++ по причине его высокой вычислительной производительности и наличия библиотек позволяющих эффективно решать возникающие подзадачи. В качестве дополнительной библиотеки была использована Intel Math Kernel Library — математическая библиотека, включающая в себя оптимизированные многопоточные реализации математических функций [5].

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

-                    Автоматическое распределение памяти между потоками.

-                    Отсутствие необходимости отдельно поддерживать последовательную и параллельную версии программы.

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

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

-                    Процессор: Intel Core i5–3570K (4 ядра по 3.4 GHz)

-                    RAM: 8GB

-                    Операционная система: Windows 7

-                    Библиотеки: Intel MKL 10.2.4.032

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

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

Таблица 1

Результаты замера времени выполнения расчётов

1 поток

2 потока

4 потока

Размер сетки

время

время

ускорение

время

ускорение

30x35

1.12

0.63

1.78

0.41

2.73

60x70

14.2

8.6

1.65

6.3

2.25

100x120

115

73

1.58

52

2.21

120x140

251

162

1.55

118

2.13

140x170

596

391

1.52

278

2.14

170x190

1116

711

1.57

506

2.21

240x280

5023

3253

1.54

2176

2.31

290x340

6953

4537

1.53

2918

2.38

 

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

Результаты замера времени выполнения расчетов по программе представлены в таблицах 2–4. Время указано в секундах. Ускорение указано относительно последовательной реализации.

Таблица 2

Размер сетки: 60x60

1 поток

2 потока

4 потока

Количество замеров

время

время

ускорение

время

ускорение

500

14.4

7.5

1.92

4.1

3.51

1000

28.7

14.8

1.94

8

3.59

2000

56.7

29.1

1.95

15.8

3.59

4000

113

58

1.95

31.3

3.61

 

Таблица 3

Размер сетки: 120x120

1 поток

2 потока

4 потока

Количество замеров

время

время

ускорение

время

ускорение

500

61.7

32.6

1.89

17.8

3.47

1000

121.3

63.6

1.91

33.9

3.58

2000

241

125.4

1.92

66.2

3.64

4000

481

249

1.93

131

3.67

 

Таблица 4

Размер сетки: 240x240

1 поток

2 потока

4 потока

Количество замеров

время

время

ускорение

время

ускорение

500

263.5

148.3

1.78

82

3.21

1000

500

275

1.82

154

3.25

2000

998

527

1.89

291

3.43

4000

1964

1043

1.88

547

3.59

 

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

 

Литература:

 

1.      Волков Е. А. Численные методы. — 2-е изд., испр. — М.: Наука. Гл. ред. физ.-мат. лит., 1987. — 248 с.

2.      Плавник А. Г. Картирование свойств геологических объектов на основе сплайн-аппроксимационного подхода: Дисс... доктора технических наук. — Новосибирск, 2013. — 248 с.

3.      Завьялов, Ю. С. Методы сплайн-функций / Ю. С. Завьялов, Б. И. Квасов, В. Л. Мирошниченко. — М.: Наука, 1980. — С. 352.

4.      Сайт программного продукта GST. URL: http://geo-spline.ru (дата обращения: 15.05.2015).

5.      Документация Intel Math Kernel Library. URL: https://software.intel.com/ru-ru/intel-software-technical-documentation (дата обращения: 15.05.2015).

Обсуждение

Социальные комментарии Cackle