5 / 5 / 1
Регистрация: 02.07.2012
Сообщений: 45
|
||||||
1 | ||||||
Оптимизация алгоритма вычисления определителя матрицы29.01.2013, 15:39. Показов 20579. Ответов 27
Метки нет (Все метки)
Здравствуйте!
Написал я давеча программку, которая считает определитель. Только вот беда - он не считает определители матриц выше 10 порядка - тупо не хватает памяти. Я так понимаю, это из-за того, что мой алгоритм - рекурсивный. Так вот, можно ли больше оптимизировать мой код, или эта рекурсия - заведомо плохой вариант?
0
|
29.01.2013, 15:39 | |
Ответы с готовыми решениями:
27
Улучшение алгоритма вычисления определителя матрицы, порядка n>3 Код вычисления определителя матрицы до 10-го порядка Рекурсивный метод вычисления определителя матрицы Написать функцию для вычисления определителя матрицы |
57 / 18 / 1
Регистрация: 14.05.2012
Сообщений: 134
|
|
29.01.2013, 17:16 | 2 |
Lexp, ну сама по себе рекурсия есть не очень хорошо в плане скорости. Странно что не хватает памяти(а как вы поняли что ее не хватает?) ведь у компьютера сейчас например 2гб оперативной памяти + подкачка. Короче много. Плюс ко всему сам по себе ваш алгоритм поиск миноров( разложение Лапласа кажется правильно ) ну ооочень медленный. Работает аж за O(n!). Например у вас 10!=3628800. Может и можно как то оптимизировать,если хорошо проанализировать код(убрать какие нибудь ненужные действия,или как нибудь их объединить),но высокого прироста к производительности вы не получите
0
|
Заблокирован
|
|
29.01.2013, 17:30 | 3 |
Lexp, посмотри 4.4.3 Матричный способ нахождения определителя
2
|
5 / 5 / 1
Регистрация: 02.07.2012
Сообщений: 45
|
|
29.01.2013, 18:24 [ТС] | 5 |
Да, сложность кошмарная, тут согласен. Видимо придется действительно Гаусса использовать, как-то сразу не додумался...
0
|
|
29.01.2013, 18:34
#6
|
Не по теме: - ели считать по свойству определителя то Гассу нет! Гаусс может лишь рассматриваться как оптимизация да и то не из лучших, те кто пишут им определители просто идут по пути наименьшего сопротивления. Причём всегда надо пробовать идти по нелёгкому пути, чтобы потом сравнить с лёгким и выбрать лучшее для той или иной СЛАУ.
0
|
5 / 5 / 1
Регистрация: 02.07.2012
Сообщений: 45
|
|
29.01.2013, 18:40 [ТС] | 7 |
Самый нелегкий путь тут - нахождение определителя прямо по определению (сумма всевозможных комбинаций того-то и того-то). Там и сложность по идее меньше будет, только вот как реализовать...
0
|
Заблокирован
|
||||||
29.01.2013, 18:50 | 8 | |||||
- ну так по линку в посте выше так его и нахожу
Добавлено через 1 минуту Причем ниже в 5.2 уже вообще сингл функция детерминанта идёт Кликните здесь для просмотра всего текста
0
|
5 / 5 / 1
Регистрация: 02.07.2012
Сообщений: 45
|
|
29.01.2013, 19:06 [ТС] | 9 |
Не-не-не, я имею в виду не рекурсивное разложение по строке, а именно сумма всех комбинаций элементов, взятых по одному из каждого столбца и каждой строки.
0
|
57 / 18 / 1
Регистрация: 14.05.2012
Сообщений: 134
|
|
29.01.2013, 19:25 | 10 |
Lexp, считая определитель как говорится "в лоб", или раскладывая по строкам - ты получишь одну и ту же сложность - O(n!)
Метод Гауса дает более лучший результат - O(n3) Так что используй метод Гауса. Быстрее ну точно не придумаешь. p.s. Есть алгоритмы,которые работают быстрее, но они быстрее лишь на ОООООЧЕЕЕНЬ больших матрицах
0
|
74 / 37 / 3
Регистрация: 23.09.2012
Сообщений: 408
|
|
29.01.2013, 19:30 | 11 |
Можно программно посчитать какие на какие элементы нужно перемножить (в индексах), что бы получить определитель и сохранить в файлик. А потом из файлика считать и в цикле посчитать. Чем не вариант?
0
|
5 / 5 / 1
Регистрация: 02.07.2012
Сообщений: 45
|
|
29.01.2013, 19:34 [ТС] | 12 |
Да, я тоже подумал, кол-во слагаемых будет как раз n!
Наверно тупо сделаю Гаусса и сравню с текущим алгоритмом. Добавлено через 2 минуты Вот это "программно посчитать" как раз в n! и выйдет...если я правильно вашу идею понял
0
|
74 / 37 / 3
Регистрация: 23.09.2012
Сообщений: 408
|
|
29.01.2013, 19:36 | 13 |
Lexp, для матрицы 2x2 это было бы:
00 01 10 11 00 * 11 - 01 * 10 в индексах. Ну или еще можно попробовать упростить матрицу до того, что бы большинство оказалось нулями
0
|
57 / 18 / 1
Регистрация: 14.05.2012
Сообщений: 134
|
|
29.01.2013, 19:38 | 14 |
Kgfq, это и есть определение определителя. Математики уже соптимизировали и доказали все что можно) Метод Гауса-самый быстрый и вменяемый метод(вплане алгоритма).
С другой стороны,как вариант, можно распараллелить данную программу-но это уже не оптимизация алгоритма,а оптимизация программы. Добавлено через 1 минуту Lexp, Гаусом не тупо, Гаусом правильно) Ты на верном пути! И поверь быстрее ты не придумаешь)))
1
|
5 / 5 / 1
Регистрация: 02.07.2012
Сообщений: 45
|
|
29.01.2013, 19:38 [ТС] | 15 |
1
|
Заблокирован
|
|
29.01.2013, 22:27 | 16 |
- ты уверен(а) в своих словах, проверька Гасса на разрежённой матрице 4000х4000 порядка, посомтришь что быстрей "матрица" или Гаусс, преращающий в кучу числе почти занулённую матрицу!
А вот всякие шапкозакидатели вроди тебя сбивают люд с пути истинного! Детерминант в FAQ я дал, ниже там идёт и метод Гаусса. Аргументируй вот это своё выссказывание . А я говрю Гауссом иногда тупее чем определителем, и?! Не по теме: PS:Если кто-то не в силах что-то написать - это не значит что это "что-то" глупость либо нерационально ИМХО!
0
|
74 / 37 / 3
Регистрация: 23.09.2012
Сообщений: 408
|
|
29.01.2013, 22:33 | 17 |
Не по теме: -=ЮрА=-, вы так брызгаете слюной, что текст сложно читать. Нельзя ли писать спокойней, рассудительней и главное - понятней. А по теме, если автор напишет Гауссом, то можно будет сравнить методы, которыми вы пользуетесь
0
|
Заблокирован
|
|
29.01.2013, 22:36 | 18 |
А для "Фом неверующих" на словах: если взять матрицу в которой ненулевых элементов кот наплакал, то можно подобрать такую строку в которой 1 элемент и все остальные - нули. И что получаем - найти детерминант на порядок ниже надо, всего один, причем если стопорить расчёт детерминанта как только в сомножителе ноль, то можно получить КОЛОСАЛЬНЕЙШИЙ выиграш в производительности и скорости. А вот Гаусс добросовестно будет
2 х (4000 * 4000) раз ворочать матрицу состоящую скажем из 80% нулей, нет слов эффективно до боли....
0
|
74 / 37 / 3
Регистрация: 23.09.2012
Сообщений: 408
|
|
29.01.2013, 22:39 | 19 |
-=ЮрА=-, вы рассматриваете крайности. Это уже вопрос динамического расчета и применения наиболее эффективного в данный момент. Но, т.к. вероятность выпадения 0 в матрице бесконечно мала (по сравнению с R), то метод Гаусса более оптимальный
0
|
|
29.01.2013, 22:46
Оптимизация алгоритма вычисления определителя матрицы
#20
|
Не по теме: - дружок поищи матрицу соединения узлов энергосистемы да рассчитай там ток и напряжение в каждом элементе при К(1,1) в оной из ветвей, а потом сравни с матричным способом...Вероятность нуля мала))) ну да в СЛАУ для студентов она и правда мала, а в реалии всё совсем совсем по другому. В реалии во многих сферах рулят крайне разрежённые СЛАУ. На сим не хочу продолжать не нужный мне спор или переубеждение. Я могу, верней я писал и "детерминант по определению" и метод Гаусса и знаю что где применимо и какая у чего производительность в близи краевых условий...
0
|
29.01.2013, 22:46 | |
Создать функцию для вычисления определителя матрицы 2х2 Подстроение алгоритма определителя Оптимизация алгоритма вычисления Алгоритм вычисления определителя квадратной матрицы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |