Motivation:
Why is this needed?
stdlib currently lacks native structures for highly symmetric dense matrices. The official documentation specifically notes that Toeplitz and Circulant matrices are "not yet supported."
Researchers and engineers frequently deal with:Signal processing and linear time-invariant (LTI) system modeling.
Solving partial differential equations using finite difference methods.Time-series analysis and auto-correlation matrices.
While libraries in Python (SciPy) and MATLAB have built-in functions to handle these memory-efficiently, Fortran developers areforced to instantiate massive dense arrays and use standard matmul for these structures. Providing a native, compressed matrix implementation fulfills a critical gap in the modern Fortran stdlib ecosystem.
Implementation Idea: Compressed Storage and Custom SpMVI propose implementing a dedicated special matrices module (e.g., stdlib_specialmatrices_toeplitz.fypp) entirely in Fortran
.Why Pure Fortran?
It seamlessly extends the existing stdlib_specialmatrices architecture (like the current tridiagonal.fypp) while maintaining zero external dependencies.Massive Memory Savings: A dense N X N matrix requires storing N^2 elements. A Toeplitz matrix only requires storing the first column and first row, reducing the memory footprint to exactly 2N - 1 elements.
Guaranteed Performance: Custom Sparse Matrix-Vector (SpMV) drivers will utilize the compressed $2N-1$ array. Even with a direct loop approach, the cache locality and memory bandwidth savings provide a massive speedup over unpacking into a standard dense matmul.
The implementation will follow a 3-stage structure:
Derived Type: Define a toeplitz_matrix type that safely encapsulates the 2N-1 elements to prevent invalid state manipulation.
Constructors: Provide user-friendly initialization interfaces accepting either a single 2N-1 array or separate column/row vectors.
SpMV Driver: Overload the * operator (or provide a matmul equivalent) to compute y = T xefficiently on the compressed data.
Prior Art
SciPy (scipy.linalg.toeplitz): The Python standard for initializing and interacting with these structures.
MATLAB (toeplitz): The gold standard for user-friendly matrix generation in engineering workflows
.Additional Information
Initial Scope: Support for standard real and complex kinds (sp, dp, qp) using fypp templating. The initial SpMV will use the direct O(N^2) memory-efficient loop.Future Extension: The architecture will allow for easy upgrading to Fast Fourier Transform (FFT) based O(N log N) multiplication in the future once the base types are merged.
Motivation:
Why is this needed?
stdlib currently lacks native structures for highly symmetric dense matrices. The official documentation specifically notes that Toeplitz and Circulant matrices are "not yet supported."
Researchers and engineers frequently deal with:Signal processing and linear time-invariant (LTI) system modeling.
Solving partial differential equations using finite difference methods.Time-series analysis and auto-correlation matrices.
While libraries in Python (SciPy) and MATLAB have built-in functions to handle these memory-efficiently, Fortran developers areforced to instantiate massive dense arrays and use standard matmul for these structures. Providing a native, compressed matrix implementation fulfills a critical gap in the modern Fortran stdlib ecosystem.
Implementation Idea: Compressed Storage and Custom SpMVI propose implementing a dedicated special matrices module (e.g., stdlib_specialmatrices_toeplitz.fypp) entirely in Fortran
.Why Pure Fortran?
It seamlessly extends the existing stdlib_specialmatrices architecture (like the current tridiagonal.fypp) while maintaining zero external dependencies.Massive Memory Savings: A dense N X N matrix requires storing N^2 elements. A Toeplitz matrix only requires storing the first column and first row, reducing the memory footprint to exactly 2N - 1 elements.
Guaranteed Performance: Custom Sparse Matrix-Vector (SpMV) drivers will utilize the compressed$2N-1$ array. Even with a direct loop approach, the cache locality and memory bandwidth savings provide a massive speedup over unpacking into a standard dense matmul.
The implementation will follow a 3-stage structure:
Derived Type: Define a toeplitz_matrix type that safely encapsulates the 2N-1 elements to prevent invalid state manipulation.
Constructors: Provide user-friendly initialization interfaces accepting either a single 2N-1 array or separate column/row vectors.
SpMV Driver: Overload the * operator (or provide a matmul equivalent) to compute y = T xefficiently on the compressed data.
Prior Art
SciPy (scipy.linalg.toeplitz): The Python standard for initializing and interacting with these structures.
MATLAB (toeplitz): The gold standard for user-friendly matrix generation in engineering workflows
.Additional Information
Initial Scope: Support for standard real and complex kinds (sp, dp, qp) using fypp templating. The initial SpMV will use the direct O(N^2) memory-efficient loop.Future Extension: The architecture will allow for easy upgrading to Fast Fourier Transform (FFT) based O(N log N) multiplication in the future once the base types are merged.