scirs2_linalg/distrib_algorithms/
mod.rs

1//! Communication-avoiding distributed dense linear algebra algorithms.
2//!
3//! This module provides implementations of ScaLAPACK-style distributed algorithms
4//! for dense linear algebra, including:
5//!
6//! - **SUMMA**: Scalable Universal Matrix Multiply Algorithm with 2D block-cyclic layout
7//! - **CAQR**: Communication-Avoiding QR via Householder with tournament tree reduction
8//! - **Distributed Lanczos SVD**: Randomized Lanczos bidiagonalization with thick restart
9//!
10//! All algorithms operate in a *simulation mode*: a single process models all virtual
11//! processors in the grid, making these implementations useful for algorithm validation,
12//! cost-model analysis, and portability testing without requiring an actual MPI cluster.
13//!
14//! # References
15//!
16//! - Van De Geijn & Watts (1997): *SUMMA: Scalable Universal Matrix Multiply Algorithm*
17//! - Demmel et al. (2012): *Communication-optimal parallel and sequential QR and LU factorizations*
18//! - Larsen (1998): *Lanczos bidiagonalization with partial reorthogonalization*
19
20pub mod gemm;
21pub mod qr;
22pub mod svd;
23
24pub use gemm::{distributed_gemm_simulate, BlockCyclicMatrix, CommCost};
25pub use qr::{caqr_simulate, HouseholderReflector};
26pub use svd::{distributed_svd_simulate, thick_restart_lanczos, LanczosSvdConfig};
27
28use crate::error::LinalgResult;
29use scirs2_core::ndarray::Array2;
30
31/// Configuration for distributed linear algebra operations.
32///
33/// Controls block size and virtual processor grid dimensions used
34/// by SUMMA and CAQR simulations.
35#[derive(Debug, Clone)]
36pub struct DistribConfig {
37    /// Tile / block size (rows and columns) used for data partitioning.
38    pub block_size: usize,
39    /// Number of virtual processor rows in the 2-D process grid.
40    pub n_proc_rows: usize,
41    /// Number of virtual processor columns in the 2-D process grid.
42    pub n_proc_cols: usize,
43}
44
45impl Default for DistribConfig {
46    fn default() -> Self {
47        Self {
48            block_size: 64,
49            n_proc_rows: 2,
50            n_proc_cols: 2,
51        }
52    }
53}
54
55/// Trait for distributed dense linear algebra operations.
56///
57/// Implementors provide distributed GEMM, QR, and SVD that mirror the
58/// interface expected by ScaLAPACK-style driver routines.
59pub trait DistributedLinearAlgebra {
60    /// Distributed general matrix multiply: `C = A * B`.
61    ///
62    /// # Arguments
63    ///
64    /// * `a` - Left operand matrix (m × k)
65    /// * `b` - Right operand matrix (k × n)
66    /// * `config` - Distribution configuration
67    ///
68    /// # Returns
69    ///
70    /// Result matrix C (m × n)
71    fn distributed_gemm(
72        a: &Array2<f64>,
73        b: &Array2<f64>,
74        config: &DistribConfig,
75    ) -> LinalgResult<Array2<f64>>;
76
77    /// Distributed QR decomposition: `A = Q * R`.
78    ///
79    /// Uses communication-avoiding Householder QR with binary-tree tournament
80    /// reduction to achieve O(log P) communication rounds.
81    ///
82    /// # Returns
83    ///
84    /// Tuple `(Q, R)` where `Q` is orthogonal and `R` is upper triangular.
85    fn distributed_qr(
86        a: &Array2<f64>,
87        config: &DistribConfig,
88    ) -> LinalgResult<(Array2<f64>, Array2<f64>)>;
89
90    /// Distributed truncated SVD via Lanczos bidiagonalization.
91    ///
92    /// Returns the top-`k` singular triplets of `A`.
93    ///
94    /// # Returns
95    ///
96    /// Tuple `(U_k, sigma_k, V_k)` where `sigma_k` are the largest `k` singular
97    /// values in descending order.
98    fn distributed_svd(
99        a: &Array2<f64>,
100        k: usize,
101    ) -> LinalgResult<(Array2<f64>, Vec<f64>, Array2<f64>)>;
102}
103
104/// Concrete implementation that delegates to simulation functions in sub-modules.
105pub struct SimulatedDistributed;
106
107impl DistributedLinearAlgebra for SimulatedDistributed {
108    fn distributed_gemm(
109        a: &Array2<f64>,
110        b: &Array2<f64>,
111        config: &DistribConfig,
112    ) -> LinalgResult<Array2<f64>> {
113        distributed_gemm_simulate(a, b, config)
114    }
115
116    fn distributed_qr(
117        a: &Array2<f64>,
118        config: &DistribConfig,
119    ) -> LinalgResult<(Array2<f64>, Array2<f64>)> {
120        caqr_simulate(a, config)
121    }
122
123    fn distributed_svd(
124        a: &Array2<f64>,
125        k: usize,
126    ) -> LinalgResult<(Array2<f64>, Vec<f64>, Array2<f64>)> {
127        distributed_svd_simulate(a, k)
128    }
129}
scirs2_linalg/distrib_algorithms/mod.rs

scirs2_linalg/distrib_algorithms/
mod.rs
