![]() |
|
![]() ![]() ![]() |
|
k0c9k |
|
|||
Новичок Профиль Группа: Участник Сообщений: 36 Регистрация: 24.12.2006 Репутация: нет Всего: нет |
Товарищи ! нужно реализовать параллельный алгоритм нахождения обратной амтрицы методом Гаусса. Не поделитесь соображениями ? Просто не могу сообразить как его вообще можно распараллелить… Но можно: надыбал какой-то исходник решения СЛАУ методом Гаусса (сам разобраться в нем как-то немогу =( )
Помогите плиз ! |
|||
|
||||
SoWa |
|
|||
![]() Харекришна ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
И ты хочешь, чтобы твой код разобрали? Нет. Лучше сам напиши. Не сложно ведь?
Что касается алгоритма. Что значит параллельный? -------------------- Всем добра ![]() |
|||
|
||||
k0c9k |
|
|||
Новичок Профиль Группа: Участник Сообщений: 36 Регистрация: 24.12.2006 Репутация: нет Всего: нет |
Не сложно. Почти написал. Такая шиза получилась. Кому интересно - могу выложить.
Параллельный в смысле, что в несколько процессов выполняется. Реализован с помощью MPI Как доделаю расскажу свои домыслы. Это сообщение отредактировал(а) k0c9k - 25.12.2006, 10:04 |
|||
|
||||
V.A.KeRneL |
|
|||
![]() Vadim A. Kazantsev ![]() ![]() Профиль Группа: Участник Сообщений: 291 Регистрация: 3.12.2006 Где: Moscow, Russia Репутация: 1 Всего: 14 |
Вообще, имхо, надо по дефолту выкладывать... Наверняка кому-нибудь в будущем пригодится! И не надо будет заново всё с нуля писать, а можно будет просто ссылочку сюда дать. А те, кто умеют пользоваться поиском по форуму, вообще новую тему создавать не станут!.. Так что, выкладывай, конечно! Это сообщение отредактировал(а) V_A_KeRneL - 25.12.2006, 10:47 -------------------- «C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы» ---/)/)---(\.../)---(\(\ --(':'=)---(=';'=)---(=':') (")(")..)-(").--.(")-(..(")(") |
|||
|
||||
SoWa |
|
|||
![]() Харекришна ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
Нет. Выкладывать не стоит. Кому надо- сами напишут.
Или если уж совсем невтерпеж похвастаться- подредактируй свой первый пост и в нем выложи -------------------- Всем добра ![]() |
|||
|
||||
k0c9k |
|
|||
Новичок Профиль Группа: Участник Сообщений: 36 Регистрация: 24.12.2006 Репутация: нет Всего: нет |
Пока исходник не отлажен расскажу что я сам надумал.
Напомню, метод Гаусса нахождения обратной матрицы заключается в приписании к правой части единичной матрицы такой-же размерности. И с помощью перестановок сведением левой матрицы к единичной. Таким образом в правой части получается обратная. Сам процесс вычисления состоит в последовательном делении i-ой строки на элемент a[i,i] (имеется ввиду что на этом этапе все элементы a[i,k], k<i уже равны нулю). Элемент a[i,i] станет равным 1. после этого можно нужно будет из всех строк вычесть i-ю строку домноженную на a[k,i],k!=i. таким образом мы сводим левую (исходную) матрицу к единичной, а в правой части появится обратная. Теперь как я всё это дело решил запараллелить: В принципе, если у нас матрица больших размеров, самой трудоёмкой частью будет вычитание текущей строки из остальных строк. Поэтому решил что у всех процессов будет храниться своя часть матрицы. После того как диспетчерский процесс считает саму матрицу он поледовательно будет выдавать всем процессам по строке. В итоге получаем что у каждого процесса будет в среднем (размерность/кол-во потоков). Теперь диспетчерский процесс посылает остальным сообщение о том, что i-строка делится на a[i,i]. Тот процесс который понял что i-строка принадлежит ему производит деление строки, после чего отсылает её остальным процессам. Процессы вычитают из своих строк полученную. Цикл повторяется. По окончании цикла, все процессы отсылают диспетчерскому строки правой части. Это сообщение отредактировал(а) k0c9k - 26.12.2006, 07:34 |
|||
|
||||
Silver |
|
|||
![]() Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 1.9.2005 Репутация: 1 Всего: 1 |
||||
|
||||
k0c9k |
|
|||
Новичок Профиль Группа: Участник Сообщений: 36 Регистрация: 24.12.2006 Репутация: нет Всего: нет |
Спасибо за хелп который здесь появился
![]() Программную реализацию выкладывать не буду, ИМХО нечитабельные исходники выкладывать бесполезно. Так что если комуто ОЧЕНЬ понадобится: стучите в ПМ. |
|||
|
||||
DENNN |
|
|||
Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 3878 Регистрация: 27.3.2002 Где: Москва Репутация: 1 Всего: 43 |
И в чем смысл? Параллельность - это когда несколько действий выполняются одновременно. А здесь одновременность только в вычитании, а потом все процессы опять ждут когда один из них поделит строку на число и разошлеть остальным. Кроме того, у меня большие сомнения, что при продуманной организации данных вычитание скажем N строк N процессами будет заметно бытсрее, чем последовательная обработка этих строк одним процессом. Вариант с многопроцессорным кластром не берем ... ![]() |
|||
|
||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
честно говоря, я вижу здесь одну вещь, котогрую можно распараллелить - вычитание одной строки из другой (ну и деление тогда же), каждая компонента векторов обрабатывается независимо, так что можно без проблем поручить это дело разным процессам
но с другой стороны, ещё неизвестно какие накладные расходы вызовет такое мелкое деление... -------------------- qqq |
|||
|
||||
k0c9k |
|
|||
Новичок Профиль Группа: Участник Сообщений: 36 Регистрация: 24.12.2006 Репутация: нет Всего: нет |
Да. у меня тоже была мысль ещё деление распределить, но из-за такой мелочи как-то не намного скорость я думаю увеличится.
Да вообще лучше для подсчета обратной матрицы в несколько процессов использовать рекурсивный алгоритм (с кватернарными деревьями)! Вот он параллелится замечательно! А гаусс - так, по приколу ![]() Это сообщение отредактировал(а) k0c9k - 28.12.2006, 13:29 |
|||
|
||||
DENNN |
|
|||
Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 3878 Регистрация: 27.3.2002 Где: Москва Репутация: 1 Всего: 43 |
Угу. Мое скромное ИМХО, паралелльность нужна для независимых процессов/потоков. Когда получится сформулировать алгоритм Гаусса как набор нескольки независимых процессов, то решение о реализации будет очевидным ))
|
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |