Module scalable 

Scalable algorithms for tall-and-skinny or short-and-fat matrices

This module implements cutting-edge scalable algorithms specifically optimized for rectangular matrices with extreme aspect ratios, which are ubiquitous in modern machine learning, data science, and scientific computing applications:

• Tall-and-Skinny QR (TSQR): Communication-optimal QR for matrices where m >> n
• LQ decomposition: Efficient factorization for short-and-fat matrices (m << n)
• Adaptive algorithms: Smart selection based on matrix aspect ratio analysis
• Blocked operations: Memory-efficient algorithms for massive matrices
• Randomized sketching: Probabilistic dimensionality reduction techniques

Key Advantages

• Communication optimality: Minimal data movement for distributed computing
• Memory efficiency: Blocked algorithms prevent memory bottlenecks
• Adaptive selection: Automatic algorithm choice based on matrix properties
• Numerical stability: Maintained accuracy even for extreme aspect ratios
• Scalability: Designed for matrices with millions of rows/columns

Mathematical Foundation

For tall-and-skinny matrices A ∈ ℝ^(m×n) where m >> n:

• TSQR reduces communication complexity from O(mn²) to O(n²)
• Tree-based reduction enables parallel and distributed computation
• Maintains numerical stability equivalent to standard Householder QR

For short-and-fat matrices A ∈ ℝ^(m×n) where m << n:

• LQ decomposition: A = LQ where L is lower triangular, Q is orthogonal
• Efficient for overdetermined systems and least-norm problems

References

• Demmel, J., et al. (2012). “Communication-optimal parallel and sequential QR and LU factorizations”
• Grigori, L., et al. (2011). “A class of communication-avoiding algorithms for solving general dense linear systems”
• Martinsson, P. G. (2020). “Randomized methods for matrix computations”

Structs

AdaptiveResult

Result type for adaptive decomposition algorithms

PerformanceMetrics

Performance metrics for algorithm execution

ScalableConfig

Configuration for scalable algorithms

Enums

AspectRatio

Matrix aspect ratio classification

Functions

adaptive_decomposition

Adaptive algorithm selection based on matrix aspect ratio

blocked_matmul

Blocked matrix multiplication optimized for extreme aspect ratios

classify_aspect_ratio

Determine the aspect ratio type of a matrix

lq_decomposition

LQ decomposition optimized for short-and-fat matrices

randomized_svd

Randomized SVD for low-rank approximation

tsqr

Tall-and-Skinny QR (TSQR) decomposition