Проект по Системи за Паралелна Обработка Паралелен Алгоритъм за пресмятане на Детерминанта на матрица
Изтегляне 24.8 Kb.
|
| Проект
по Системи за Паралелна Обработка Паралелен Алгоритъм за пресмятане на Детерминанта на матрица Изготвил: Бойко Караджов Ръководител: ас. Христо Христов Проверил: ........................ (ас. Христо Христов) АБСТРАКТНО Матриците се използват постоянно в моделирането на много различни типове данни като графи, игри и невронни мрежи. Детерминантата на една матрица дава много информация за данните в нея (примерно ако е равна на 0 знаем, че векторите, от които е съставена са линейно зависими). Затова пресмятането на детерминанта на матрица е нещо, което се налага често в най-различни математически проблеми. Пресмятането на детерминанта обемна операция и изисква много изчисления. Съвременните изчислителни системи работят паралелно и се нуждаем от подходящ алгоритъм за да използваме наличните ресурси.
Алгоритъмът, който ще предложа използва адюнгирани количества. За матрица N x N трябва да изчисли детерминантите на N на брой матрици (N – 1) x (N – 1): 
Като за матрица 2x2 вече използва директна формула: 
По този начин за последователно изчисление сложността на алгоритъма е o(n!). Всяко адюнгирано количество може да бъде изчислено независимо от останалите, което дава възможност за очевидна паралелизация. Синхронизация е необходима само на края когато трябва получените резултати от адюнгираните количества да се редуцират в едно число – детерминантата. Алгоритъмът е следния:
Синхронизация се прави само в края, което прави алгоритъмът много чист. Проблеми са, че отделните задачи са много големи и някои нишки може да изостанат повече от другите, при което може някои изчислителни ядра да останат в режим на изчакване. Освен това когато броят на нишките не е кратен на броя на колоните на матрицата в края работят само нишки равни на остатъка при делението на брой колони на матрицата / броя на нишките. Идея: по-добър подход би бил да се работи по формулата на Лабниц като се генерират пермутации на елементите на матрицата и така всяка пермутация може да се изчисли независимо, изчисленията ще са разделени на много повече на брой много по-малки части.
Разработено е проложение на Java по горе описания алгоритъм. За експеримента ще се изчислява детерминанта на матрица с размерност 11 х 11. Спрямо броя нишки ще видим времето необходимо за изчисление (T) и следните два индикатора: S(t) = T(1) / T(t) E(t) = S(t) / t , където t е брой нишки.   Каталог: docs -> example.projects -> not.so.bad docs -> Опит в група чрез психодрама, социометрия и групова терапия docs -> Дв бр. 103 от 2 Декември 2008г., изм дв бр. 24 от 31 Март 2009г docs -> Фондация «Гъривер клиринг хауз» (c/o Център за култура и дебат „Червената къща”) docs -> Иван (Ванчо) Флоров и м а г и н е р н о с т а docs -> Соу „СВ. Св. Кирил и методий docs -> Рискови фактори на тютюнопушенето not.so.bad -> Проект по Системи за Паралелна Обработка Паралелен Алгоритъм за example.projects -> Задача: Генериране на страници на книга Изготвил : Александър Боянов Тодоров, фак.№: 80435, 3 курс, Компютърни науки Изтегляне 24.8 Kb. Сподели с приятели:
|