Параллельное создание разреженных матриц

Существуют ли какие-либо алгоритмы, которые позволяют эффективно создавать (заполнять элементами) разреженную (например, CSR или координатную) матрицу параллельно?


parallel-processing csr sparse-matrix
person Fic Firic    schedule 01.08.2010    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Если вы храните свою матрицу как карту координат, любой язык, имеющий доступную параллельную реализацию словаря, должен сделать эту работу за вас.

У Java есть ConcurrentHashMap, а у .NET 4 есть ConcurrentDictionary, оба из которых позволяют многопоточную неблокирующую (афаик) вставку элементов параллельно.

person tzaman    schedule 01.08.2010
comment
Параллелизм и параллелизм — не одно и то же. Проблема здесь заключается в действительно параллельном по данным заполнении элементов в разреженной матрице. В частности, в моем случае я хочу реализовать это на графических процессорах. - person Fic Firic; 01.08.2010

arrow_upward
0
arrow_downward

Не существует эффективных алгоритмов для создания разреженных матриц параллельным по данным способом. Правдоподобным является тип координатной матрицы, который требует сортировки после заполнения содержимого, но этот тип медленный для матричных продуктов и т. д.

Решение заключается в том, что вы не строите разреженную матрицу — вы не храните ее в памяти; вы выполняете неявные операции на месте, когда вычисляете элементы разреженной матрицы.

person Fic Firic    schedule 03.08.2010