Usage of Sparse Matrix Storage Format in Implementation of Finite Element Method

Finite element method (FEM) applied to a partial differential equation problem yields a system of algebraic equations in matrix form. Matrix of coefficients for the system (also known as stiffness matrix or nodal assembly matrix) is sparse. Memory allocation to keep and use the stiffness matrix in full form appears to be extremely inefficient in terms of memory usage, in some cases making it impossible to apply FEM because of available memory limitations. There are multiple storage formats purposed to keep and use a sparse matrix with maximum efficiency. However, known algorithmic implementations of such a storage formats like compressed column storage (CCS) are designed with assumption that a sparse matrix is available in full form and CCS is initialized from it. This paper describes a data structure and related algorithms making it possible to initialize CCS before the beginning of the stiffness matrix assembly stage, so that non-zero coefficients are written directly into CCS skipping memory allocation for stiffness matrix in full form.

References

[1] Pissanetzky S. Sparse matrix technology. Academic Press, 1984. 336 p. (Russ. ed.: Tekhnologiya razrezhennykh matrits. Moscow, Mir Publ., 1988. 410 p.).

[2] Iain S. Duff, Roger G. Grimes, John G. Lewis. Sparse matrix test problems. ACM Transactions on Mathematical Software, 1989, vol. 15, no. 1, pp. 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] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to algorithms. 2nd ed. McGraw-Hill Science/Engineering/Math, 2001. 1056 p. (Russ. ed.: Algoritmy. Postroenie i analiz. Moscow, Wil’yams Publishing House, 2005. 1296 p.).

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