Code Generation for Sparse Matrices

Sparse matrices provide efficient storage in memory for arrays with many zero elements. Sparse matrices can provide improved performance and reduced memory usage for generated code. Computation time on sparse matrices scales only with the number of operations on nonzero elements.

Functions for creating and manipulating sparse matrices are listed in Sparse Matrices. To check if a function is supported for code generation, see the function reference page. Code generation does not support sparse matrix inputs for all functions.

Sparse Data Types in Generated Code

If your target language is C, the code generator creates a type definition for sparse matrices called sparse. This definition stores the arrays of row indices, column indices, and corresponding element values for the sparse matrix. The sparse type definition is generated in the file myFunction_types.h, where myFunction refers to the name of your top-level function.

If your target language is C++, the code generator creates a class sparse in the file sparse.h.

The number of nonzero elements in a sparse matrix can change during computation. For this reason, sparse matrices in the generated code use variable-size arrays and dynamic memory allocation. If your target language is C, the generated code implements dynamically allocated variables by using the emxArray type. If your target language is C++, the generated code implements dynamically allocated variables by using the coder::array class template.

For example, consider the function myDiag:

function out = myDiag(n,k)
% create diagonal sparse matrix
A = speye(n);
out = A.*k;

Generate code for the function by using the codegen command:

codegen -config:lib myDiag -args {3, 5} -launchreport

The sparse type can be found in the file myDiag_types.h.

Input Definition

Suppose that you have a function foo that accepts a sparse matrix as an input. This function multiplies the sparse matrix by an identity matrix and outputs the product:

function C = foo(ASparseInput)
B = speye(size(ASparseInput'));
C = ASparseInput*B;

Suppose that you want to generate standalone lib, dll, or exe code to use outside of the MATLAB® environment. To generate lib code, enter:

codegen -config:lib foo -args {sparse(5,5)} -launchreport

You can simplify your standalone code by constructing the sparse matrix inside your entry-point function rather than passing a sparse matrix as an input. When you follow this guideline, construction of the sparse matrix can be deferred to the code generator. Other code that uses your generated code can pass input types such as arrays rather than specialized sparse types.

For example, instead of generating code directly from foo, create a new entry-point function fooMain to generate code from. Replace the sparse input with the triplet form of the sparse data.

function [ii,jj,out] = fooMain(i,j,v,m,n)
S = sparse(i,j,v,m,n);
[ii,jj,out] = find(foo(S));

Suppose that you want to generate code for a 5-by-5 sparse matrix S with a variable-size number of nonzero elements. To generate code, enter:

S = sparse(5,5);
[m,n] = size(S);
[i,j,v] = find(S);
i = coder.typeof(i,[inf 1]);
codegen -config:lib fooMain -args {i,i,i,m,n} -launchreport

You can specify the input for fooMain with integer and variable-size array types. If you generate code directly from foo, you must construct the input as a sparse type.

If you do choose to pass a sparse matrix as an entry-point function input, you can use coder.typeof to initialize the input. For example, for the function foo, you can enter:

t = coder.typeof(sparse(5,5));
codegen -config:lib foo -args {t} -launchreport

For sparse matrices, the code generator does not track upper bounds for variable-size dimensions. All variable-size dimensions are treated as unbounded.

If you generate a MEX function for foo, the input and output data must be converted to sparse type. This conversion can slow performance for repeated MEX function calls or large inputs and outputs.

You cannot define sparse input types programmatically by using assert statements.

Code Generation Guidelines

Initialize matrices by using sparse constructors to maximize your code efficiency. For example, to construct a 3-by-3 identity matrix, use speye(3,3) rather than sparse(eye(3,3)).

Indexed assignment into sparse matrices incurs an overhead compared to indexed assignment into full matrices. For example:

S = speye(10);
S(7,7) = 42;

As in MATLAB, sparse matrices are stored in compressed sparse column format. When you insert a new nonzero element into a sparse matrix, all subsequent nonzero elements must be shifted downward, column by column. These extra manipulations can slow performance.

Code Generation Limitations

To generate code that uses sparse matrices, dynamic memory allocation must be enabled. To store the changing number of nonzero elements, and their values, sparse matrices use variable-size arrays in the generated code. To change dynamic memory allocation settings, see Control Memory Allocation for Variable-Size Arrays. Because sparse matrices use variable-size arrays for dynamic memory allocation, limitations on Variable-Size Data also apply to sparse matrices.

You cannot assign sparse data to data that is not sparse. The generated code uses distinct data type representations for sparse and full matrices. To convert to and from sparse data, use the explicit sparse and full conversion functions.

You cannot define a sparse matrix with competing size specifications. The code generator fixes the size of the sparse matrix when it produces the corresponding data type definition in C/C++. As an example, the function foo causes an error in code generation:

function y = foo(n)
if n > 0
    y = sparse(3,2);
    y = sparse(4,3);

Logical indexing into sparse matrices is not supported for code generation. For example, this syntax causes an error:

S = magic(3);
S(S > 7) = 42;

For sparse matrices, you cannot delete array elements by assigning empty arrays:

S(:,2) = [];

See Also

| | | | |

Related Topics