Использование форматов хранения разреженных матриц при реализации метода конечных элементов

Применение метода конечных элементов сводит краевую задачу для уравнения в частных производных к решению системы линейных алгебраических уравнений в матричной форме. По построению, матрица коэффициентов системы линейных алгебраических уравнений (также называемая матрицей жесткости) является разреженной. Выделение памяти для хранения разреженной матрицы коэффициентов в полной форме оказывается чрезвычайно неэффективным решением, в некоторых случаях делающим использование метода конечных элементов невозможным вследствие ограничений по доступной памяти. Существует ряд форматов представления разреженных матриц, предназначенных для их хранения и использования с максимальной эффективностью. Известные реализации таких форматов, как CCS (compressed column storage) разработаны в предположении, что сохраняемая матрица доступна в полной форме, и CCS создается из нее. Предложена дополнительная структура данных и алгоритмы, позволяющие инициализировать CCS до начала сборки матрицы коэффициентов с тем, чтобы собирать матрицу коэффициентов с записью ненулевых коэффициентов непосредственно в формате CCS, минуя стадию инициализации матрицы коэффициентов в полной форме.

Литература

[1] Писсанецки С. Технология разреженных матриц / пер. с англ. М.: Мир, 1988. 410 с.

[2] Iain S. Duff, Roger G. Grimes, John G. Lewis. Sparse matrix test problems // ACM Transactions on Mathematical Software. 1989. Vol. 15. No. 1. P. 1-14.

[3] Saad Y. Iterative methods for sparse linear systems. 2nd ed. SIAM, 2003. 528 p.

[4] Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical recipes the art of scientific computing. Cambridge University Press., 2007. 1256 p.

[5] Кормен Томас Х., Лейзерсон Чарльз И., Ривест Рональд Л., Штайн Клиффорд. Алгоритмы. Построение и анализ / пер. с англ. М.: Издательский дом "Вильямс", 2005. 1296 с.

[6] Bathe Klaus-Jurgen. Finite element procedures. Prentice Hall, 1995. 1037 p.