• Регистрация
gry_n_go
gry_n_go+1.26
н/д
  • Написать
  • Подписаться

GPU поддерживает одержимых фракталами (перевод статьи Клива Молера)

Перевод работы, демонстрирующей построение и изображения фракталов. Конкретно - множества Мандельброта. Использование GPU существенно ускоряет такие упражнения.

GPU поддерживает одержимых фракталами

Клив Молер, MathWorks (перевод Г.Байдин)

 

 

Я фанат фракталов. И теперь у меня есть графический процессор, который помогает мне фанатеть. Графические процессоры были первоначально предназначены для ускорения графики, но MatLab® использует их для ускорения вычислений. Фракталы1 - это графика, требующая обширных вычислений. Идеальные кандидаты для GPU.

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

Мой графический процессор - это NVIDIA ® Titan V, размещенный в отдельном корпусе для периферийных устройств, который больше, чем ноутбук, и обеспечивает раздельное питание и охлаждение. Он примерно в 300 раз быстрее процессора для вычисления этих фракталов и полностью меняет то, как я взаимодействую с моей mandelbrot программой. В своей программе я применяю gpuArray, это даёт возможность довести разрешение расчетной сетки до сопоставимого с разрешением моего экрана и уточнять решение до тех пор, пока мелкие детали изображения не станут видны.

 

 

Визуализация множества Мандельброта

Первое опубликованное изображение множества Мандельброта было напечатано на строчном принтере в 1978 году Робертом Бруксом и Питером Мательском.

Изображение множества Мандельброта на строчном принтере.

Первое цветное изображение появилось на обложке журнала Scientific American в 1985 году. Это было примерно в то время, когда компьютерные графические дисплеи стали широко доступны.

Цветное изображение множства Мандельброта.

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

 

 

Внутри множества Мандельброта

То, что происходит в Мандельброте, остается у Мандельброта. Метод построения множества Мандельброта представляет собой простую итерацию с комплексными числами, начиная с начальной точки z1 = 0. Множество Мандельброта - это область на комплексной плоскости, состоящая из значений z0, для которых орбиты генерируемых точек, определяемые итерацией

zk+1=zk2+z0, k=1,2,...

остаются ограниченными. Вот и все. Это полное определение. Удивительно, что такое простое определение может создать такую завораживающую сложность.

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

 

 

Рисунок 1 представляет собой набросок геометрии множества Мандельброта. Самый большой компонент - кардиоида в форме сердца, ограниченная кривой с параметрическим уравнением

z = eit /2 − e2it /4, −π ≤ t ≤ π

Рис. 1. Набросок геометрии множества Мандельброта.

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

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

 

 

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

 

 

Вычисление Мандельброта

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

Вот функция, которая составляет основу вычислений. Входными данными является комплексная скалярная начальная точка z0 и действительный скалярный параметр, который я называю depth. На выходе получаем значение счетчика kz. Если итерация прервана из-за того, что z находится за пределами круга радиуса два, значит z было суждено стать бесконечным, и счетчик kz можно использовать как индекс в цветовой карте. С другой стороны, если z "остается живой" на протяжении depth итераций, то она объявляется входящей в множество Мандельброта.

function kz = mandelbrot (z0, depth)

  z = z0;

  kz = 0;

  while (z * conj (z) <= 4) & (kz <= depth)

        kz = kz + 1;

        z = z * z + z0;

  end

end


(прим. переводчика: приведенная функция не является классическим определением множества Мандельброта, в котором постоянное слагаемое z0 и стартовое значение z могут быть разными; см. википедию)

 

Давайте создадим сетку точек на комплексной плоскости, покрывающую квадрат шириной w с центром в комплексной точке zc.

grid = 512;

s = w*(-1:1/grid:1);

[u,v] = meshgrid(s+real(zc),s+imag(zc));

 

Теперь мы подходим к единственному месту в программе, где есть отличие версии, работающей на CPU, от версии, которая работает на GPU. Cгенерируем сетку на ЦП:

z0 = u + i*v;

 

Для GPU это будет выглядеть так:

z0 = gpuArray(u + i*v);

 

Теперь уже для любого процессора инструкция:

kz = arrayfun(@mandelbrot,z0);

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

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

 

 

На периферии

Область, известная как Долина Морских Коньков, находится между центральной кардиоидой и диском слева от нее. На самом деле есть две долины: одна выше и одна ниже реальной оси. И встречаются они в красной точке, которую мы видели на рисунке 1. Проявив немного воображения, вы можете представить себе маленьких морских существ, живущих на рисунке 2. Как мы увидим позже, в Долине также есть и скрытое π.

Рисунок 2. Долина морских коньков.

Поскольку множество Мандельброта самоподобно, оно содержит бесконечное количество миниатюрных Мандельбротов, каждое из которых имеет ту же форму, что и большое. Тот, что показан на Рисунке 3, имеет коэффициент увеличения 1010 .

Рисунок 3. Миниатюрный Мандельброт.

 

 

Скрытое π

Замечательный результат был обнаружен в 1991 году Дэйвом Боллом, тогда аспирантом Государственного университета Колорадо. Болл исследовал поведение итерации Мандельброта в Долине Морских Коньков. Долины сужаются по мере приближения к оси, которую они встречаются в точке (-3/4, 0), красной точке на рисунке 1.

Мы можем повторить вычисление Болла на небольшой сетке с центром рядом с осью в точке -3/4 + yi для крошечного значения y и мнимой единицы i .

y = 1.0e-07

zc = -3/4 + y*i

Сделайте сетку достаточно большой, чтобы она касалась оси.

width = 2*y

grid = 4

 

Выберите величину depth обратно пропорционально y, что сделает её огромной.

depth = 4/y

 

С этими параметрами запустите приведенный выше код. Он выдаст:

kz =

40000000 40000000 40000000 40000000 40000000

40000000 40000000 40000000 40000000 40000000

40000000 40000000 31415926 40000000 40000000

40000000 40000000 20943951 40000000 40000000

40000000 40000000 15707963 40000000 40000000

 

Посмотрите на количество итераций в центре сетки. Увидели знакомое значение?

Это не случайность. В статье 2001 года Аарона Клебаноффа «π в множестве Мандельброта» анализируются аналогичные вычисления на острие передней части кардиоиды.

Далее любопытный вариант итерации Мандельброта.

 

Пылающий корабль

Пылающий корабль произошел из странной итерации:

zk+1 = F(zk) + z0, k = 1, 2, . . .

где

F(z) = (|Re(z)|+ i|Im(z)|) 2

Я говорю это странно, потому что функция F(z) не аналитическая. Меня заинтересовала эта итерация из-за сверхъестественного сходства на следующих изображениях.

Начальная область, показанная на рисунке 4, представляет собой квадрат шириной 3,5 с центром в -0,5 -0,5 i . Я добавил стрелку, как указатель на интересующую область следом за кораблем.

Рисунок 4. Горящий корабль, начальный домен.

Увеличьте кильватерный след от корабля в 500 раз до точки -1,861-0,002 i . Примените bone палитру, чтобы рисунок казался холодным, а не теплым. На рис. 5 показан полученный фрактал рядом с фотографией 1915 года корабля «Эндьюранс» исследователя Антарктики Эрнеста Шеклтона, захваченного льдами в море Уэдделла.

Рис. 5. Слева: увеличенный вид следа от Пылающего Корабля. Справа: фотография корабля Шеклтона, вмерзшего во лёд в Антарктиде, сделанная Херли в 1915 году. Фото: Национальная библиотека Австралии, https://nla.gov.au/nla.obj-158931586/view.

 

 

Башня из возведения в степень

Начните с любого комплексного числа z и многократно возводите его в степень.

z, z^z, (z^z)^z, . . .

Мы можем выразить это как итерацию. Начнем с y0= 1 и далее

yk+1 = (z) yk

Если z слишком велико, эта итерация уйдет в бесконечность. Для некоторых же z, она будет сходиться к конечному пределу. Например, если z = sqrt(2), то yk сходится к 2. Самый интересный случай, когда yk зацикливается. Например, если z взять близким к 2.5+4i, то цикл будет иметь длину 7.

2.4684 + 4.0754i

-0.6216 + 0.3634i

0.2603 - 0.0184i

1.4868 + 0.3613i

-3.4877 + 6.1054i

7.7632e-06 - 2.6617e-06i

1.0000 + 0.0000i

2.4684 + 4.0755i

 

Эта длина цикла является основой фрактала «башни возведения в степень». На рисунке 6 показан общий фрактал.

Рис. 6. Фрактал Башни возведения в степень.

 

Увеличение в 105 раз и изменение цветовой карты дает изображение, показанное на рисунке 7.

Рис. 7. Деталь фрактала башни возведения в степень.

 

 

Метод Ньютона

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

Итерация знакома. Выберите функцию f(z) с производной f′( z). Начните с z0 и выполняйте итерации

zк+1 = zk- f(zk) /f′(zk)

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

Есть много функций (и цветовых карт) на выбор. Мой любимый - кубический многочлен:

f(z) = z3 – 2z– 5

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

Рис. 8. Итерация Ньютона по z3 - 2z - 5.

 

На рисунке 9 показано глобальное поведение метода Ньютона, ищущего нули функции:

f(z) = tan(sin(z))− sin(tan(z))

Такая функция имеет бесконечно много нулей и неограниченную первую производную.

Рисунок 9. Деталь из итерации Ньютона по tan (sin (z)) - sin (tan (z)).

 

Функция на рисунке 10: f(z) = z sin( 1 / z)

Наиболее заметные синие области окружают нули на уровне ± 1 / π.

Рисунок 10. Деталь из итерации Ньютона по z sin (1 / z).

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

1 Термин фрактал был введен Бенуа Мандельбротом (1924–2010), польским / французским / американским математиком, который большую часть своей карьеры провел в Исследовательском центре IBM Watson в Йорктаун-Хайтс, штат Нью-Йорк.

Опубликовано 2019

 

Ссылки

Аарон Клебанофф, «π в множестве Мандельброта», Фракталы, World Scientific Publishing Company, т. 9, 2001.

Фрэнк Херли, 1915, Долгая-долгая ночь [Эндюранс в зимней антарктической темноте, заточенный в море Уэдделла, экспедиция Шеклтона, 27 августа 1915 года] , Национальная библиотека Австралии.

Файлы

  • GPU Enables Obsession with Fractals - MATLAB & Simulink rus.pdf

Теги

    08.09.2020

    Комментарии

    • hex oct bin
      hex oct bin +17.80
      9.09.2020 02:58

      Что-то халтурой попахивает =D

      • gry_n_go
        gry_n_go+1.26
        9.09.2020 03:26

        Что именно? Перевод или сама статья? Если перевод - готов доработать