Expand description
§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 (`from_triplets` returns a Result;
// unwrap the SparseMatrix before passing to the solver).
let matrix = SparseMatrix::from_triplets(
vec![(0, 0, 5.0), (0, 1, 1.0), (1, 0, 2.0), (1, 1, 7.0)],
2, 2
).expect("valid triplets");
// 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::Result;pub use error::SolverError;pub use matrix::Matrix;pub use matrix::SparseFormat;pub use matrix::SparseMatrix;pub use solver::BackwardPushSolver;pub use solver::ForwardPushSolver;pub use solver::HybridSolver;pub use solver::NeumannSolver;pub use solver::PartialSolution;pub use solver::SolverAlgorithm;pub use solver::SolverOptions;pub use solver::SolverResult;pub use types::ConvergenceMode;pub use types::EdgeId;pub use types::ErrorBounds;pub use types::NodeId;pub use types::NormType;pub use types::Precision;pub use types::SolverStats;pub use sublinear::sublinear_neumann::SublinearNeumannResult;pub use sublinear::sublinear_neumann::SublinearNeumannSolver;pub use sublinear::ComplexityBound;pub use sublinear::SublinearConfig;pub use sublinear::SublinearSolver;pub use simd_ops::axpy_simd;pub use simd_ops::dot_product_simd;pub use simd_ops::matrix_vector_multiply_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 complexity::Complexity;pub use complexity::ComplexityClass;pub use complexity::ComplexityIntrospect;pub use coherence::check_coherence_or_reject;pub use coherence::coherence_score;pub use coherence::approximate_spectral_radius;pub use coherence::delta_below_solve_threshold;pub use coherence::delta_inf_bound;pub use coherence::optimal_neumann_terms;pub use coherence::optimal_neumann_terms_with_rho;pub use coherence::CoherenceCache;pub use incremental::solve_on_change_sublinear;pub use incremental::solve_on_change_sublinear_auto;pub use incremental::solve_on_change_sublinear_auto_with_rho;pub use incremental::IncrementalConfig;pub use incremental::IncrementalSolver;pub use incremental::SolveOnChangeSublinearOp;pub use incremental::SparseDelta;pub use budget::BudgetExhausted;pub use budget::PlanBudget;pub use witness::verify_sparse_solution;pub use witness::VerifySparseSolutionOp;pub use witness::WitnessReport;pub use stream::event_stream_iter;pub use stream::EventStatus;pub use stream::EventStreamConfig;pub use stream::EventStreamOp;pub use stream::ProcessedEvent;pub use contrastive::contrastive_solve_on_change;pub use contrastive::contrastive_solve_on_change_sublinear;pub use contrastive::contrastive_solve_on_change_sublinear_auto;pub use contrastive::contrastive_solve_on_change_sublinear_auto_with_rho;pub use contrastive::find_anomalous_rows;pub use contrastive::find_anomalous_rows_in_subset;pub use contrastive::find_rows_above_threshold;pub use contrastive::AnomalyRow;pub use contrastive::ContrastiveSolveOnChangeOp;pub use contrastive::ContrastiveSolveOnChangeSublinearOp;pub use closure::closure_indices;pub use closure::ClosureIndicesOp;pub use entry::solve_single_entries_neumann;pub use entry::solve_single_entry_neumann;pub use entry::SolveSingleEntryNeumannOp;pub use temporal_nexus::core::ConsciousnessTask;pub use temporal_nexus::core::ContinuityMetrics;pub use temporal_nexus::core::ContractionMetrics;pub use temporal_nexus::core::IdentityContinuityTracker;pub use temporal_nexus::core::NanosecondScheduler;pub use temporal_nexus::core::StrangeLoopOperator;pub use temporal_nexus::core::TemporalConfig;pub use temporal_nexus::core::TemporalError;pub use temporal_nexus::core::TemporalResult;pub use temporal_nexus::core::TemporalWindow;pub use temporal_nexus::core::TscTimestamp;pub use temporal_nexus::core::WindowOverlapManager;
Modules§
- budget
PlanBudget— cumulative complexity-class + operation-count accumulator for chained solves.- closure
- Bounded-depth graph closure over a sparse matrix’s adjacency.
- coherence
- Coherence gate — refuse to spend polynomial-time work on a near-singular system whose residual signal-to-noise ratio is too low to produce a useful answer.
- complexity
- Complexity-class declarations for every public solver / sampler / analyser.
- contrastive
- Contrastive search — find the rows whose solution diverged most from a baseline. ADR-001 roadmap item #6.
- entry
- Single-entry sublinear Neumann solver.
- error
- Error types and handling for the sublinear solver.
- incremental
- Event-gated incremental solve — ADR-001 roadmap item #2.
- 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 - stream
- Streaming event iterator over the SubLinear orchestrator.
- 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.
- witness
- Sparse solve witness — per-entry residual audit for SubLinear orchestrator outputs.
Structs§
- Build
Info - Information about the current build configuration.
Constants§
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.