Storage formats

After applying the finite element method, the problem reduces to a system of linear algebraic equations

The matrix $A$ in such a system is usually large but sparse: almost all of its elements are zero. This is natural for FEM — each simplex is connected only to a small number of neighbouring nodes, so a single row of the global matrix contains nonzero elements only at the positions of the local neighbourhood of a node. Storing such a matrix as a dense table is wasteful: most of the memory is spent on zeros, and matrix-vector multiplication performs many useless operations.

In a FEM implementation it is convenient to use three representations of one and the same sparse matrix.

1. COO (coordinate list) stores the matrix as a list of triples $(i, \; j, \; a_{ij})$, where $i$ is the row index, $j$ is the column index, and $a_{ij}$ is the element value. The format is convenient when assembling the global matrix: the local matrices of the simplices are simply appended to the common list, and duplicate indices are summed.
2. CSR (compressed sparse row) stores the matrix row by row in three arrays: the values of the nonzero elements, their column indices, and the array of offsets of the beginning of each row. The format is inconvenient for adding new elements, but optimal for the operation $A \cdot x$, which is performed at every iteration.
3. CSC (compressed sparse column) is the column analogue of CSR. It is not needed for solving the system, but it is useful when multiplying two sparse matrices, when fast access to the elements of the right matrix by columns is required.

All three formats for one and the same matrix $A$ are shown in figure (3.1).

Next, let us talk about the solution method.