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