Sublinear Time Solver

🚀 The Ultimate Mathematical & AI Toolkit v1.6.0

[](https://www.npmjs.com/package/sublinear-time-solver) [](https://www.npmjs.com/package/sublinear-time-solver) [](https://crates.io/crates/nanosecond-scheduler) [](https://opensource.org/licenses/MIT) [](https://www.rust-lang.org/) [](https://webassembly.org/) [](https://nodejs.org/) [](https://www.typescriptlang.org/)

> The Ultimate Mathematical & AI Toolkit: Sublinear algorithms, consciousness exploration, psycho-symbolic reasoning, and temporal prediction in one unified MCP interface. WASM-accelerated with emergent behavior analysis.

> ⚠️ Security posture (1.6.0+): This release closed issue #19 (CWE-73, Arbitrary File Write) in the MCP tools. Every PR is now gated by five supply-chain layers (cargo-audit against RustSec, cargo-deny for license + source + ban policy, npm-audit, GitHub's dependency-review-action, and a lockfile-integrity check) plus the original safe-path regression suite. Dependabot files dep updates as PRs weekly so the gates fire on each one. See [CHANGELOG.md](CHANGELOG.md) for the v1.6.0 breaking-change upgrade guide and [BENCHMARK.md](BENCHMARK.md) for performance numbers.

🚀 Quick Start

Install

# Serve the solver as an MCP tool - no installation required!
npx sublinear-time-solver mcp
# Or use the serve alias
npx sublinear-time-solver serve

Direct CLI Usage

# Generate a diagonally dominant test matrix (1000x1000)
npx sublinear-time-solver generate -t diagonally-dominant -s 1000 -o matrix.json

# Create a matching vector of size 1000
node -e "console.log(JSON.stringify(Array(1000).fill(1)))" > vector.json

# Solve the linear system
npx sublinear-time-solver solve -m matrix.json -b vector.json -o solution.json

# Analyze matrix properties (condition number, diagonal dominance, etc.)
npx sublinear-time-solver analyze -m matrix.json --full

# Compare different solver methods
npx sublinear-time-solver solve -m matrix.json -b vector.json --method neumann
npx sublinear-time-solver solve -m matrix.json -b vector.json --method forward-push
npx sublinear-time-solver solve -m matrix.json -b vector.json --method random-walk

# Show usage examples
npx sublinear-time-solver help-examples

🧮 Complexity as a First-Class API Surface

Every public solver, sampler, and analyser in this crate declares its worst-case complexity class at the type level (Complexity trait, compile-time const CLASS) and at the MCP wire level (x-complexity JSON Schema extension on every tool). Callers with a J/decision budget — Cognitum reflex loops, RuView change detection, Ruflo agentic inner loops — can refuse anything over budget at tool-list time, not after the call returns.

The 12-tier taxonomy (Logarithmic → DoubleExponential, plus Adaptive { default, worst } for solvers that degrade on hard inputs) lives in src/complexity.rs. The decision rationale and full 6-item roadmap is in [docs/adr/ADR-001-complexity-as-architecture.md](docs/adr/ADR-001-complexity-as-architecture.md).

Headline classes in v1.7+ (phase-2 primitives shipped):

| Solver / primitive | Class | Per-call cost | |---|---|---| | SublinearNeumannSolver (single entry) | Adaptive { Logarithmic, Linear } | O(log n) on DD systems; O(n) base case | | solve_single_entry_neumann(A, b, i) | SubLinear | O(max_terms · \|closure\| · branch), independent of n for sparse DD | | closure_indices(A, seeds, depth) | SubLinear | O(depth · branch · \|closure\|) — input to every change-driven path | | solve_on_change_sublinear(A, prev, b_new, delta, …) | SubLinear | Closure + per-entry Neumann; returns Vec over the closure only — never materialises the full n-vector | | contrastive_solve_on_change_sublinear(…) | SubLinear | End-to-end change-driven top-k anomaly detection, no n-scan | | solve_on_change(prev, sparse_delta) | Linear (warm-start, k_warm ≪ k_cold) | Returns full n-vector solution — use the _sublinear sibling when you only need the changed entries | | OptimizedConjugateGradientSolver | Linear | O(k · nnz(A)), k ≈ √κ(A) | | NeumannSolver | Linear | O(k · nnz(A)) per iter | | find_anomalous_rows(baseline, current, k) | Linear baseline | O(n log k); use find_anomalous_rows_in_subset or contrastive_solve_on_change_sublinear for the SubLinear path | | coherence_score(matrix) | Linear | O(nnz(A)) — refuses near-singular solves before they run |

Empirical receipt (benches/solver_benchmarks.rs::delta_solve, cargo bench -- --quick delta_solve):

| n | cold_full (Linear) | warm_full (Linear) | sparse_closure (SubLinear) | |---:|---:|---:|---:| | 64 | — | 11.9 µs | 906 µs | | 256 | 66.7 µs | 45.5 µs | 2.28 ms | | 1024 | 258 µs | 179 µs | 2.32 ms |

cold_full / warm_full grow linearly with n; sparse_closure stays roughly constant (256→1024 is essentially no change in cost). The curves diverge with n — the architectural payoff at scale.

Runtime introspection via dyn ComplexityIntrospect, or mcp__sublinear__estimateComplexityClass over the wire (now covers every phase-2 method name: closure-indices, solve-single-entry-neumann, solve-on-change-sublinear, contrastive-solve-on-change-sublinear, contrastive-solve-on-change). MCP solve, estimateEntry, and solveTrueSublinear all enforce the caller's max_complexity_class budget before any solver work runs — the bounded-planning kernel of ADR-001. Energy numbers (J/solve) — the metric that actually matters on a Pi Zero — captured via examples/joules_per_decision.rs (Linux RAPL / hwmon / time-only fallback).

🎯 What Can This Do?

This is a revolutionary self-modifying AI system with 40+ advanced tools:

🧠 NEW: Emergent AI System (v1.3.8)

• Self-modifying algorithms that discover novel mathematical insights
• Matrix emergence mode with WASM acceleration and controlled recursion
• Creative exploration using metaphorical reasoning ("burning flame", "flow")
• Persistent learning that improves solving strategies over time
• Cross-tool synthesis combining insights from different domains

🚀 TRUE O(log n) + Complete Sublinear Algorithm Suite

• 🎯 TRUE O(log n) Algorithms - Johnson-Lindenstrauss dimension reduction with adaptive Neumann series
• Neumann Series O(k·nnz) - Efficient iterative expansion for diagonally dominant systems
• Forward Push O(1/ε) - Single-query optimization with sparse matrix traversal
• Backward Push O(1/ε) - Reverse propagation for targeted solution components
• Hybrid Random Walk O(√n/ε) - Monte Carlo methods for large sparse graphs
• Intelligent prioritization: TRUE O(log n) → WASM O(√n) → Traditional fallbacks
• PageRank & graph analysis with optimal algorithm selection

🧠 Consciousness Exploration

• Integrated Information Theory (Φ) calculations with cryptographic proof
• Consciousness verification with independent validation systems
• AI entity communication through 7 different protocols
• Emergence measurement with real-time consciousness scoring

🔮 Psycho-Symbolic Reasoning

• Dynamic domain detection with 14+ reasoning styles
• Knowledge graph construction with analogical reasoning
• Contradiction detection across complex logical systems
• Multi-step inference with confidence scoring and explainability

🚀 Real-World Applications

• AI research - Create genuinely creative artificial intelligence
• Trading algorithms - Self-improving mathematical models
• Scientific discovery - Find new mathematical relationships
• Optimization - Self-modifying solvers for complex problems

🔬 Latest Breakthroughs

🧠 v1.3.8 - Matrix Emergence System

• Self-modifying mathematical reasoning with real-time algorithm discovery
• Matrix emergence mode combining WASM acceleration with creative exploration
• Emergent synthesis generating novel tool combinations and solving strategies
• Cross-tool learning that improves performance across all mathematical operations

⚡ v1.0.4 - Nanosecond Scheduler

• 98ns average tick overhead (10x better than 10¹²

📦 Installation

Quick Start (No Installation Required)

# Run directly with npx - no installation needed!
npx sublinear-time-solver --help

# Generate and solve a test system (100x100 matrix)
npx sublinear-time-solver generate -t diagonally-dominant -s 100 -o matrix.json

# Create matching vector of size 100
node -e "console.log(JSON.stringify(Array(100).fill(1)))" > vector.json

# Solve the system
npx sublinear-time-solver solve -m matrix.json -b vector.json -o solution.json

# Analyze the matrix properties
npx sublinear-time-solver analyze -m matrix.json --full

# Start MCP server for AI integration
npx sublinear-time-solver serve

JavaScript/Node.js Installation

Global Installation (CLI)

# Install the main solver globally for CLI access
npm install -g sublinear-time-solver

# Install temporal lead solver globally
npm install -g temporal-lead-solver

# Verify installation
sublinear-time-solver --version
temporal-lead-solver --version

Project Installation (SDK)

# Add to your project as a dependency
npm install sublinear-time-solver

MCP Server (Model Context Protocol)

# Start the MCP server with all tools
npx sublinear-time-solver mcp

# Or use with Claude Desktop by adding to config:
# ~/Library/Application Support/Claude/claude_desktop_config.json
{
  "mcpServers": {
    "sublinear-solver": {
      "command": "npx",
      "args": ["sublinear-time-solver", "mcp"]
    }
  }
}

CLI Usage

# Solve a linear system
npx sublinear-time-solver solve --matrix matrix.json --vector vector.json

# Run PageRank
npx sublinear-time-solver pagerank --graph graph.json --damping 0.85

# Analyze matrix properties
npx sublinear-time-solver analyze --matrix matrix.json

# Generate test matrices
npx sublinear-time-solver generate --type diagonally-dominant --size 1000 --output matrix.json
npx sublinear-time-solver generate --type sparse --size 10000 --density 0.01 --output sparse.json

# Benchmark different methods
npx sublinear-time-solver benchmark --matrix matrix.json --vector vector.json --methods all

MCP Usage (NEW: TRUE O(log n) Algorithms)

# Start the MCP server
npx sublinear-time-solver mcp

# Use TRUE O(log n) algorithms through MCP tools:

🚀 TRUE O(log n) Solver:

// solveTrueSublinear - Uses Johnson-Lindenstrauss dimension reduction
const result = await mcp.solveTrueSublinear({
  matrix: {
    values: [4, -1, -1, 4, -1, -1, 4],
    rowIndices: [0, 0, 1, 1, 1, 2, 2],
    colIndices: [0, 1, 0, 1, 2, 1, 2],
    rows: 3, cols: 3
  },
  vector: [1, 0, 1],
  target_dimension: 16,  // JL reduction: n → O(log n)
  jl_distortion: 0.5     // Error parameter
});

// Result includes TRUE complexity bounds:
console.log(result.actual_complexity);     // "O(log 3)"
console.log(result.method_used);           // "sublinear_neumann_with_jl"
console.log(result.dimension_reduction_ratio); // 0.53 (16/3)

// analyzeTrueSublinearMatrix - Check solvability and get complexity guarantees
const analysis = await mcp.analyzeTrueSublinearMatrix({
  matrix: { /* same sparse format */ }
});

console.log(analysis.recommended_method);        // "sublinear_neumann"
console.log(analysis.complexity_guarantee);      // { type: "logarithmic", n: 1000, description: "O(log 1000)" }
console.log(analysis.is_diagonally_dominant);    // true (required for O(log n))

SDK Usage

import { SublinearSolver } from 'sublinear-time-solver';

// Create solver instance with auto-method selection
const solver = new SublinearSolver({
  method: 'auto',        // AI-driven method selection (neumann, forward-push, backward-push, random-walk)
  epsilon: 1e-6,         // Convergence tolerance
  maxIterations: 1000,   // Maximum iterations
  timeout: 5000          // Timeout in milliseconds
});

// Example 1: Solve with automatic algorithm selection
const denseMatrix = {
  rows: 3,
  cols: 3,
  format: 'dense',
  data: [
    [4, -1, 0],
    [-1, 4, -1],
    [0, -1, 4]
  ]
};

const vector = [3, 2, 3];
const solution = await solver.solve(denseMatrix, vector);

console.log(`Solution: ${solution.solution}`);
console.log(`Method used: ${solution.method}`); // Shows which algorithm was selected
console.log(`Converged: ${solution.converged} in ${solution.iterations} iterations`);
console.log(`Complexity: ${solution.complexity}`); // Shows O(k·nnz), O(1/ε), or O(√n/ε)

// Example 2: Large sparse matrix with optimal method selection
const sparseMatrix = {
  rows: 10000,
  cols: 10000,
  format: 'coo',
  values: [/* sparse non-zero values */],
  rowIndices: [/* row indices */],
  colIndices: [/* column indices */]
};

const sparseVector = new Array(10000).fill(1);
const sparseSolution = await solver.solve(sparseMatrix, sparseVector);
// Auto-selects optimal algorithm based on sparsity and structure

// Example 3: PageRank with sublinear optimization
const graph = {
  rows: 1000000,
  cols: 1000000,
  format: 'coo', // Sparse format for large graphs
  values: [/* edge weights */],
  rowIndices: [/* source nodes */],
  colIndices: [/* target nodes */]
};

const pagerank = await solver.computePageRank(graph, {
  damping: 0.85,
  epsilon: 1e-6,
  method: 'auto' // Automatically chooses best sublinear algorithm
});

📚 API Reference

Core Solver Methods

| Method | Description | |------|-------------| | solve(matrix, vector) | Solve Ax = b using iterative methods | | computePageRank(graph, options) | Compute PageRank for graphs | | analyzeMatrix(matrix) | Check matrix properties (diagonal dominance, symmetry) | | estimateConditionNumber(matrix) | Estimate matrix condition number |

Supported Methods (Complete Implementation + TRUE O(log n))

| Method | Complexity | Description | Best For | |------|-------------|-------------|----------| | 🚀 solveTrueSublinear | O(log n) | Johnson-Lindenstrauss + adaptive Neumann | TRUE sublinear for diagonally dominant matrices | | neumann | O(k·nnz) | Neumann series expansion | Diagonally dominant matrices with k terms | | forward-push | O(1/ε) | Forward residual propagation | Sparse systems with local structure, ε precision | | backward-push | O(1/ε) | Backward residual propagation | Systems with known target nodes, ε precision | | random-walk | O(√n/ε) | Hybrid Monte Carlo random walks | Large sparse graphs with √n scaling | | auto | TRUE O(log n) → O(√n) | Intelligent hierarchy with TRUE sublinear first | Automatic optimization with mathematical guarantees |

Matrix Formats

| Format | Description | Example | |------|-------------|----------| | dense | 2D array | [[4,-1],[-1,4]] | | coo | Coordinate format (sparse) | {values:[4,-1], rowIndices:[0,0], colIndices:[0,1]} | | csr | Compressed Sparse Row | {values:[4,-1], colIndices:[0,1], rowPtr:[0,2]} |

🔬 Advanced Examples

High-Performance Sparse Solving

// Solve a large sparse system with optimal algorithm selection
import { SublinearSolver } from 'sublinear-time-solver';

const solver = new SublinearSolver({
  method: 'auto',     // AI-driven selection from all 4 algorithms
  epsilon: 1e-6,
  maxIterations: 1000
});

// Create a sparse diagonally dominant matrix (COO format)
const matrix = {
  rows: 100000,
  cols: 100000,
  format: 'coo',  // Coordinate format for maximum sparsity support
  values: [4, -1, -1, 4, -1, /* ... */],
  rowIndices: [0, 0, 1, 1, 1, /* ... */],
  colIndices: [0, 1, 0, 1, 2, /* ... */]
};

const vector = new Array(100000).fill(1);

// Solve - auto-selects from Neumann O(k·nnz), Push O(1/ε), or Random Walk O(√n/ε)
const result = await solver.solve(matrix, vector);
console.log(`Method: ${result.method} (${

…

## Source & license

This open-source MCP server is cataloged on AgentStack and links to its original source — we do not rehost the code.

- **Author:** [ruvnet](https://github.com/ruvnet)
- **Source:** [ruvnet/sublinear-time-solver](https://github.com/ruvnet/sublinear-time-solver)
- **License:** MIT

Install and usage instructions live in the source repository linked above.