Треугольные и разреженные матрицы в C++

Это очень простой вопрос: как лучше всего работать с треугольными матрицами и работать с разреженными матрицами в C++?

Для треугольной матрицы я предлагаю такой простой формат данных, как

double* myMatrix;
int dimension;

как структура данных в пользовательском классе. (Предполагаю, что это была квадратная матрица в полном виде.) И будут методы установки и доступа к элементам.

Для разреженных матриц - я знаю пару методов, таких как сохранение только позиций элементов в строке/столбце и их значений. Это вопрос к вашему опыту - какая реализация разреженной матрицы будет лучшей?

P.S. Меньше памяти, меньше загрузки процессора — вот моя цель, я ищу лучшее решение, а не самое простое. Все матрицы будут использованы для решения систем линейных уравнений. И размер матриц будет огромным.

Большое спасибо за каждый совет!


c++ performance memory-management sparse-matrix
person Pavel Oganesyan    schedule 14.04.2012    source источник
comment
Как насчет сторонней библиотеки, такой как Eigen?   -  person Vaughn Cato    schedule 14.04.2012
comment
Если вы не являетесь экспертом, используйте уже существующие библиотеки. Я рекомендую коды Тима Дэвиса, например. CSparse, УМФПАК.   -  person David Heffernan    schedule 14.04.2012
comment
Сторонняя библиотека не является решением в моей ситуации. Возможно, я могу искать решения с открытым исходным кодом и использовать некоторые части, как позволяет их лицензия, но я не могу добавить внешние модули в виде dll и libs в свой проект по некоторым причинам.   -  person Pavel Oganesyan    schedule 14.04.2012
comment
Кажется, существует приличное количество существующих исследований. Сначала посмотрите туда: en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix   -  person bitmask    schedule 14.04.2012
comment
Кто сказал что-нибудь о DLL? Я использую сторонний код (CSparse) и просто компилирую его в свой код. В любом случае, если вы абсолютно ничего не знаете об алгоритмах разреженных матриц, попытка написать эффективный алгоритм, начинающийся с вопроса о переполнении стека, обречена на провал. По крайней мере, купите хорошую книгу. Опять же, книга Тима Дэвиса превосходна.   -  person David Heffernan    schedule 15.04.2012
comment
См. библиотеку шаблонов матриц.   -  person Peter Wood    schedule 15.04.2012
comment
Как насчет использования std::map‹std::pair‹int,int›,double›?   -  person Vaughn Cato    schedule 15.04.2012
comment
@DavidHeffernan Я просто спросил, делал ли кто-нибудь что-нибудь с такими алгоритмами самостоятельно и может дать совет немного лучше, чем Google и повторное использование. И я не надеялся, что вопрос на SO станет чудом для решения моих проблем :) Поскольку большинство людей говорят, что CSparse лучший, я посмотрю на него. Спасибо.   -  person Pavel Oganesyan    schedule 15.04.2012

Ответы (1)


arrow_upward
1
arrow_downward

Если вы понятия не имеете о структуре матрицы, то это в основном то же самое, что и карта. Вы можете использовать std::map<std::pair<int,int>,double>. Или, возможно, std::unordered_map, если он у вас есть.

person Vaughn Cato    schedule 14.04.2012