How Sparse Matrices Work in Nelson: Architecture, Construction, and Operations

Nelson implements sparse matrices using the Eigen C++ library (Eigen::SparseMatrix), wrapping them in the ArrayOf container to support MATLAB-compatible syntax for construction, arithmetic, concatenation, and conversion operations.

Sparse matrices in the nelson-lang/nelson open-source numerical computing environment provide memory-efficient storage for large matrices with few non-zero elements. The implementation leverages the Eigen linear algebra library while exposing a high-level interpreter interface that mirrors MATLAB's sparse matrix functionality.

Architecture and Storage Format

Nelson stores sparse matrices using Eigen's Eigen::SparseMatrix class. Each sparse array is wrapped in an ArrayOf object—the generic container for all Nelson data types. The ArrayOf flag isSparse() marks the underlying data as a sparse matrix, and the actual Eigen pointer is held in the Data structure as a void*.

Key architectural components include:

• modules/types/src/include/SparseDynamicFunctions.hpp — Declares the C API used by the interpreter to dispatch sparse operations to the underlying Eigen implementation.
• modules/types/src/cpp/SparseDynamicFunctions.cpp — Loads the Eigen-based functions from the nlsSparse shared library at runtime.
• modules/sparse/src/cpp/SparseType.cpp — Implements low-level wrappers including Eigen_EyeSparseMatrixConstructor, Eigen_DeleteSparseMatrix, Eigen_MakeDenseArrayOf, Eigen_MakeSparseArrayOf, and Eigen_CopySparseMatrix.
• modules/types/src/include/ArrayOf.hpp — Provides the generic container API with methods like isSparse(), makeSparse(), and getSparseDataPointer().

Creating Sparse Matrices in Nelson

Nelson offers multiple constructors for creating sparse matrices, implemented in modules/sparse/src/cpp/SparseConstructors.cpp.

Basic Construction

% Empty sparse matrix of size m-by-n
S = sparse(m, n);

% From I,J,V triplets
S = sparse(I, J, V);

% With explicit dimensions
S = sparse(I, J, V, m, n);

% With pre-allocated non-zero count
S = sparse(I, J, V, m, n, nnz);

Helper Functions

MATLAB-compatible helper functions provide convenient entry points:

• sprand(m,n,density) — Generates a random sparse matrix with specified density (defined in modules/sparse/functions/sprand.m).
• sprandn(m,n,density) — Same as sprand but values drawn from a normal distribution.
• speye(m,n) — Creates a sparse identity matrix via Eigen_EyeSparseMatrixConstructor.
• spones(S) — Replaces all non-zero entries with 1 (implemented in SparseNonZeros.cpp with element-wise assignment).

Supported Sparse Matrix Operations

All operations are routed through the dynamic functions declared in SparseDynamicFunctions.hpp and implemented in the nlsSparse module.

Unary Operations

• Transpose (A') — Implemented in TransposeSparseDouble.cpp and TransposeSparseLogical.cpp. Creates a new Eigen matrix with swapped dimensions.
• Negation (-A) — Implemented in UminusSparse.cpp. Copies the matrix and multiplies each entry by -1.

Binary Arithmetic

When both operands are sparse, Nelson calls Eigen's sparse arithmetic kernels. If one operand is dense, the sparse operand converts to dense via Eigen_MakeDenseArrayOf.

• Addition/Subtraction (A + B, A - B) — Element-wise operations preserving sparsity when both inputs are sparse.
• Element-wise Multiplication/Division (A .* B, A ./ B) — Supported for compatible sparse matrices.
• Matrix Multiplication (A * B) — Uses Eigen's sparse-sparse or sparse-dense multiplication routines.

Concatenation

• Vertical ([A; B]) — VertCatSparseDouble.cpp and VertCatSparseLogical.cpp transpose the inputs, perform horizontal concatenation, then transpose back.
• Horizontal ([A, B]) — HorzCatSparseDouble.cpp and HorzCatSparseLogical.cpp directly build a larger sparse matrix by inserting the two blocks.

Indexing and Subsetting

Indexing operations use GetSparseVectorSubsetsDynamicFunction and GetSparseNDimSubsetsDynamicFunction to retrieve rows, columns, or elements via Eigen iterators.

% Extract row i
row_i = A(i, :);

% Extract column j
col_j = A(:, j);

% Extract submatrix
sub = A(1:10, 1:10);

Conversion and Utilities

• full(A) — Converts sparse to dense using Eigen_MakeDenseArrayOf.
• sparse(denseMatrix) — Converts dense to sparse using Eigen_MakeSparseArrayOf via SparseConstructor.
• nnz(A) — Returns the number of non-zeros via CountNonzerosDynamicFunction (calls Eigen::SparseMatrix::nonZeros()).
• [I,J,V] = IJV(A) — Extracts the internal triplet representation via SparseToIJVDynamicFunction.
• mustBeSparse(A) — Validator that raises Nelson:validators:mustBeSparse if A.isSparse() is false (implemented in mustBeSparseBuiltin.cpp).

Summary

• Nelson implements sparse matrices using Eigen's Eigen::SparseMatrix class, wrapped in the ArrayOf container with an isSparse() flag.
• Construction supports empty allocation, I/J/V triplet input, and MATLAB-compatible helpers like sprand, speye, and spones defined in SparseConstructors.cpp and related .m files.
• Supported operations include transpose, negation, arithmetic (+, -, .*, ./, *), vertical/horizontal concatenation, indexing, and conversion between sparse and dense formats.
• Utility functions nnz, IJV, and mustBeSparse provide introspection and validation capabilities, with implementations in SparseType.cpp and mustBeSparseBuiltin.cpp.

Frequently Asked Questions

What underlying library does Nelson use for sparse matrix storage?

Nelson uses the Eigen C++ template library, specifically the Eigen::SparseMatrix class. The library stores sparse data in a compressed column (or row) format using three arrays: outerIndexPtr, innerIndices, and valuePtr. Nelson wraps this Eigen object in its generic ArrayOf container and tracks the sparse property via the isSparse() method.

How do I convert a dense matrix to sparse format in Nelson?

Use the sparse() constructor. When passed a dense matrix, it calls SparseConstructor(fullMatrix), which internally invokes Eigen_MakeSparseArrayOf to create a compressed sparse representation. For example: S = sparse(eye(1000)) creates a sparse identity matrix without storing the full 1000×1000 dense array in memory.

What happens when I perform arithmetic between a sparse and a dense matrix?

Nelson's ArrayOf arithmetic operators first check the isSparse() flag for both operands. If one operand is sparse and the other is dense, the sparse operand is converted to dense using Eigen_MakeDenseArrayOf before the operation proceeds. This ensures compatibility but may increase memory usage. For efficient computation, keep both operands sparse when possible, as Eigen's sparse-sparse kernels avoid dense allocation entirely.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}