Разреженные матрицы и оптимизация их решения

Форум для обсуждения вопросов математики

Модератор: Admin

Isaev
Сообщения: 10
Зарегистрирован: Пн окт 01, 2007 10:57 pm
Контактная информация:

Разреженные матрицы и оптимизация их решения

Сообщение Isaev » Вт сен 06, 2016 3:42 pm

Доброго времени суток!

Имеются большие матрицы, разреженные (меньше 1% не нулевых элементов), с главной диагональю, симметричные, содержат только 0 и 1, все очень похожие, изображения примеров:
http://imgur.com/a/rYjIq

Это маленькие, будут до 150000 порядка, похожие на ленточные, но есть мусор вокруг. Не знаю есть ли смысл (и возможно ли) их к ленточным привести и есть другие методы для данной проблемы? Как лучше хранить, есть ли смысл в переобуславливателе в данном случае, есть ли смысл в LU разложении и каким методом оптимальнее будет в данном случае решать?

Мне нужно алгоритм придумать для программки для их быстрого решения. Пока реализовал решения СЛАУ методом Гаусса, оптимизировал под 64бит с учётом булевых переменных (хранение в виде бит для более быстрых операций умножения и сложения). В результате получилось 50.041 x 50.041, имеющая 0.73% не нулевых элементов, решается примерно 10 мин, что не правильно и ясно что нужно менять логику, а не оптимизировать дальше. Подсказали про разреженные матрицы и данная тема для моего случая очень даже подходит, только не могу определиться какой именно алгоритм для моей задачи наиболее подходит, чтобы не пробовать всё подряд.

Гаусса я дооптимизировал до 7500х7500 за секунду (именно для булевых), потом он начинает хромать и довольно быстро умирает, (10к х 10к примерно 5сек, 17к х 17к около 20 и т.д., а на 50к х 50к уже до 10мин доходит) ну он и предназначен для не больших матриц в принципе, этого стоило ожидать.
В одном месте меня направили в сторону GMRES, но он довольно общий, не учитывающим плюс симметрии и для плавающей арифметики… Но его можно распараллелить.

Всё работает в рамках булевой алгебры!
Интересен алгоритм, реализую сам.

PS про предобуславливатели много читал, но так и не понял как применять и нужны ли они в моём случае?

Markiyan Hirnyk
Сообщения: 1221
Зарегистрирован: Вс дек 04, 2011 11:07 pm

Re: Разреженные матрицы и оптимизация их решения

Сообщение Markiyan Hirnyk » Вт сен 06, 2016 5:10 pm

Задайте ваш вопрос здесь http://dxdy.ru/okolonauchnyj-soft-f39.html, там весьма квалифицированные участники. Насколько я в курсе, Мэйпл имеет мощные средства для работы с разреженными матрицами, но я не специалист в этих вопросах.

Isaev
Сообщения: 10
Зарегистрирован: Пн окт 01, 2007 10:57 pm
Контактная информация:

Re: Разреженные матрицы и оптимизация их решения

Сообщение Isaev » Вт сен 06, 2016 6:18 pm

Markiyan Hirnyk писал(а):Источник цитаты Задайте ваш вопрос здесь

Да, я там видел обсуждения по теме, участники "весьма квалифицированные", согласен. Вопрос там задавал, но как-то те, кто хотелось бы, чтобы ответил, его обошли вниманием...
Мне больше не софт интересен, а внутренности, т.к. мне интереснее понять принцып, а не пользоваться сторонними средствами... Ну разве что, чтобы видеть по скорости на что ориентироваться.