WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«КАФЕДРА САПР (РК6) МГТУ ИМ. Н.Э. БАУМАНА Желдаков А.В. Научный руководитель: к.т.н., доцент Федорук В.Г. Задачи дипломного проекта 1.Реализация и исследование модифицированного ...»

Параллельные методы решения

больших систем ЛАУ

КАФЕДРА САПР (РК6) МГТУ ИМ. Н.Э. БАУМАНА

Желдаков А.В .

Научный руководитель: к.т.н., доцент

Федорук В.Г .

Задачи дипломного проекта

1.Реализация и исследование модифицированного алгоритма

Гаусса для решения СЛАУ с ленточной матрицей коэффициентов .

2.Реализация метода Монте-Карло в ПО OpenFOAM .

3.Исследование эффективности метода Монте-Карло .

4.Сравнительный анализ алгоритмов на задаче гидродинамики .

ПОСТАНОВКА ЗАДАЧИ

Задача нахождения решения СЛАУ может быть представлена в виде

КОРРЕКТНОСТЬ ПОСТАНОВКИ ЗАДАЧИ И ПОНЯТИЕ ОБУСЛОВЛЕННОСТИ

Задача поставлена корректно, если решение существует, единственно и если оно непрерывно зависит от входных данных .

Критерий существования и единственности решения СЛАУ det() 0 Мера обусловленности матрицы = 1 Зависимость относительной погрешности решения от погрешности матрицы A от погрешности правых частей

ПОСТАНОВКА ЗАДАЧИ

Задача нахождения решения СЛАУ может быть представлена в виде

ОСНОВНЫЕ ПОНЯТИЯ

1. Размер строки матрицы n .

2. Смещение

3. Количество ненулевых диагоналей N .

4. Вектора Красная диагональ соответствует d1 .

5. Время выполнения операции деления дел .

6. Время выполнения прочих арифметических операций арф .



7. Время передачи единицы данных по коммуникационной сети СРП пд .

8. Число узлов вычислительной системы системы p .

МОДИФИЦИРОВАННЫЙ МЕТОД ГАУССА РЕШЕНИЯ СЛАУ

С ЛЕНТОЧНОЙ МАТРИЦЕЙ КОЭФФИЦИЕНТОВ

ТРАНСФОРМАЦИЯ ИСХОДНОЙ ЗАДАЧИ

Исходная задача Расширим вектор x, добавив в его начало S переменных, а также введём в систему S дополнительных уравнений:

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

Для матрицы A` дополнительно введем вектора. Каждый из этих векторов имеет размерность L и содержит отличные от 0 элементы строки матрицы A` с номером .

ПРЯМОЙ ХОД АЛГОРИТМА

Вычтем первые S уравнений из последних S уравнений по следующему правилу – из уравнения с номером вычитается уравнение с номером .

Далее итерационно вычисляем компоненты векторов c` по формулам После выполнения итераций в правом нижнем углу матрицы коэффициентов образуется подматрица Q размерности SxS. Для последних S уравнений задачи выполним прямой ход алгоритма Гаусса без изменения .

СХЕМА МЕТОДА ДЛЯ СИСТЕМЫ ТИПА МУЛЬТИПРОЦЕССОР

1. Процессор Q1 назначается главным (master-процессор) все остальные вспомогательные (slave-процессоры). На master-процессоре запускаем основной процесс алгоритма .

2. Запускаем p потоков управления, каждому из которых предадим на обработку z= векторов .

При обработке данных участвуют как master-процессор, так и slave-процессоры .

3. Каждый поток управления производит модификацию своей части векторов .

4. На master-процессоре выполним прямой ход стандартного алгоритма Гаусса для последних S уравнений модифицированной задачи .



6. На master-процессоре выполняем обратный ход алгоритма Гаусса и завершаем работу программы .

АНАЛИТИЧЕСКАЯ ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА

–  –  –

Достоинства алгоритма .

-Простота программной реализации .

-Экономия памяти вычислительной системы по сравнению с методом Гаусса .

-Возможность простой адаптации под различные вычислительные системы с общей памятью .

-Отсутствие множественного доступа по записи к исходным данным .

Недостатки алгоритма .

-Падение ускорения с ростом смещения .

-Необходимость выделения дополнительной памяти на этапе модификации исходной задачи .

-Метод не использует при прямом ходе выбор ведущего элемента .

ОПИСАНИЕ МЕТОДА МОНТЕ-КАРЛО

Метод Монте-Карло – стохастический численный метод

Особенности:

• Использует Марковские процессы .

• Позволяет найти решение отдельного корня, не решая СЛАУ целиком .

• Обладает естественным параллелизмом .

• Сложность O(n) .

Ограничения:

• Матрица А коэффициентов СЛАУ должна обладать строгим диагональным преобладанием .

СХЕМА МЕТОДА МОНТЕ-КАРЛО

–  –  –

1. Случайные числа (природный процесс)

2. Псевдослучайные числа (ГСЧ: линейный конгруэнтный алгоритм, вихрь Мерсена, …)

3. Квазислучайные числа (последовательности Соболя, Холтона …)

–  –  –

Достоинства алгоритма .

- Вычислительная сложность порядка O(n) .

- Обладает естественным параллелизмом .

- Единственный известный алгоритм, позволяющий найти значение одной компоненты вектора неизвестных x не вычисляя остальных .

–  –  –

Зависимость времени решения от размерности СЛАУ .

Метод Монте-Карло (МК), метод бисопряженных градиентов (БСГ) и модифицированный метод Гаусса (ММГ) .

ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ЧАСТЬ

–  –  –

1.Исследован предложенный модифицированный алгоритм Гаусса для решения СЛАУ с ленточной матрицей коэффициентов .

2.Исследована возможность реализации метода Монте-Карло для решения СЛАУ большой размерности .

3.Реализован метода Монте-Карло для OpenFOAM .

4.Проведен сравнительный анализ исследуемых алгоритмов .






Похожие работы:

«Министерство образования и науки РФ Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Казанский (Приволжский) Федеральный университет" ИНСТИТУТ ФИЗИКИ КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ И МОДЕЛИРОВАНИЯ ФИЗИЧЕСКИХ ПРОЦЕССОВ Специальность: 050203.65 Физика с дополнительн...»

«УДК 004.48, 004.45 АВТОМАТИЗИРОВАННАЯ СИСТЕМА КОНТРОЛЯ И ДИАГНОСТИКИ НЕИСПРАВНОСТЕЙ ЦИФРОВЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Г.А . Смельчакова, А.С. Пентин, Е.А. Солодянкина АО "НПО автоматики", Россия (620075, Россия, г. Екатеринбург, ул. Мамина-Сибиряка, 145), e-mail: gasmelchakova@gmail.com Аннотация: В статье рассматривается подход, применяемый в...»

«Реферат Пояснительная записка содержит листов, рисунок, источников, 1 приложение. ГОЛОСОВАЯ БИОМЕТРИЯ, РАСПОЗНАВАНИЕ ДИКТОРА, ИДЕНТИФИКАЦИЯ ПО ГОЛОСУ, МЕЛ-ЧАСТОТНЫЕ КЕПСТРАЛЬНЫЕ КОЭФФИЦИЕНТЫ, ВЕКТОРНОЕ КВАНТОВАНИЕ. Объектом исследования явл...»

«Федеральное архивное агентство (Росархив) Федеральное бюджетное учреждение Всероссийский научно-исследовательский институт документоведения и архивного дела (ВНИИДАД) СРАВНИТЕЛЬНЫЙ АНАЛИЗ ПРОГРАММНЫХ ПРОДУКТОВ, ПРЕДНАЗНАЧЕННЫХ ДЛЯ ИНФОРМАТИЗАЦИИ ВНУТРИАРХИВНОЙ ДЕЯТЕЛЬ...»

«36 Прикладная дискретная математика. Приложение В этих же обозначениях можно сформулировать следующий известный факт: пусть F квадратичная APN-функция от n переменных, n нечётно. Тогда для любого v Fn, v = 0, мно...»

«X-CORE ® Контролер для полива приусадебных участков RUN SENSOR BYPASS SYSTEM OFF CURRENT TIME/DAY ACTIVE MANUAL-ONE STATION START TIMES RUN TIMES SEASONAL ADJUSTMENT WATER DAYS Руководство пользователя и инструкции по программированию Совместим с пультами дистанционного упр...»

«Гусев Антон Георгиевич Оптимизационные и теоретико-игровые модели рынка электроэнергии о 1.01.09 дискретная математика и математическая кибернетика Автореферат диссертации на соискание ученой степени кандидата физико-математических наук 1О ^ Москва-2012 Работа выполнена на кафед...»

«ГЕОФИЗИЧЕСКИЕ ИССЛЕДОВАНИЯ, 2009, том 10, № 2, с.56-68 УДК 556.33:550.348 ОЦЕНКА ИНФОРМАТИВНОСТИ УРОВНЕМЕРНЫХ НАБЛЮДЕНИЙ В СКВАЖИНАХ ДЛЯ ПОИСКА ГИДРОГЕОДИНАМИЧЕСКИХ ПРЕДВЕСТНИКОВ ЗЕМЛЕТРЯСЕНИЙ (НА ПРИМЕРЕ КАМЧАТКИ) 2009 г....»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

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