Есть ли эффективный способ динамического изменения compress_matrix в boost?

Я использую ublas:: Compressed Matrix для работы с UMFPACK, редким линейным решателем. Так как я делаю симуляцию, так каждый раз, когда линейная система создается несколько иначе, что может включать в себя увеличение/уменьшение матрицы коэффициентов и некоторых разреженных матричных умножений. Шкала линейной системы составляет около 25 000.

Даже если есть обязательный патч для повышения эффективности работы с UMFPACK, мне все равно нужно время от времени менять матрицу, иногда даже вычислять количество ненулевых значений было бы трудоемким (в идеале я должен укажите число ненулевых значений при инициализации матрицы). Кроме того, я использую ublas:: range для динамического добавления столбцов/строк.

Итак, мой вопрос: есть ли эффективный способ сделать это? Сейчас это слишком медленно для меня. Транспонирование матрицы с размером как 15k стоит около 6 с, а добавление около 12 тыс. Строк - это быстро (потому что я предполагаю, что это матрица строк), но добавление одинакового количества столбцов в матрицу может стоить до 20 с (я предполагаю, что для того же как и выше, так что даже я использовал матрицу столбцов, общее требуемое время было бы таким же).

Своего рода отчаяние. Любое предложение приветствуется.

Приветствия.

Ответ 1

Я не знаком с вашими пакетами, но почему вы (в идеале) должны указать количество ненулевых элементов в вашей матрице? Не можете ли вы переопределить и уменьшить размер?

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

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

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

Ответ 2

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

И вы используете флаг -DNDEBUG, для uBlas, правильно?

Я еще не уверен, в чем проблема...

Бест, Умут

Ответ 3

Вместо того, чтобы строить А, объединив несколько разных наборов значений, рассмотрели ли вы их сохранение в отдельных матрицах и используя существующие алгоритмы решения, чтобы построить свой собственный общий решатель? В принципе, вы должны применить соответствующее разложение (LU, QR, что угодно) к одной компонентной матрице, запустить соответствующее обновление/преобразование для последующих компонентов и повторить для каждой последующей матрицы. Затем вы можете использовать матрицы компонентов с факторизацией для вычисления вашего решения. Неясно, поддерживает ли библиотека, с которой вы работали, или вам придется писать некоторые/все численные подпрограммы самостоятельно.

Ответ 4

Вы попробовали Eigen для такого рода проблем? Недавно они завершили поддержку разреженных матриц.