sublinear_solver/sublinear/
mod.rs

1//! True sublinear-time algorithms for linear system solving
2//!
3//! This module implements mathematically rigorous sublinear algorithms
4//! that achieve O(log n) complexity under specific conditions.
5
6pub mod dimension_reduction;
7pub mod spectral_sparsification;
8pub mod sublinear_neumann;
9pub mod johnson_lindenstrauss;
10pub mod sketching;
11pub mod fast_sampling;
12
13use crate::matrix::Matrix;
14use crate::types::Precision;
15use crate::error::{SolverError, Result};
16
17/// Configuration for sublinear algorithms
18#[derive(Debug, Clone)]
19pub struct SublinearConfig {
20    /// Target dimension after dimension reduction
21    pub target_dimension: usize,
22    /// Sparsification parameter (0 < eps < 1)
23    pub sparsification_eps: Precision,
24    /// Johnson-Lindenstrauss distortion parameter
25    pub jl_distortion: Precision,
26    /// Sampling probability for sketching
27    pub sampling_probability: Precision,
28    /// Maximum recursion depth
29    pub max_recursion_depth: usize,
30    /// Base case threshold for recursion
31    pub base_case_threshold: usize,
32}
33
34impl Default for SublinearConfig {
35    fn default() -> Self {
36        Self {
37            target_dimension: 64,
38            sparsification_eps: 0.1,
39            jl_distortion: 0.5,
40            sampling_probability: 0.01,
41            max_recursion_depth: 10,
42            base_case_threshold: 100,
43        }
44    }
45}
46
47/// Sublinear complexity bounds for different matrix types
48#[derive(Debug, Clone)]
49pub enum ComplexityBound {
50    /// O(log n) for diagonally dominant matrices
51    Logarithmic(usize),
52    /// O(sqrt(n)) for well-conditioned matrices
53    SquareRoot(usize),
54    /// O(n^eps) for general sparse matrices
55    Sublinear { n: usize, eps: Precision },
56}
57
58/// Trait for algorithms that achieve true sublinear complexity
59pub trait SublinearSolver {
60    /// Verify that the matrix satisfies conditions for sublinear complexity
61    fn verify_sublinear_conditions(&self, matrix: &dyn Matrix) -> Result<ComplexityBound>;
62
63    /// Solve with guaranteed sublinear complexity
64    fn solve_sublinear(
65        &self,
66        matrix: &dyn Matrix,
67        b: &[Precision],
68        config: &SublinearConfig,
69    ) -> Result<Vec<Precision>>;
70
71    /// Get the actual complexity bound achieved
72    fn complexity_bound(&self) -> ComplexityBound;
73}
sublinear_solver/sublinear/mod.rs

sublinear_solver/sublinear/
mod.rs
