Ищем интерфейс C / C ++ для эффективного вычисления огромной разреженной матрицы в Linux

Question

Я ищу интерфейс C / C ++ для эффективного вычисления огромной разреженной матрицы в Linux.Матрица может быть в миллионы раз миллионы / тысячи.Я проверил несколько существующих библиотек, но, похоже, ни одна из них не удовлетворяет всем моим требованиям,

1, мне нужно создать разреженную матрицу, динамически добавляя в нее элементы.(не для SparseLib ++)

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

3, он должен поддерживать операции матрицы, умноженные на матрицу / вектор (многие библиотеки поддерживают этибазовые операции)

4, он должен поддерживать пошаговое умножение или деление двух разреженных матриц или векторов, например. * или ./ в MATLAB (не нашел для этого библиотеку, и мне нужно этооперация, чтобы отфильтровать некоторые записи одной разреженной матрицы с другой разреженной матрицей)

5, Инверсия матрицы или линейный решатель.(Большинство библиотек предоставляют решатель для линейной системы)

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

Спасибо.

Answer 1

Я бы порекомендовал CSparse Тимом Дэвисом.

Обновление (2019): С тех пор Тим Дэвис выпустил SuiteSparse . Это удовлетворяет всем требованиям, перечисленным в посте, включая возможность поэтапного построения матрицы (см. слайд 34 в презентации RedisGraph или «3.1.8 Неблокирующий режим» в документе SuiteSparse: GraphBLAS ).

Answer 2

Вы смотрели на LinBox ?Он поддерживает несколько форматов хранения разреженных матриц, некоторые из которых позволяют вам устанавливать записи после создания матрицы:

// set m[i,j] to a
m.refEntry(i, j) = a;

Я не уверен, удовлетворяется ли ваше требование 4. из-заполе, но его можно легко закодировать с помощью метода refEntry.

Answer 3

Увы, в большинстве библиотек с разреженной матрицей используется формат, который очень затрудняет динамическую установку элементов (Google для Compressed Sparse Row, который является наиболее распространенным форматом).

Как вы сказали, большинство библиотек предоставляют вам все ваши требования, кроме # 1. Для # 2 это обычно легко, когда вы понимаете формат хранения.

Intel MKL предоставляет решатель PARDISO, который не навязывает формат, он требует только того, чтобы вы могли создавать матричные / векторные продукты: вы вызываете солвер в цикле, получаете из него код возврата и выполняете то, что он просит вас сделать (умножение на A, проверка условия завершения, предварительная обработка, ...). Таким образом, вы можете использовать любую схему хранения, которая вам нужна. Это полезно, например, если вы не хотите хранить матрицу или если у вас есть какой-то необычный формат хранения.

Ваши требования (особенно # 1) делают превосходным кандидатом на разреженные матрицы на основе квадродеревьев . Однако я не знаю ни одной хорошей реализации этого. Если вам удастся закодировать его / найти реализацию, я был бы признателен.

Answer 4

Я был очень счастлив, используя Intel MKL .

Answer 5

Попробуйте TAUCS или MUMPS .

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

Я согласен с Александром, что эти пакеты поставляются с собственным «форматом» для кодирования разреженной матрицы, но это неизбежно, поскольку вы должны сообщить решающему, где находятся ненулевые элементы.Но, с другой стороны, их не сложно освоить.TAUCS, кстати, использует формат хранения сжатых столбцов (CCS).То, на что ссылается Александр, - это, вероятно, сжатое хранилище строк (CRS).Я думаю, что есть еще один популярный формат, который явно кодирует значение элемента с помощью (i, j) «местоположения» элемента в матрице, но это о нем.

Подробнее об этих пакетах см. www.matrixprogramming.com .