knappmatris

Knappmatris, commonly translated as sparse matrix, is a matrix that contains a relatively small number of nonzero elements compared with its overall size. In practice, a matrix is considered sparse when the majority of its entries are zero, which allows specialized storage and computational techniques to be used.

The defining feature of a knappmatris is its sparsity pattern, which can vary from a few nonzeros scattered throughout to banded or block structures. The density, defined as the ratio of nonzero elements to the total number of elements, is typically small. Exploiting sparsity reduces memory usage and accelerates many linear algebra operations, especially for large matrices.

To store knappmatriser efficiently, several sparse formats are commonly used. The most widespread are compressed sparse row (CSR) and compressed sparse column (CSC), which keep only the nonzero values and their indices. Coordinate (COO) format records triplets of row index, column index, and value. More specialized formats exist for particular sparsity patterns, such as diagonal, banded, or block sparse structures. The choice of format affects performance for specific operations like matrix-vector products or solving linear systems.

Operations on knappmatriser are optimized to skip zeros. A typical example is matrix-vector multiplication, which can run in O(nnz) time, where nnz is the number of nonzero elements. Solving sparse linear systems often relies on iterative methods (e.g., Conjugate Gradient, GMRES) with suitable preconditioners.

Applications are widespread, including finite element and finite difference discretizations, network and graph analysis, and large-scale data problems in machine learning. A common example is the sparse adjacency matrix of a graph, where most possible edges are absent.

Example: a 5x5 matrix with nonzeros only at positions (1,3)=7, (2,5)=4, (4,1)=1, (5,2)=9 is a knappmatris with four nonzeros.