Эффективно поиск массивов в FORTRAN

Question

Я пытаюсь сохранить матрицу жесткости в FORTRAN в разреженном формате для сохранения памяти, т. Е. Я использую три вектора ненулевых элементов (irows, icols, A). После определения размера этих массивов следующим шагом будет вставка значений в них. Поэтому я использую точки gauss, т. Е. Для каждой точки gauss я собираюсь найти локальную матрицу жесткости, а затем вставить эту локальную матрицу жесткости в Global (irows, icols, A).

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

Может ли кто-нибудь предложить лучший способ вставки локальной матрицы жесткости для каждой точки гаусс глобальной матрицы жесткости.

Answer 1

Я вполне уверен, что это хорошо известная проблема в анализе FEM - я нашел ссылку на нее в этом scipy documentation, но, конечно, принципы не зависят от языка. В основном, что вам нужно сделать, это создать свою матрицу в том формате, который у вас есть, но вместо того, чтобы искать матрицу, чтобы увидеть, существует ли запись, просто предположите, что она этого не делает. Это означает, что вы получите дублирующиеся записи, которые необходимо добавить вместе, чтобы получить правильное значение.

После того, как вы построили свою матрицу, вы обычно конвертируете ее в более эффективную форму для ее решения (например, CSR etc.). Точный формат может быть определен разреженным решателем, который вы используете. Во время этого процесса преобразования дублирующиеся записи должны быть добавлены вместе - и некоторые редкие библиотеки матриц сделают это для вас. Я знаю, что scipy делает это, и многие из его внутренних процедур написаны в fortran, поэтому вы можете использовать один из них (все они с открытым исходным кодом). Или вы можете проверить, подходит ли что-либо по адресу netlib.

Answer 2

Если вы используете структуру данных, предварительно отсортированную, было бы очень удобно ее искать. Либо как ваша основная структура данных, либо как вспомогательная структура данных. Вы хотите, чтобы вы могли вставить другую запись в середину. Например, двоичное дерево поиска (http://en.wikipedia.org/wiki/Binary_search_tree).