После применения метода конечных элементов задача сводится к системе линейных алгебраических уравнений

Матрица $A$ в такой системе обычно большая, но разреженная: почти все её элементы равны нулю. Это естественно для МКЭ — каждый симплекс связан лишь с небольшим числом соседних узлов, поэтому одна строка глобальной матрицы содержит ненулевые элементы только в позициях локальной окрестности узла. Хранить такую матрицу как плотную таблицу расточительно: большая часть памяти уходит на нули, а умножение матрицы на вектор выполняет много лишних операций.

В реализации МКЭ удобно использовать три представления одной и той же разреженной матрицы.

1. COO (coordinate list) хранит матрицу как список троек $(i, \; j, \; a_{ij})$, где $i$ — номер строки, $j$ — номер столбца, $a_{ij}$ — значение элемента. Формат удобен при сборке глобальной матрицы: локальные матрицы симплексов просто добавляются в общий список, а дублирующиеся индексы суммируются.
2. CSR (compressed sparse row) хранит матрицу построчно в трёх массивах: значений ненулевых элементов, номеров их столбцов и массива смещений начала каждой строки. Формат неудобен для добавления новых элементов, зато оптимален для операции $A \cdot x$, которая выполняется на каждой итерации.
3. CSC (compressed sparse column) — столбцовый аналог CSR. Для решения системы он не нужен, но полезен при умножении двух разреженных матриц, когда требуется быстрый доступ к элементам по столбцам правой матрицы.

Все три формата для одной и той же матрицы $A$ показаны на рисунке (3.1).

Далее поговорим о методе решения.