Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Блочный метод гауса.

Автор: Nookie 28.10.2007, 15:48

Это не обычный мтод гауса, а блочный, когда рассмариваются элементы не как числа а как матрици заданного размера. прикрепил файл, там мой отчет. Этот метод должен давать выйгриш в скорости в 6-7 раз по сравнению с обычным метдом гауса. Я написал на С++, решает, но вот толго, для больших размеров вйгрыш всего на 5 секунд... может кто подскажет как улучшить?

Автор: Akina 28.10.2007, 15:55

Это ж как надо собою гордиться, чтобы ТАКОЕ количество ошибок наляпать?

Автор: marcusmae 28.10.2007, 16:04

Nookie,  1) раз у Вас блочный метод Гаусса (кажется, ещё и с выбором ведущего элемента), то нужно искать обратные матрицы к тем блокам, на которые Вы делите большую матрицу. Как Вы ищите обратные матрицы? 2)  Цитата(Nookie @  28.10.2007,  15:48 ) Этот метод должен давать выйгриш в скорости в 6-7 раз по сравнению с обычным метдом гауса. что-то сомневаюсь. А откуда ввобще такие числа и почему нет зависимости от размерности матрицы? В любом случае, надо программу смотреть, а то так непонятно, что улучшать.

Автор: Nookie 28.10.2007, 17:50

Я могу скинуть программу, но будет ли там что понятно для вас. Он должен работать быстрее... Обратную матрицу я ищу по методу: не помню как он называет, но делаю так.. записываю две матрици подряд, первую привожу к единичной, а вторая тоже изменияется.. справа получается обратная матрица, по мойму метод лапласса, точно это метод Гаусса... (как-то криво написал) Насчет выйгрыша времени, нам это наш препод рассазал, думаю верить ему можно...  Я протестировал программу, обратную матрицу он ищет не так долго... там мелочи, подсчитал все время, которое он считает обратные матрицы, просуммировал... получилось всего 0,5-1 секунда, с матрицей 2000*2000 и размером блока на 50*50. Больше всего занимает времени это умножение и отнятие строк.... самое интересное, ребята делают программы, которые рещают матрице 2000*2000 за 6 секунд, а у меня за 38 секунд..................... А насчет ошибок думаю это не важно.

Автор: marcusmae 28.10.2007, 18:21

Цитата(Nookie @  28.10.2007,  17:50 ) Обратную матрицу я ищу по методу: Ага, прямым методом, значит. Хорошо. Цитата(Nookie @  28.10.2007,  17:50 ) Насчет выйгрыша времени, нам это наш препод рассазал, думаю верить ему можно...  Лучше, конечно, иметь дело с книжками и оценками на число умножений, зависящими от размеров матрицы. Скажем, обычный метод Гаусса - порядка n^3 / 3 (это очень много). Цитата(Nookie @  28.10.2007,  17:50 ) самое интересное, ребята делают программы, которые рещают матрице 2000*2000 за 6 секунд, а у меня за 38 секунд Я решал за это время слау с размерностями в пару десятков тысяч. Естественно, не методом Гаусса, и не очень плотные матрицы (много нулей). Цитата(Nookie @  28.10.2007,  17:50 ) Я могу скинуть программу, но будет ли там что понятно для вас. Ну хоть бы какие-нибудь детали показали бы. У Вас там, должно быть, какой-то формат есть? Вряд ли хороша идея иметь один большой двумерный массив для матрицы и постоянно считать отступы для добора до нужных блоков. Наверно, вы храните двумерный массив блоков или что-то такое? Цитата(Nookie @  28.10.2007,  17:50 ) Больше всего занимает времени это умножение и отнятие строк.... Вычитание делаете в позиции или кладёте результат на новое место? И вообще, все эти операции собственного производства или какой-то готовый BLAS используете?

Автор: Nookie 29.10.2007, 01:18

Попытаюсь на все ответить. Масив такой Код double *Matr; Matr=(double*)malloc(Size*Size*sizeof(double)); например, размер блока SizeBlock, чтобы обратиться к i, j блоку делаю так Код Matr[(i * SizeBlock + k) + j * SizeBlcok + l] В результате перехожу в i, j блок и в этом блоке в k, l элемент этого блока... вычитая сразу кладу в матрицу, то есть посчитал элемент умноженияи в том же цикле положил результат. Препод сам написал книжки, Богачев К.Ю., называется решение линейных систем, но там про блочный метод ничего не написано, там рассказывается обычные методы. вот. если вам надо, миогу эту книгу дать в электронном виде. Он же у нас ведет практикум по ЭВМ. Если хотите, могу скинуть программу, только на мыло. Не хочу в общак. Спасибо. Добавлено через 2 минуты и 28 секунд >вычитая сразу кладу в матрицу, то есть посчитал элемент умноженияи в том же цикле положил результат. результат разности.... в смысле отнял

Автор: marcusmae 29.10.2007, 23:42

Цитата(Nookie @  29.10.2007,  01:18 ) например, размер блока SizeBlock, чтобы обратиться к i, j блоку делаю таккод Код Matr[(i * SizeBlock + k) + j * SizeBlcok + l] В результате перехожу в i, j блок и в этом блоке в k, l элемент этого блока... Хм, ну вот, я бы воздержался от расчёта означенного выражения для каждого элемента блока - целых два умножения. Предлагаю хранить так : 1) двумерный массив указателей на блоки 2) каждый блок = массив элементов блока Плюс один момент : когда вам нужно перейти к следующему элементу строки или столбца, берите не индексы, а инкрементируйте указатель на текущий элемент на единицу, или, соответственно, на длину строки (сумма дешевле умножений). Я бы организовал вычитание как-то так : Код // A1 = A1 - A2. inline double* inposMatSubstract(const int m, const int n, double* matrix1, const double* matrix2) { double* currMatrix1 = matrix1; double* currMatrix2 = matrix2; for (int elemIndex = 0; elemIndex < m * n; elemIndex++) {     *currMatrix1 -= *currMatrix2;     currMatrix1++; currMatrix2++; } return matrix1; } А можно на Ваше посмотреть?

Автор: Nookie 30.10.2007, 19:10

Схожу завтра на пару, спрошу у препода, потом напишу в чем все таки дело....

Автор: Nookie 15.11.2007, 14:10

Короче я сдал эту задачу, сЩитает очень хорошо, за 6.80 секунд... просто надо было оптимизировать и кое-что поправит. Спасибо за помощь. Если надо могу кому-нибудь скинут программу.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)