#java #concurrency #linear-algebra #sparse-matrix
#java #параллелизм #линейная алгебра #разреженная матрица
Вопрос:
Я ищу библиотеку матриц / линейной алгебры на Java, которая предоставляет разреженную матрицу, в которую можно записывать одновременно из разных потоков. Большинство библиотек, с которыми я сталкивался, либо вообще не предоставляют разреженные матрицы, либо 1.) поддерживают их открытой адресной хэш-картой, либо 2.) затем сохраняют в формате CSR или CSC, который вообще не поддается многопоточному построению. Прямо сейчас я собираю записи параллельно, используя параллельную хэш-карту, и они заполняют разреженную матрицу из одного потока, но это кажется пустой тратой ресурсов (пространство для хранения параллельной хэш-карты и время, чтобы по существу заполнить матрицу дважды).).
Комментарии:
1. Вы пробовали Colt? acs.lbl.gov/software/colt
2. Я посмотрел на colt. Проблема с их разреженной матрицей ( acs.lbl.gov/software/colt/api/cern/colt/matrix/impl / … ), как подробно описано в примечании к реализации, заключается в том, что она использует OpenIntDoubleHashMap и поэтому не синхронизирована.
Ответ №1:
Вы не можете просто волшебным образом сделать процедуры алгебры разреженных матриц масштабируемо параллельными. Для решения этих проблем используются некоторые из самых сложных алгоритмов численного анализа, которые все еще являются предметом интенсивных исследований.
Вы не говорите, что вы хотите делать с этими матрицами, но я полагаю, что вы хотите решение систем линейных уравнений. Если вы хотите, чтобы это было параллельно, вам понадобится сторонняя библиотека, очень большие матрицы и, вероятно, немного денег.
Наиболее распространенный способ сборки разреженных матриц — это собрать их в формате триплета и преобразовать в формат сжатой строки или столбца. Сборка может быть дорогостоящей, но ее легко выполнять параллельно. Просто позвольте каждому потоку иметь свой собственный список триплетов и соедините их вместе перед преобразованием в сжатый формат.
Комментарии:
1. Привет, Дэвид, спасибо за твой ответ. На самом деле я не хочу решать линейную систему с помощью матрицы. Однако мне нужно вычислить матрично-векторное произведение. Однако из вашего ответа я понял, что одновременное построение разреженной матрицы — это скорее что-то типа «сверни свое»?
2. матричный векторный продукт может выполняться параллельно, но вам нужны большие матрицы, чтобы сделать его полезным. Конечно, вам не нужно сжатое хранилище для этой операции, но это все равно может быть более эффективным. Как вы в настоящее время строите свои матрицы? Используете ли вы триплеты?
3. Прямо сейчас я использую реализацию Apache Commons Math sparse matrix. Это одна из тех, на которые я ссылался выше, которая не является потокобезопасной и поддерживается хэш-картой. В настоящее время я строю матрицу, помещая все записи в ConcurrentHashMap, а затем последовательно строю матрицу из этой хэш-карты в одном потоке. Я предполагаю, что мне нужен класс matrix, которому я могу просто передать уже созданный список триплетов, или который по своей сути потокобезопасен.
4. Они варьируются от небольших (~ 10 000 x 10 000) до средних (~ 100 000 x 100 000) по размеру — некоторые могут быть больше в будущем. Они, как правило, имеют плотность около 1%.
5. Если вы просто умножаете матрицу на что-то, вам не нужно, чтобы она была потокобезопасной. Вы можете разделить свою проблему на параллельные задачи и просто быть осторожными, когда объединяете результаты задач вместе. Вы также должны быть осторожны, чтобы все задачи начинались с одной и той же матрицы.
Ответ №2:
Я помню, что матрицы в параллельном colt были потокобезопасными. Библиотека представляет собой многопоточную версию colt.
Комментарии:
1. Похоже, что, хотя некоторые операции с матрицей операций распараллелены в «parallel colt», фактическая реализация разреженной матрицы в основном такая же, как у colt. Это означает, что она использует одно и то же серверное хранилище, запись которого не является потокобезопасной.