2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Разреженные матрицы и оптимизация их решения
Сообщение22.07.2016, 19:35 
Аватара пользователя


20/07/16
14
Germany
Доброго времени суток!

Имеются большие матрицы, разреженные (меньше 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, но он довольно общий, не учитывающим плюс симметрии и для плавающей арифметики… Но его можно распараллелить.

Всё работает в рамках булевой алгебры!
Не советуйте готовые библиотеки или продукты, мне интересна сама теория и алгоритм

 Профиль  
                  
 
 Re: Разреженные матрицы и оптимизация их решения
Сообщение22.07.2016, 20:08 
Заслуженный участник


15/05/05
3445
USA
На эту тему есть достаточно много литературы. Например:

- Р. Тьюарсон. Разреженные матрицы. 1977
- А.Джордж, Дж.Лю. Численное решение больших разреженных систем уравнений. 1984
- О. Эстербю, З.Златев. Прямые методы для разреженных матриц. 1987
- Серджио Писсанецки. Технология разреженных матриц. 1988

- Duff I.S., Erisman A.M., Reid J.K. Direct Methods for Sparse Matrices. 1989
- Yousef Saad. Iterative Methods For Sparse Linear Systems. 2003
- Timothy A. Davis. Direct Methods for Sparse Linear Systems. 2006

 Профиль  
                  
 
 Re: Разреженные матрицы и оптимизация их решения
Сообщение23.07.2016, 01:54 
Аватара пользователя


20/07/16
14
Germany
Да, с пятью из них я уже поверхностно ознакомился и запутался в разнообразии методов. Потому в общем и задал вопрос тут.
Конкретно на мои вопросы, заданные выше я не нашёл ответа. Тут мало голой теории, хотелось бы услышать совет людей, которые занимались данной темой на практике

 Профиль  
                  
 
 Re: Разреженные матрицы и оптимизация их решения
Сообщение01.08.2016, 11:30 
Аватара пользователя


20/07/16
14
Germany
По теме предобуславливатели может кто-нибудь привести конкретный пример в котором они помогают привести матрицу к более быстрому решению?
Я пока не понял смысла их предназначения... Или они в моём случае мало пригодны?

 Профиль  
                  
 
 Re: Разреженные матрицы и оптимизация их решения
Сообщение08.09.2016, 16:39 
Аватара пользователя


20/07/16
14
Germany
Просто на листочке нарисуйте, если не сложно... мне б принцып понять

 Профиль  
                  
 
 Re: Разреженные матрицы и оптимизация их решения
Сообщение10.09.2016, 09:20 
Супермодератор
Аватара пользователя


20/11/12
5728
 !  Isaev, замечание за подъём темы бессодержательным сообщением.
Попробуйте поискать аналогичные темы на форуме.

 Профиль  
                  
 
 Re: Разреженные матрицы и оптимизация их решения
Сообщение12.09.2016, 09:43 
Аватара пользователя


20/07/16
14
Germany
Deggial, так я находил обсуждения по этим темам у вас на форуме, тут есть люди, которые разбираются в этой теме.
И на других форумах советовали именно к вам обратиться

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group