Crate sublinear_solver 

Sublinear-Time Solver for Asymmetric Diagonally Dominant Systems

This crate implements cutting-edge sublinear-time algorithms for solving linear systems of the form Ax = b where A is an asymmetric diagonally dominant matrix.

Key Features

• Sublinear Time Complexity: O(log^k n) for well-conditioned systems
• Multiple Algorithms: Neumann series, forward/backward push, hybrid random-walk
• Incremental Updates: Fast cost propagation for dynamic systems
• WASM Compatible: Cross-platform deployment via WebAssembly
• High Performance: SIMD optimization and cache-friendly data structures

Quick Start

use sublinear_solver::{SparseMatrix, NeumannSolver, SolverAlgorithm, SolverOptions};

// Create a diagonally dominant matrix
let matrix = SparseMatrix::from_triplets(
    vec![(0, 0, 5.0), (0, 1, 1.0), (1, 0, 2.0), (1, 1, 7.0)],
    2, 2
);

// Set up the right-hand side
let b = vec![6.0, 9.0];

// Solve using Neumann series
let solver = NeumannSolver::new(16, 1e-8);
let result = solver.solve(&matrix, &b, &SolverOptions::default())?;

println!("Solution: {:?}", result.solution);
println!("Converged in {} iterations", result.iterations);

Algorithms

Neumann Series Solver

Uses the matrix series expansion (I - M)^(-1) = Σ M^k for solving systems. Optimal for well-conditioned diagonally dominant matrices.

Forward/Backward Push

Graph-based algorithms that propagate residuals locally, achieving sublinear complexity for sparse systems with good graph structure.

Hybrid Random-Walk

Combines stochastic estimation with deterministic push methods for robust performance across different problem types.

WebAssembly Support

Enable the wasm feature for browser and Node.js deployment:

[dependencies]
sublinear-solver = { version = "0.1", features = ["wasm"] }

Re-exports

pub use error::SolverError;

pub use error::Result;

pub use matrix::Matrix;

pub use matrix::SparseMatrix;

pub use matrix::SparseFormat;

pub use solver::SolverAlgorithm;

pub use solver::SolverOptions;

pub use solver::SolverResult;

pub use solver::PartialSolution;

pub use solver::NeumannSolver;

pub use solver::ForwardPushSolver;

pub use solver::BackwardPushSolver;

pub use solver::HybridSolver;

pub use types::NodeId;

pub use types::EdgeId;

pub use types::Precision;

pub use types::ConvergenceMode;

pub use types::NormType;

pub use types::ErrorBounds;

pub use types::SolverStats;

pub use sublinear::SublinearConfig;

pub use sublinear::SublinearSolver;

pub use sublinear::ComplexityBound;

pub use sublinear::sublinear_neumann::SublinearNeumannSolver;

pub use sublinear::sublinear_neumann::SublinearNeumannResult;

pub use simd_ops::matrix_vector_multiply_simd;

pub use simd_ops::dot_product_simd;

pub use simd_ops::axpy_simd;

pub use simd_ops::parallel_matrix_vector_multiply;

pub use optimized_solver::OptimizedConjugateGradientSolver;

pub use optimized_solver::OptimizedSparseMatrix;

pub use math_wasm::Matrix as WasmMatrix;

pub use math_wasm::Vector as WasmVector;

pub use solver_core::ConjugateGradientSolver;

pub use solver_core::SolverConfig as WasmSolverConfig;

pub use temporal_nexus::core::NanosecondScheduler;

pub use temporal_nexus::core::TemporalConfig;

pub use temporal_nexus::core::ConsciousnessTask;

pub use temporal_nexus::core::TemporalResult;

pub use temporal_nexus::core::TemporalError;

pub use temporal_nexus::core::TscTimestamp;

pub use temporal_nexus::core::TemporalWindow;

pub use temporal_nexus::core::WindowOverlapManager;

pub use temporal_nexus::core::StrangeLoopOperator;

pub use temporal_nexus::core::ContractionMetrics;

pub use temporal_nexus::core::IdentityContinuityTracker;

pub use temporal_nexus::core::ContinuityMetrics;

Modules

error

Error types and handling for the sublinear solver.

math_wasm

matrix

Matrix operations and data structures for sparse linear algebra.

optimized_solver

High-performance optimized solver implementations.

simd_ops

SIMD-accelerated linear algebra operations for high-performance computing.

solver

Sublinear-time solver algorithms for asymmetric diagonally dominant systems.

solver_core

sublinear

True sublinear-time algorithms for linear system solving

temporal_nexus

Temporal Nexus - Nanosecond Scheduler for Temporal Consciousness Temporal Nexus - Nanosecond Precision Consciousness Framework

types

Common types and type aliases used throughout the solver.

Structs

BuildInfo

Information about the current build configuration.

Constants

DESCRIPTION

VERSION

Functions

build_info

Get information about the current solver build.

has_simd_support

Check if the current build supports SIMD optimizations.

init

Initialize the solver library with default logging configuration.