Разработки СО РАН - каталоги программ и БД

Поиск по каталогам:

2014-12-24

Назначение - Тест проверяет принадлежность к простым числам сверхбольших чисел Мерсенна.
 

Область применения - Теория чисел, тестирование производительности вычислительных систем.
 

Используемый алгоритм - Используется  алгоритм теста Люка-Лемера, в котором сверхбольшие числа представлены в виде динамических линейных массивов в двоичной системе счисления. Арифметические операции над числами выполняются по алгоритмам длинной арифметики. Поиск очередного самого большого простого числа   Мерсенна вида 2PM - 1 , где РM, в свою очередь, простое число, принимающее значения более 57 млн, является весьма трудоемкой задачей. В соответствии с тестом Люка-Лемера выполняется (PM -2) итераций цикла, на каждой из которых определяется целочисленный остаток от деления на число Мерсенна. Эта операция и определяет в основном трудоемкость теста. Только при представлении чисел в двоичной системе счисления представляется возможность упростить эту операцию до одной элементарной операции сложения. 

В программе реализован разработанный авторами алгоритм вычисления целочисленного остатка при делении на сверхбольшое чисто Мерсенна в двоичной системе счисления.  Целочисленный остаток в двоичной системе счисления определяется как сумма двух частей в записи делимого. Первая часть записи от разряда единиц (нулевой разряд) до разряда с номером (PM - 1), где PM - показатель степени числа Мерсенна. Вторая часть записи от разряда с номером PM и до старшего разряда в записи делимого. Использование данного алгоритма позволяет существенно снизить трудоемкость теста Люка-Лемера и время работы программы.

Алгоритм описан в статье Гончаренко В.Е. "Оптимизация вычислений целочисленного остатка в тесте Люка-Лемера для сверхбольших чисел Мерсенна" в сборнике статей Международной научно-практической конференции "Теоретические и практические вопросы науки XXI века", 2014 г., г. Уфа, Ч2.

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

Инструментальные средства создания - Microsoft  Visual Studio 2010, Visual C++.

Во Вложении прикреплен файл исходного кода программы на языке C++.

2014-12-22

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

Область применения - Программа может быть использована в  области физики, материаловедения, математики.

Используемый алгоритм:   

Теория плотных упаковок и алгоритмы построения для них описаны в [1,2,3].

1. Sloane, N. J. A. (1998). "The Sphere-Packing Problem".Documenta Mathematika 3: p. 387–396.

2. В. М. Сидельников. О плотнейшей укладке шаров на поверхности n-мерной евклидовой сферы и числе векторов двоичного кода с заданным кодовым расстоянием. Доклады АН СССР, 1973, т. 213, № 5, с. 1029–1032

3. O’Toole, P. I.; Hudson, T. S. (2011). "New High-Density Packings of Similarly Sized Binary Spheres". The Journal of Physical Chemistry C 115 (39): 19037.

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

  • Упорядоченная плотная упаковка шаров (послойная). Представляет собой заполнение большого шара слоями малых шаров. Алгоритм: построение каждого слоя начинается с края окружности каждого слоя с последующим уменьшением расстояния до центра слоя.
  • Упорядоченная плотная упаковка шаров (кубическая). Представляет собой обычную кубическую упаковку, вложенную в шар. Алгоритм: вокруг каждого шара строится строится восемь окружающих его шаров.
  • Неупорядоченная плотная упаковка шаров в сферических координатах. Представляет собой неплотную упаковку шаров, расположенных случайным образом. Алгоритм: построение нескольких шаров осуществляется случайным образом, затем построение в сферических координатах.
  • Неупорядоченная плотная упаковка шаров на основе кубической. Представляет собой неплотную упаковку шаров расположенных случайным образом. Алгоритм: построение нескольких шаров осуществляется случайным образом, затем построение по принципу кубической упаковки.
  • Неупорядоченная упаковка шаров с малой плотностью. Алгоритм: Построение шаров случайным образом. Число генерирования координат в 1000 раз превышает отношение кубов радиусов большого и малого шаров (R1)3/(R2)3 .
  • Неупорядоченная упаковка шаров со средней плотностью. Алгоритм: Построение шаров случайным образом. Число генерирования координат в 10000 раз превышает отношение кубов радиусов большого и малого шаров (R1)3/(R2)3 .
  • Неупорядоченная упаковка шаров с большой плотностью. Алгоритм: Построение шаров случайным образом. Число генерирования координат в 100000 раз превышает отношение кубов радиусов большого и малого шаров (R1)3/(R2)3 .

Функциональные возможности

   С помощью данной программы можно:

         - осуществлять различные построения плотных упаковок;

         - осуществлять обзор упаковок в режиме 3D;

         - сохранять абсолютно точное изображение упаковки.

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

         - шары пожно строить полностью или строить только их центры координат;

         - предусмотрена защита от столкновений и наложений внутренних шариков;

         - работа с объектами происходит в реальном времени;

         - автоматический расчет дисперсии для большого числа случаев;

         - удобные настройки построения объектов.         

Инструментальные средства создания - Среда программирования Delphi 7.0

2014-11-10

Назначение. Программа предназначена для уточнения формы источника цунами по двум типам измерений высоты возмущения водной поверхности океана: точечные (надводные буи DART (Deep-ocean Assessment and Reporting of Tsunamis)) и пространственные (альтиметрические спутниковые) измерения.

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

Используемый алгоритм:
В работе используется градиентный метод решения обратных задач (метод сопряженных градиентов) для волнового уравнения, основанный на решении соответствующей сопряженной задачи [1-3].

В программе есть возможности  решения задач:

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

В отличие от программ аналогичного типа данная программа позволяет:
1. Анализировать матрицы дискретных обратных задач (1), (2) и (3) с помощью метода сингулярного разложения, тем самым определять степень некорректности обратных задач;
2. Совмещать данные обратных задач ((3) = (1) + (2)) для улучшения устойчивости восстановления начального возмущения (регуляризация обратной задачи).

[1] S.I. Kabanikhin, M.A. Bektemesov, D.B. Nurseitov, O.I. Krivorotko, A.N. Alimova. An optimization method in the Dirichlet problem for the wave equation // Journal of Inverse and Ill-Posed Problems, V. 20, N. 2, 2012, pp. 193-211.
[2] S.I. Kabanikhin, A. Hasanov, I.V. Marinin, O.I. Krivorotko, D. Khidasheli. A variational approach to reconstruction of an initial tsunami source perturbation // Applied Numerical Mathematics, V. 83, 2014, pp. 22-37.
[3] S.I. Kabanikhin, O.I. Krivorotko. Optimization approach to combined inverse tsunami problem // Proceedings conference Inverse Problems – from Theory to Applications (IPTA2014), Bristol, UK, 26-28 August, 2014, pp. 102-107.

Функциональные возможности подробно описаны в Инструкции в Приложении. Рекомендуется не задавать области размером более 100х100 километров, дабы ограничить время выполнения программы до 30 минут. Для визуализации результата в качестве примера приведены исполнительные файлы отрисовки в Gnuplot.

Инструментальные средства создания: программа разработана на языке программирования Fortran 90 в среде разработки Visual Studio 2010 с использованием функций BLAS и LAPACK библиотеки Intel Math Kernel Library и открытого стандарта для распараллеливания программ OpenMP.

В приложении находятся два файла:
1. instrukciya-sovmeshchennaya_obratnaya_zadacha.pdf - описание алгоритма и программы.
2. combenditp.rar - архив, содержащий 5 файлов:

Interface_CombinedITP.exe - исполняющий файл-форма, генерирующая входные параметры и вызывающая расчетный модуль.

OMITP.exe - расчетный математический модуль. Запускается автоматически файлом Interface_CombinedITP.exe.

Model_Bath.dat - тестовый файл, описывающий входную функцию дна (двумерный массив).

Plot2D.plt - исполняющий файл, позволяющий отрисовывать в формате *.eps выходные одномерные файлы как двумерные графики.

Plot3D_result.plt - исполняющий файл, позволяющий отрисовывать в формате *.eps входные и выходные двумерные файлы как трехмерные графики.

2014-09-16

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

Программа является модификацией программы "Приближенное вычисление несвязности планарного графа с высоконадежными ребрами" http://fap.sbras.ru/node/4086. В её основе лежат аналогичные асимптотические отношения, параметры которых определяются с помощью разработанного алгоритма построения двойственного графа (файл Инструкция №2 в Приложении).  Однако наравне с существенным сокращением числа арифметических операций, данная модификация позволяет обрабатывать сети с различными весами на ребрах, что значительно расширяет класс рассматриваемых соединений и область применения программы.

[1] G.Sh. Tsitsiashvili, A.S. Losev, M.A. Osipova.  Disconnection probability of planar weighted graph // Applied Mathematical Sciences, Vol. 8, 2014, no. 10, 469-472 

В отличие от программ аналогичного типа данная программа позволяет:
1. Работать с графом произвольного вида;
2. Использовать новые, модифицированные алгоритмы, уменьшая вычислительную сложность;
3. Не требовать высоких технических характеристик к используемым аппаратным средствам.

Функциональные ограничения - в силу используемых формул вероятность отказа ребра должна быть меньше чем 0,01.
Исходя из удобства, не рекомендуется использовать программу для графов с количеством вершин более 100.

Программа разработана на Object Pascal  в среде разработки Delphi 7.

2014-06-26

Назначение: Библиотека LIAC (Light Interaction with Anisotropic Crystals) предназначена для расчёта фотореалистических изображений прозрачных и полупрозрачных (цветных прозрачных) изотропных, одноосных и двуосных монокристаллов и кристаллических агрегатов с помощью алгоритмов лучевой трассировки. Данная библиотека является первой библиотекой, позволяющей рассчитывать фотореалистические изображения двуосных кристаллов и одноосных кристаллических агрегатов.

Библиотека реализует расчёт взаимодействия луча света с изотропными и анизотропными прозрачными и полупрозрачными монокристаллами и кристаллическими агрегатами.

Библиотека позволяет рассчитывать следующие оптические эффекты:

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

Область применения: Компьютерная графика. Фотореалистический рендеринг (расчёт изображений близких к фотографии) монокристаллов и кристаллических агрегатов.

Используемый алгоритм: 

Для расчёта отражённых и преломлённых лучей, возникающих при падении луча на границу сред в кристаллах используется модель, разработанная автором на основе ковариантного метода, предложенного в [1] и получившего распространение в кристаллооптике, и методах, применяемых в компьютерной графике для физически корректного расчёта распространения луча света в сцене. Для представления поляризации луча света применяются матрицы когерентности. Для расчёта поглощения луча используется модель Бугера-Ламберта-Бера, а коэффициент поглощения для заданного луча света, с заданным состоянием поляризации и направлением распространения, вычисляется на основе модели из [2]. Разработанные автором модели и алгоритмы описаны в работах [3], [4], [5].

[1] Фёдоров, Ф.И. Отражение и преломление света прозрачными кристаллами / Ф.И. Фёдоров, В.В. Филиппов. – Минск: Наука и техника. – 1976.

[2] Борн, М. Основы Оптики. / М. Борн, Э. Вольф. – М.: Наука. – 1973.

[3] Дебелов, В.А. Локальная модель взаимодействия света с изотропными и одноосными прозрачными средами / В.А. Дебелов, Д.С. Козлов // Вестник НГУ: Информационные Технологии. – 2012. – Т. 10. – № 1. ­– С. 5–23.

[4] Debelov, V. A. A Local Model of Light Interaction with Transparent Crystalline Media / V.A. Debelov, D.S. Kozlov // IEEE Transactions on Visualization and Computer Graphics. – 2013. – Vol. 19. – No. 8. – P. 1274–1287.

[5] Дебелов, В.А. Алгоритм фотореалистического рендеринга окрашенных полупрозрачных кристаллов / В.А. Дебелов, Д.С. Козлов // Информационные технологии в проектировании и производстве. – 2014. – № 2. – С. 25–30.

Функциональные возможности:

Используемые объекты:

Описание луча: точка начала, вектор направления распространения, матрица когерентности и система координат, связанная с лучом, в которой задана матрица когерентности.

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

Описание полупрозрачной среды: описание прозрачной среды и главные спектры поглощения (один спектр для изотропной среды, два спектра для одноосной, три спектра для двуосной).

Описание геометрии границы: нормаль к границе в точке падения луча.

Основные функции:

1.       Расчёт всех отражённых и преломлённых лучей, возникающих при падении луча на границу двух изотропных, одноосных или двуосных сред (в любой комбинации), т.е. расчёт взаимодействия луча света с внешними и внутренними границами сред в монокристаллах и кристаллических агрегатах, см. CLIACInterface::interactWithRay.

2.       Расчёт поглощения луча света при прохождении им заданного расстояния в изотропной, одноосной или двуосной среде, т.е. расчёт изменения луча при прохождении им расстояния между границами сред в кристаллах, см. ILIACMedium::passThroughMedium.

Ограничения функциональности:

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

Для описания спектров и работы с ними используется разработанная автором библиотека CIE, идущая в комплекте с библиотекой LIAC.

Инструментальные средства создания: Microsoft Visual Studio 2013, язык программирования C++.

Описание файлов:

1.    LIAC_Library.zip – содержит следующие папки:

a.    Help – справочные файлы по API библиотек LIAC и CIE.

b.    Include – заголовочные файлы библиотек LIAC и CIE.

c.     Lib – библиотечные модули, собранные компилятором Visual C++ версии 18 (Visual Studio 2013).

d.    Samples – примеры использования библиотеки:

      Пример 1.     InterfaceInteraction – расчёт отражённых и преломлённых лучей на границах: вакуум (изотропная среда) – стекло (изотропная среда), вакуум – кальцит (одноосная среда), вакуум – оксалат аммония (двуосная среда), кальцит – оксалат аммония, оксалат аммония – оксалат аммония (с различной ориентацией кристаллической решётки).

      Пример 2.     ConicalRefraction – расчёт изображения внутренней конической рефракции на монокристалле оксалата аммония.

      Пример 3.     CrystalRendering – расчёт изображения трёхмерной сцены содержащей одноосный монокристалл.

Изображения, рассчитанные с помощью библиотеки:

1. Двойное кольцо внутренней конической рефракции на монокристалле оксалата аммония (результат работы Примера 2):

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

Результаты тестирования библиотеки доступны: http://oapmg.sscc.ru/temp_crystal_tests/