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

Question

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

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

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

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

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

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

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

Спасибо.

Answer 1

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

Answer 2

Я был очень доволен использованием MKL от Intel.

Answer 3

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

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

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

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

Answer 4

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

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

Я не уверен, что ваше требование 4. удовлетворён ли вне коробки, но он может быть легко закодирован с использованием метода refEntry.

Answer 5

Пробег: TAUCS или MUMPS.

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

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

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