Лабораторная работа 5 (Определитель матрицы и простые числа Мерсенна (Захаров))

Посмотреть архив целиком

Национальный Исследовательский Университет

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

Институт автоматики и вычислительной техники

Кафедра прикладной математики

Лабораторная работа № 5

Программирование на языке FPTL

Курс «Параллельные системы и параллельные вычисления»




Выполнил

студент 5 курса группы А-13-08

Захаров Антон

Преподаватель

Шамаль Павел Николаевич


Постановки задач

1. Пусть дана квадратная матрица размерности . Требуется реализовать алгоритм нахождения определителя. Матрицу представлять в виде списка списков.


2. Нахождение простых чисел Мерсе́нна (вида ).


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



Тестирование проводилось на компьютере со следующей конфигурацией:

ПРОЦЕССОР Intel Core i5 2500MHz Ivy Bridge

ОПЕРАТИВНАЯ ПАМЯТЬ 16Gb DDR3 1600MHz

ФИЗИЧЕСКИЙ НАКОПИТЕЛЬ OCZ-VERTEX3 (120Gb, SATA600, SSD)

ГРАФИЧЕСКИЙ ПРОЦЕССОР AMD Radeon HD 7700 (1Gb DDR5 4.6GHz)

ОПЕРАЦИОННАЯ СИСТЕМА Windows 7 Ultimate x64 (SP1)



Задача 1

Разложение по строке (сложность )

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

Для матрицы первого порядка детерминантом является сам единственный элемент этой матрицы:

Для матрицы детерминант определяется как:

Для матрицы определитель задаётся рекурсивно:

где — дополнительный минор к элементу . Эта формула называется разложением по строке.

В частности, формула вычисления определителя матрицы такова:

Для решения данной задачи на языке FPTL был определён вспомогательный тип List, значениями которого могут быть пустой список (c_nil) или элемент любого типа и список List из элементов этого типа. Для удобства работы со списком были написаны рекурсивные функции removeFromList и listGet, осуществляющие удаление и получение элементов списка с заданным индексом.

Чтение матрицы из файла осуществляется набором рекурсивных функций:
readNumb, считывающей число из файла, используя регулярное выражение,
readLine, считывающей строку в список элементов, readElems и readMatrix.

Для облечения работы с матрицей (списком списков) также была реализована рекурсивная функция get для получения элемента матрицы с заданным индексом.

Результаты вычислительного эксперимента

Матрица 10 х 10


Число
потоков

Время решения (сек)

Время
решения1
(сек)

Ускорение

1

2

3

4

5

1

52,373

52,860

52,514

52,653

52,979

52,676

1,000

2

38,168

38,249

38,042

37,834

37,955

38,050

1,384

3

32,085

31,763

31,584

31,215

31,062

31,542

1,670

4

29,718

29,854

29,716

29,765

29,810

29,773

1,769

5

35,885

39,602

38,685

37,520

39,301

38,199

1,379

6

40,587

40,602

39,227

39,111

41,202

40,146

1,312

7

39,988

40,420

39,351

39,256

40,056

39,814

1,323

8

41,771

42,413

42,171

41,614

42,069

42,008

1,254

9

51,488

51,168

52,249

51,042

51,834

51,556

1,022

10

67,732

67,085

67,763

65,584

66,215

66,876

0,788

11

71,582

74,718

70,854

68,716

69,765

71,127

0,741

12

85,287

81,614

92,988

104,420

89,351

90,732

0,581








Время

(сек)

Зависимость времени решения задачи от числа потоков

Число

потоков





Ускорение

Зависимость ускорения параллельного решения от числа потоков

Число

потоков



Data List['t]

{

List = c_nil ++ 't * List['t].c_cons;

}


// Вычисление определителя матрицы из файла

// in [1] - путь к файлу с матрицей

Scheme Determinant

{

@ = [1].readMatrix.det.print;

// Вычисление определителя матрицы

// in [1] - матрица

// in [2] - размерность матрицы

det = (id * 1).det1;

// in [3] - индекс текущего столбца

// out [1] - определитель матрицы

det1 = ([2] * 1).equal -> [1].~c_cons.[1].~c_cons.[1],

([2] * [3]).equal -> id.det1i,

(id.det1i * ([1] * [2] * [3].inc).det1).add;

det1i = ([3].inc.sign * ([1] * 1 * [3]).get * id.minor).mul3;

// Вычисление дополнительного минора к заданному элементу 1-ой строки матрицы

// in [1] - матрица

// in [2] - размерность матрицы

// in [3] - индекс столбца элемента

// out [1] - дополнительный минор

minor = (([1] * [2] * 1 * [3]).submatr * [2].dec).det;

// Получение подматрицы

// in [1] - матрица

// in [2] - размерность матрицы

// in [3] - номер удаляемой строки

// in [4] - номер удаляемого столбца

submatr = (id * 1).submatr1;

// in [5] - номер текущей строки

// out [1] - подматрица

submatr1 = ([5] * [2]).greater -> c_nil,

([5] * [3]).equal ->

([1].~c_cons.[2] * [2] * [3] * [4] * [5].inc).submatr1,

(([1].~c_cons.[1] * [2] * [4] * 1).removeFromList *

([1].~c_cons.[2] * [2] * [3] * [4] * [5].inc).submatr1).c_cons;


// --- Вспомогательные функции ---

// Удаление элемента из списка

// in [1] - список

// in [2] - количество элементов списка

// in [3] - индекс удаляемого элемента списка

// in [4] - индекс текущего элемента

// out [1] - новый список

removeFromList = ([4] * [2]).greater -> c_nil,

([4] * [3]).equal ->

([1].~c_cons.[2] * [2] * [3] * [4].inc).removeFromList,

([1].~c_cons.[1] * ([1].~c_cons.[2] * [2] * [3] *

[4].inc).removeFromList).c_cons;

// Считывание матрицы и её размерности из файла

// in [1] - файловая переменная

// out [1] - матрица

// out [2] - размерность матрицы

readMatrix = [1].readFile.readNumb.(([2] * [1]).readElems * [1]);

// Считывание матрицы из файла

// in [1] - строка

// in [2] - количество элементов в строке

// out [1] - матрица

readElems = ([1] * "").equal -> c_nil,

(([1] * [2] * 0).readLine * [2]).([1] * ([2] * [3]).readElems).c_cons;

// Чтение строки в список элементов

// in [1] - строка

// in [2] - размерность матрицы

// in [3] - индекс текущего столбца

// out [1] - прочитанный список

// out [2] - оставшаяся часть строки

readLine = ([2] * [3]).equal -> c_nil * [1],

(([1].readNumb * [2] * [3]).([1] * ([2] * [3] *

[4].inc).readLine)).(([1] * [2]).c_cons * [3]);

// Считывание числа из файла

// in [1] - строка матрицы

// out [1] - первое число, находящееся в строке

// out [2] - оставшаяся часть строки

readNumb = ([1] * "-?\\d+").getToken.([1].toInt * [2]);

// Получение элемента матрицы

// in [1] - матрица

// in [2] - индекс строки

// in [3] - индекс столбца

// out [1] - элемент матрицы

get = (([1] * [2]).listGet * [3]).listGet;

// Получение элемента списка

// in [1] - список

// in [2] - индекс элемента списка

listGet = ([1] * [2] * 1).listGet1;

// in [3] - индекс текущего элемента списка

// out [1] - элемент списка

listGet1 = ([2] * [3]).equal -> [1].~c_cons.[1],

([1].~c_cons.[2] * [2] * [3].inc).listGet1;

// Умножение [1]x[2]x[3]

mul3 = ([1] * ([2] * [3]).mul).mul;

// Возвращает 1, если [1] - чётное, иначе возвращает -1

sign = (([1] * 2).mod * 0).equal -> 1, -1;

// Инкремент

inc = ([1] * 1).add;

// Декремент

dec = ([1] * 1).sub;

}


Application

% Determinant("G10.txt")





Задача 2

Числа Мерсенна – числа вида , где – натуральное число.

Последовательность чисел Мерсенна начинается так:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, …

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


Случайные файлы

Файл
65606.rtf
42469.rtf
74719-1.rtf
158834.rtf
160651.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.