Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
matrix_example.C File Reference

Comprehensive example demonstrating sparse matrices and vectors in Aleph-w. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <memory>
#include <tclap/CmdLine.h>
#include <al-vector.H>
#include <al-matrix.H>
#include <al-domain.H>
#include <htlist.H>
#include <ahFunctional.H>
Include dependency graph for matrix_example.C:

Go to the source code of this file.

Functions

void print_section (const string &title)
 
void print_subsection (const string &title)
 
void demo_sparse_vector ()
 
void demo_string_indexed_vector ()
 
void demo_sparse_matrix ()
 
void demo_named_matrix ()
 
void demo_vector_arithmetic ()
 
void demo_adjacency_matrix ()
 
void demo_epsilon ()
 
void demo_initializer_list ()
 
void demo_transpose ()
 
void demo_identity ()
 
void demo_matrix_vector_mult ()
 
void demo_matrix_mult ()
 
void demo_outer_product ()
 
void demo_comparison ()
 
void demo_matrix_arithmetic ()
 
void demo_row_col_operations ()
 
void demo_linear_system ()
 
int main (int argc, char *argv[])
 

Detailed Description

Comprehensive example demonstrating sparse matrices and vectors in Aleph-w.

This program demonstrates sparse Matrix and Vector classes from al-matrix.H and al-vector.H. Unlike dense matrices (which store all elements), sparse matrices only store non-zero entries, making them memory-efficient for sparse data. Additionally, they support domain-based indexing, allowing rows and columns to be indexed by any type (not just integers).

Sparse vs Dense Matrices

Dense Matrix

  • Stores ALL elements (even zeros)
  • Memory: O(rows × cols)
  • Access: O(1) - direct indexing
  • Best for: Dense data, small matrices

Sparse Matrix (This Example)

  • Stores ONLY non-zero entries
  • Memory: O(nonzero_entries)
  • Access: O(log n) - search in sparse structure
  • Best for: Sparse data, large matrices with few non-zeros

When to Use Sparse?

Use sparse when:

  • Sparsity > 90%: Most entries are zero
  • Large matrices: Memory savings significant
  • Domain-based indexing: Need named rows/columns

Example: 1000×1000 matrix with only 1000 non-zeros:

  • Dense: 1,000,000 elements = 8 MB (for doubles)
  • Sparse: 1,000 elements = 8 KB (huge savings!)

Key Features Demonstrated

Sparse Storage

  • Efficient storage: Only non-zero entries stored
  • Automatic cleanup: Near-zero entries removed (epsilon tolerance)
  • Memory efficient: O(nonzeros) instead of O(rows×cols)
  • Flexible: Can handle very large matrices

Domain-Based Indexing

Unlike traditional matrices (indexed 0..n-1), Aleph-w matrices support:

  • String indices: matrix["row_name"]["col_name"]
  • Custom types: Any comparable type as index
  • Named dimensions: Rows/columns have meaningful names

Example:

Matrix<string, string, double> sales(products, stores);
sales.set_entry("Laptop", "BOG", 150);
sales.set_entry("Phone", "MED", 450);

Operations Demonstrated

  • Element access: get_entry(), set_entry()
  • Arithmetic: +, -, +=, -= for matrices/vectors
  • Scalar operations: mult_by_scalar(), scalar * matrix
  • Row/column extraction: get_row_vector(), get_col_vector()
  • Row/column setting: set_vector_as_row(), set_vector_as_col()
  • Transposition: transpose()
  • Identity matrix: identity() (for square matrices)
  • Matrix multiplication: vector_matrix_mult(), matrix_vector_mult()
  • Matrix-vector multiplication: operator*, mult_matrix_vector_sparse(), mult_matrix_vector_dot_product(), mult_matrix_vector_linear_comb()
  • Vector-matrix multiplication: operator*, mult_vector_matrix_linear_comb()
  • Outer product: outer_product(v1, v2)
  • Comparison: ==, !=, equal_to() (with epsilon tolerance)
  • Initializer list construction: Direct matrix initialization
  • Conversion: to_rowlist(), to_collist(), to_str()

Applications

Scientific Computing

  • Linear systems: Sparse linear algebra (demonstrated in demo_linear_system)
  • Finite element methods: Sparse stiffness matrices
  • Graph algorithms: Adjacency matrices (demonstrated in demo_adjacency_matrix)

Data Analysis

  • Feature matrices: Machine learning (many zeros)
  • Transaction data: User-item matrices (sparse)
  • Time series: Sparse temporal data

Business Applications

  • Sales data: Products × Stores (demonstrated in demo_named_matrix)
  • Resource allocation: Resources × Tasks
  • Financial modeling: Instruments × Time periods

Complexity

Operation Dense Sparse Notes
Storage O(n²) O(nnz) Sparse wins for sparse data
Access O(1) O(1) avg Hash-based storage
Addition O(n²) O(nnz) Sparse much faster
M×v mult O(n²) O(nnz) Sparse iteration available
M×M mult O(n³) O(nnz₁×nnz₂) Depends on sparsity

Demos Included

  1. Sparse Vector Basics - Vector creation and element access
  2. String-Indexed Vectors - Domain-based indexing with strings
  3. Sparse Matrix Basics - Matrix creation and storage
  4. Named Row/Column Matrix - Real-world sales data example
  5. Vector Arithmetic - Addition, subtraction, scalar ops
  6. Graph Adjacency Matrix - Practical graph representation
  7. Epsilon Tolerance - Near-zero handling
  8. Initializer List Construction - Direct matrix initialization
  9. Matrix Transpose - Row/column swapping
  10. Identity Matrix - Creating identity for square matrices
  11. Matrix-Vector Multiplication - Multiple methods compared
  12. Matrix-Matrix Multiplication - Two approaches demonstrated
  13. Outer Product - Vector outer product
  14. Matrix Comparison - Equality with epsilon tolerance
  15. Matrix Arithmetic - Full arithmetic operations
  16. Row/Column Operations - Extract/set rows and columns
  17. Linear System Example - Practical Ax=b verification

Usage

# Run all matrix demonstrations
./matrix_example
See also
al-matrix.H Sparse Matrix class
al-vector.H Sparse Vector class
al-domain.H Domain-based indexing
Author
Leandro Rabindranath León
Date
2024

Definition in file matrix_example.C.

Function Documentation

◆ demo_adjacency_matrix()

◆ demo_comparison()

void demo_comparison ( )

Definition at line 851 of file matrix_example.C.

References Aleph::DynList< T >::insert(), Aleph::maps(), print_section(), and print_subsection().

Referenced by main().

◆ demo_epsilon()

◆ demo_identity()

void demo_identity ( )

Definition at line 638 of file matrix_example.C.

References Aleph::DynList< T >::insert(), Aleph::maps(), and print_section().

Referenced by main().

◆ demo_initializer_list()

void demo_initializer_list ( )

Definition at line 560 of file matrix_example.C.

References Aleph::DynList< T >::insert(), Aleph::maps(), print_section(), and print_subsection().

Referenced by main().

◆ demo_linear_system()

◆ demo_matrix_arithmetic()

◆ demo_matrix_mult()

void demo_matrix_mult ( )

Definition at line 752 of file matrix_example.C.

References Aleph::DynList< T >::insert(), Aleph::maps(), and print_section().

Referenced by main().

◆ demo_matrix_vector_mult()

◆ demo_named_matrix()

void demo_named_matrix ( )

◆ demo_outer_product()

void demo_outer_product ( )

◆ demo_row_col_operations()

◆ demo_sparse_matrix()

◆ demo_sparse_vector()

◆ demo_string_indexed_vector()

◆ demo_transpose()

◆ demo_vector_arithmetic()

◆ main()

◆ print_section()

◆ print_subsection()