MATLAB - Sparse Matrix

MATLAB - Sparse Matrices

In numerical computing, a sparse matrix is a matrix in which most of the elements are zero. In contrast, a matrix where most elements are non-zero is called a dense matrix. Storing and manipulating sparse matrices as if they were dense is extremely inefficient in terms of both memory and computation time.

MATLAB has a powerful and efficient implementation for sparse matrices that stores only the non-zero elements and their indices.

Why Use Sparse Matrices?

Sparse matrices are critical in many fields of science and engineering, including network analysis, finite element modeling, and computational fluid dynamics. The key advantages are:

• Efficient Memory Usage: Storing a 10,000 x 10,000 dense matrix requires 10000 * 10000 * 8 bytes (approx. 800 MB). If this matrix has only 50,000 non-zero elements, the sparse representation will only use a few megabytes, a dramatic saving.
• Computational Speed: Operations like matrix-vector multiplication or solving linear systems (A\b) are significantly faster because the algorithms are designed to skip operations involving zeros.

The main trade-off is that accessing or modifying individual elements can sometimes be slower than with dense matrices due to the more complex indexing required.

Creating Sparse Matrices

You can create sparse matrices in MATLAB in several ways.

1. Converting from a Dense Matrix

The simplest way is to convert an existing dense matrix using the sparse() function. MATLAB will automatically find the non-zero elements and create the sparse data structure.

Example 1: Basic Conversion

% 1. Create a dense matrix with many zeros
A_dense = [0, 0, 8, 0;
           5, 0, 0, 0;
           0, 2, 0, 0;
           0, 0, 0, 9];

% 2. Convert it to a sparse matrix
S = sparse(A_dense);

% Display the sparse matrix
disp(S);

Output: MATLAB’s output for a sparse matrix is a list of the non-zero elements and their (row, column) indices. The nnz count indicates the number of non-zeros.

   (2,1)        5
   (3,2)        2
   (1,3)        8
   (4,4)        9

To see the full matrix representation (if it’s small enough), you can use the full() function:

full(S)

ans =

     0     0     8     0
     5     0     0     0
     0     2     0     0
     0     0     0     9

2. Creating from Coordinate-List (COO) Format

A more efficient method, especially for very large matrices, is to create the sparse matrix directly from lists of row indices, column indices, and their corresponding values. This avoids creating the large dense matrix in memory first.

Syntax

S = sparse(rows, cols, values, m, n)

• rows: vector of row indices for each non-zero value.
• cols: vector of column indices for each non-zero value.
• values: vector of the non-zero values themselves.
• m: total number of rows in the desired matrix.
• n: total number of columns in the desired matrix.

Example 2: Direct Creation

% Define the components of the sparse matrix
rows   = [1, 2, 3, 4, 4];
cols   = [3, 1, 2, 4, 1];
values = [10, 20, 30, 40, 50];

% Define the final size of the matrix
m = 5; % 5 rows
n = 5; % 5 columns

% Create the sparse matrix
S_direct = sparse(rows, cols, values, m, n);

% Display the result
disp(full(S_direct));

Pro Tip: If you provide duplicate (row, col) pairs, sparse will sum the corresponding values. This is a very useful feature for assembling matrices from elemental contributions in methods like finite element analysis.

Output:

     0     0    10     0     0
    20     0     0     0     0
     0    30     0     0     0
    50     0     0    40     0
     0     0     0     0     0

Operations with Sparse Matrices

You can perform standard arithmetic on sparse matrices just like with dense matrices. MATLAB’s operators are overloaded to use highly efficient sparse algorithms automatically.

Example 3: Solving a Sparse Linear System

One of the most important applications of sparse matrices is solving the linear system Ax = b, where A is large and sparse.

% Create a large, sparse, diagonally-dominant matrix
n = 1000;
A = spdiags([-1*ones(n,1), 3*ones(n,1), -1*ones(n,1)], -1:1, n, n);

% Create a dense vector
b = ones(n, 1);

% Solve the system Ax = b using the backslash operator
% This is highly optimized for sparse matrices!
tic;         % Start timer
x = A \ b;
toc;         % End timer

% Compare to solving with a dense matrix (for demonstration)
% WARNING: This can be very slow and memory-intensive!
% A_dense = full(A);
% tic; x_dense = A_dense \ b; toc;

Expected Output: The code will execute very quickly and display the elapsed time, which should be very small. If you were to uncomment and run the dense version, you would notice it is significantly slower and uses much more memory. This demonstrates the power of using sparse matrices for large-scale problems.

Elapsed time is 0.001234 seconds.