Обратная матрица, параллельное программирование

[Rekky]

Добрый день
Получили задание на КП (тема). Сейчас пытаюсь написать пункт
"Получение обратной матрицы распараллеливанием"
Должен содержать что- то вроде зачем и в каких сферах применяется, почему именно распараллеливанием, какие общие методы..недостатки, плюсы..
Может быть у кого есть какая литература? а то у меня даже сложности с тем, чтобы найти зачем нужна обратная матрица.,кроме одной фразы: для решения уравнений

[Вадим Мошев]

Литература какого профиля интересует вас? Программировании или математика (алгебра матриц?) Думаю, что у меня есть то, что вам может пригодиться/помочь

Я вас поправлю, она нужна не для решения уравнений, а их систем, более точно - СЛАУ (системы линейных алгебраических уравнений).

Метод с применением обратной матрицы называется матричным.
Коротко говоря, если у вас есть система вида
A*X = B,
Где A - матрица коэффциентов,
x - Матрица-стобец неизвестных
B - матрица-столбец свободных членов, то решение X может быть найдено таким образом:

X = B*A[-1]
Здесь A[-1] - обратная матрица к матрице коэффициентов

[Rekky]

Так вот например я нашла по теме

1. Существует гипотеза Штрассена, согласно которой: для сколь угодно малого ε > 0 существует алгоритм, при достаточно больших натуральных n, гарантирующий перемножение двух матриц размера nn за O(n ε + 2) операций. Исходя из данной гипотезы, предположим, что для оптимизации нахождения обратной матрицы необходимо задачу обращения свести к задаче умножения. В таком случае, станет возможным применение алгоритма Штрассена, сложность которого составляет: Ө(n log27) = Ө(n 2.81) , что дает заметный выигрыш на больших плотных матрицах, начиная, примерно, от 6464. В [1] приводится описание сведения обращения матрицы к операции умножения, фактически представляющий из себя LUP-разложение с дальнейшим преобразованием и перемножением полученных матриц. Реализовать алгоритм можно с помощью рекурсии [2].
2. Метод Гаусса-Жордано. Параллельная версия данного метода основывается на декомпозиции матрицы на несколько частей, независимая обработка каждой по соответствующим формулам и объединение в единый результат, который и будет являться обратной матрицей [3].
3. Алгоритм Block Tridiagonal Matrix Inversion основан на построении Tridiagonal matrix и дальнейшей ее обработке, которая представляет собой декомпозицию полученной матрицы на блоки и их параллельная обработка

Мне нужно определить какой метод лучше..я так поняла что Штрассена, тк матрицы у меня будут огромных размеров, если это так, то мне нужен пример нахождения обратной матрицы таким методом (прям по шагам с примерной небольшой матрицей)..и реализация в // программировании..А если не штрассена, то тогда интересует литература по другим методам, желательно на русском и с примерами решения..

Программировании или математика (алгебра матриц?)

Касательно этого вопроса, то сначала в КП мне нужно описать словесно алгоритм обычный и для параллельного программирования, а потом и текст программы с MPI
Вот содержание так сказать

2.2 Алгоритм 8
2.2.1 Последовательный алгоритм: 8
2.3 Параллельная модификация алгоритма 11
2.3.1 Выделение информационных зависимостей 12
2.3.2 Масштабирование и распределение подзадач по процессорам 12
2.3.3 Анализ эффективности 13
4.2 Управление коммуникационной средой MPI 36
4.2.1 Коммуникационное программное обеспечение для мультикомпьютеров 35
4.2.2 Сравнение возможностей PVM и MPI. 36
4.2.3 Описание MPI 39
5 Программа решения

[Вадим Мошев]

Ну вот пока что могу предложить.
По программированию там нет ничего, но есть литература, посвящённая матрицам, а также математические методы...

Может как-то поможет...
Потом ещё у себя посмотрю...

http://www.programmersclub.ru/литера...трица-паралле/

[Вадим Мошев]

Ну, как, полезные книги?
кстати, вот ещё одна, но уже по программированию на языке Object pascal (Delphi), если вы в нём разбираетесь, конечно...

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

http://www.programmersclub.ru/литера...трица-паралле/

[Rekky]

К сожалению, ничего не подошло...касательно параллельного программирования, и по методу Штрассена ничего тоже не нашла..Я думаю, во втором архиве тоже код не для // программирования?! посмотрю чуть позже...
Последовательный то я и сама напишу...как найти обратную матрицу известным мне способом..а вот для // что- то совсем трудно найти

[Rekky]

Товарищи, может кто знает...неужели вот ЭТО:
image079.gif
Гораздо лучше для параллельного программирования и производительности, нежели если найти обратную матрицу через транспонированную матрицу? неужели такая огромная разница будет во времени?
Размер матрицы более 10000

[Вадим Мошев]

Сообщение от Rekky

Товарищи, может кто знает...неужели вот ЭТО:
Вложение 39355
Гораздо лучше для параллельного программирования и производительности, нежели если найти обратную матрицу через транспонированную матрицу? неужели такая огромная разница будет во времени?
Размер матрицы более 10000

Я честно скажу, ничего не знаю про параллельное программирование, метод Штрассена, но скажу вот что.
Разница может, конечно, быть, но если вы будете искать обратную матрицу через транспонированную, то, с учётом того, размер исходной более 10000 эл-тов, вам большое количество (более 100) определителей большого порядка (поскольку используемая в этой формуле матрица в качестве элементов содержит алгебраические дополнения исходной матрицы).

Однако, если вы под "размером" матрицы понимаете её порядок, то минимальный размер такой матрицы будет 10000x10000, то есть 100000000 (сто миллионов элементов).

Для вычисления обратной матрицы через транспонированную, вам придётся считать сто миллионов определителей 9999-го порядка...

Скажется на производительности, мне кажется...

Поправка: считать будете не вы, а ПК.

[Rekky]

Поправка: считать будете не вы, а ПК.

:D Как знать..мб скучно совсем в декрете станет
ладно шутки шутками..но скорее всего вы правы..ладно надо попробовать ручками порешать этого Штрассена..авось, что и пойму)
по формулам так сложно что-то решать..вот если бы им в помощь примеры были..тык вот не найду никак

Как вы думаете, что такое детерминант в минус первой степени..это определитель обратной матрицы (из формулы выше)? но мы же ее и вычисляем, те. он нам не известен, или же это определитель одной из подматриц...мб A11 ^-1

[Вадим Мошев]

Как вы думаете, что такое детерминант в минус первой степени..это определитель обратной матрицы (из формулы выше)? но мы же ее и вычисляем, те. он нам не известен, или же это определитель одной из подматриц...мб A11 ^-1

Детерминант (он же определитель) - это обычное число. А число возведённое в степень (-1), как вы знаете, вычисляется как 1/число, то есть

x^(-1) = 1/x

Отсюда следует, что для x = 0 это действие неопределено, и это не удивительно, ведь для матрицы с детерминантом, равным нулю, обратной матрицы не существует...