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, Супермодераторы



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

Сейчас этот форум просматривают: DariaRychenkova


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

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