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

Question

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

Answer 1

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

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

Answer 2

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

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