SparseMatrix: Dynamic and Compressed Matrix Library in C++

Overview

This repository contains a high-performance, templated C++ library for sparse matrix operations. The library is designed to bridge the gap between dynamic matrix construction and efficient, cache-friendly mathematical operations.

The core architecture allows seamless transition between an uncompressed, dynamically mutable state (using a customized std::map) and a highly optimized compressed state (CSR/CSC). This ensures optimal memory usage and rapid computation for large-scale linear algebra tasks.

Features

• Templated Design: Supports arbitrary data types, including real numbers (double, float) and complex numbers (std::complex).
• Dual State Architecture: * Uncompressed State: Allows rapid insertion and modification of non-zero elements.
  • Compressed State: Converts the matrix into a Compressed Sparse Row (CSR) or Compressed Sparse Column (CSC) format for memory-efficient and cache-optimized operations.
• Flexible Storage Ordering: The StorageOrder template parameter dictates whether the matrix operates in a row-major or column-major fashion.
• Matrix Market Integration: Built-in parser to read and instantiate matrices directly from standard Matrix Market format files.
• Optimized Matrix-Vector Multiplication: Implements custom multiplication algorithms tailored specifically to the matrix's current state (compressed/uncompressed) and storage order (row/column-wise) to maximize cache hits.

Software Architecture

The Matrix<T, StorageOrder> Class

Located within the algebra namespace, this templated class manages the sparse matrix data lifecycle.

Internal Data Structures:

• Uncompressed Form (data): Utilizes a std::map<std::array<std::size_t, 2>, T> to map (i,j) coordinates to values. A custom CompareOperator modifies the lexicographic ordering of the keys based on the StorageOrder template parameter, ensuring that map traversal naturally follows the intended row or column-wise sequence.
• Compressed Form (compr): Utilizes three flat std::vector arrays (inner, outer, values) to strictly adhere to standard CSR/CSC memory layouts.

Key Methods:

• compress() / uncompress(): Handles the algorithmic transformation between the map-based dynamic state and the vector-based compressed state. To ensure zero memory overhead, the inactive data structure is explicitly cleared after state transition.
• operator()(i, j): Provides coordinate access. In the uncompressed state, the non-const version allows insertion. In the compressed state, it is restricted to modification of existing non-zero elements or read-only access to preserve the structural integrity of the CSR/CSC format.
• extract(i): Leverages std::map::lower_bound and upper_bound for efficient extraction of entire rows or columns when in the uncompressed state.
• norm<NormType>(): Computes the Frobenius, L1, or L-Infinity norm.

Operator Overloads & Metaprogramming

• Matrix-Vector Products: Friend operators handle multiplication with both std::vector and single-column Matrix objects. The implementation relies heavily on if constexpr to resolve the optimal algorithm (row-times-vector vs. linear combination of columns) at compile-time based on the StorageOrder.
• Complex Number Support: Custom equality operators bridge std::complex and real types, enabling robust zero-checking algorithms across different numeric domains.

Performance and Results

The included main.cpp driver provides a benchmarking suite utilizing the Chrono utility to evaluate the efficiency of the matrix-vector multiplication implementations.

Testing against standard Matrix Market datasets reveals significant computational acceleration when utilizing the compressed formats:

• Row-Wise Storage (CSR): Operations are approximately 20x faster compared to the uncompressed dynamic map.
• Column-Wise Storage (CSC): Operations are approximately 6x faster compared to the uncompressed state.

These results highlight the critical necessity of cache-friendly memory layouts (contiguous vectors) over pointer-based tree structures (std::map) for intensive linear algebra operations.