Mathematical Reference

Mathematical and Algorithmic Documentation for Phasic

Version: 1.0 Date: 2026-04-09 Status: All 27 content files complete. Converted to Quarto book with native cross-references.

Reading Guide

This Supplementary Online Material (SOM) provides exhaustive mathematical and algorithmic documentation for every algorithm in the phasic library. Each file contains formal definitions, theorems with proofs, algorithm pseudocode with correspondence tables, complexity analysis, and correctness arguments.

How to read: Files are numbered 01–27. A file may only reference files with a lower number. The prerequisites listed in each file’s Introduction section give the minimal reading order. For a complete sequential reading, proceed in numerical order.

Notation: All notation follows docs/notation_standard.md. The Symbol Quick Reference (Section 12 of that document) is the master symbol table.

Relationship to other documentation: The SOM formalizes and proves; it does not duplicate API documentation (docs/pages/), tutorials, or how-to guides. Implementation Notes sections bridge the SOM to the codebase.

Document dependency DAG

01 Preliminaries
 ├── 02 Graph Representation
 │    ├── 03 Numerical Primitives
 │    ├── 04 SCC and Topological Sort
 │    │    ├── 05 Graph Normalization
 │    │    │    ├── 06 Graph Elimination
 │    │    │    │    ├── 07 Reward Transformation
 │    │    │    │    ├── 10 Symbolic Graph Elimination ← 09
 │    │    │    │    ├── 11 Trace System ← 09
 │    │    │    │    │    ├── 12 Graph Hashing
 │    │    │    │    │    └── 13 SCC Trace Stitching ← 04
 │    │    │    │    └── 14 Distribution Computation
 │    │    │    │         ├── 15 Moment Computation
 │    │    │    │         ├── 16 PDF Gradients
 │    │    │    │         └── 17 Sampling
 │    │    │    └── 08 State Space Construction
 │    │    └── 09 Symbolic Expressions
 │    ├── 23 State Indexing
 │    └── 24 Hex Grid
 ├── 18 SVGD ← 14, 15
 ├── 19 MCMC ← 14, 15
 ├── 20 BFFG ← 17
 ├── 21 Method of Moments ← 15
 ├── 22 Probability Matching ← 14
 ├── 25 JAX Integration ← 09, 11, 14
 ├── 26 Graph Builder ← 11, 14, 15
 └── 27 Van Loan Equivalence ← 06, 14, 15

Global Algorithm Registry

Algorithm Title Source function(s)
Algorithm 3.1 AVL Find-or-Insert ptd_avl_tree_find_or_insert
Algorithm 3.2 Graph Validation ptd_validate_graph
Algorithm 3.3 Graph Clone ptd_clone_graph
Algorithm 4.1 Kahan Summation kahan_init, kahan_add, kahan_result
Algorithm 4.2 Log-Space Weight Evaluation ptd_graph_update_weights (log mode)
Algorithm 5.1 Tarjan’s SCC Detection ptd_find_strongly_connected_components
Algorithm 5.2 Topological Sort of Condensation DAG ptd_directed_graph_topological_sort
Algorithm 6.1 Continuous Graph Normalization ptd_normalize_graph
Algorithm 6.2 Discrete Graph Normalization ptd_dph_normalize_graph
Algorithm 7.1 Vertex Elimination (Single Vertex) ptd_graph_ex_absorbation_time_comp_graph
Algorithm 7.2 Full Graph Elimination ptd_graph_ex_absorbation_time_comp_graph
Algorithm 7.3 Moment Computation via Elimination Commands ptd_expected_waiting_time
Algorithm 8.1 Reward Transformation ptd_graph_reward_transform
Algorithm 10.1 GenerateStateSpace ptd_find_or_create_vertex
Algorithm 11.1 Expression Evaluation ptd_expr_evaluate
Algorithm 12.1 Symbolic Graph Elimination phasic_symbolic.c
Algorithm 12.2 Symbolic Graph Instantiation phasic_symbolic.c
Algorithm 13.1 Trace Recording record_elimination_trace
Algorithm 13.2 Trace Evaluation evaluate_trace
Algorithm 14.1 Graph Content Hash ptd_hash_graph
Algorithm 15.1 SCC-Based Trace Decomposition and Stitching hierarchical_trace_cache.py
Algorithm 16.1 DPH Forward Step ptd_dph_probability_distribution_step
Algorithm 16.2 CPH PDF via Uniformization ptd_probability_distribution_context_create
Algorithm 17.1 k-th Moment Computation ptd_expected_waiting_time
Algorithm 17.2 Expected Sojourn Times and Cross-Moments ptd_expected_sojourn_time_subset
Algorithm 18.1 PDF + Gradient Computation ptd_graph_pdf_with_gradient
Algorithm 19.1 Unconditioned Path Sampling ptd_random_sample_path
Algorithm 19.2 Backward Probability Computation ptd_backward_probabilities
Algorithm 19.3 Conditioned Path Sampling ptd_random_sample_path_conditioned
Algorithm 20.1 SVGD Optimization SVGD.optimize()
Algorithm 21.1 Metropolis-Hastings with Adaptive Proposals MCMC.sample()
Algorithm 22.1 BFFG Log-Probability Estimation bffg_log_prob
Algorithm 23.1 Method of Moments Estimation method_of_moments
Algorithm 24.1 Probability Matching Estimation probability_matching
Algorithm 25.1 IndexToProperties PropertySet.index_to_props
Algorithm 25.2 PropertiesToIndex PropertySet.props_to_index
Algorithm 26.1 HexGridConstruction HexGrid.from_shapefile
Algorithm 26.2 HexNeighborEnumeration HexGrid.neighbors
Algorithm 27.1 JAX-Compatible PMF Computation compute_pmf_ffi
Algorithm 28.1 GraphBuilder PMF Computation GraphBuilder.compute_pmf

Global Definition Registry

Definitions are numbered NN.M (file number, sequential within file). This table is populated as batches complete.

Definition Name File
— To be populated —

Coverage Matrix

Every public function in the phasic codebase must appear in at least one SOM file’s Implementation Notes section. This matrix is populated during the final homogeneity pass (Batch 15, check H2).

src/c/phasic.c

Function SOM file(s) Status
— To be populated —

src/c/phasic_symbolic.c

Function SOM file(s) Status
— To be populated —

src/c/phasic_hash.c

Function SOM file(s) Status
— To be populated —

src/phasic/trace_elimination.py

Function/Class SOM file(s) Status
— To be populated —

src/phasic/svgd.py

Function/Class SOM file(s) Status
— To be populated —

src/phasic/mcmc.py

Function/Class SOM file(s) Status
— To be populated —

src/phasic/bffg.py

Function/Class SOM file(s) Status
— To be populated —

src/phasic/method_of_moments.py

Function/Class SOM file(s) Status
— To be populated —

src/phasic/probability_matching.py

Function/Class SOM file(s) Status
— To be populated —

src/phasic/state_indexing.py

Function/Class SOM file(s) Status
— To be populated —

src/phasic/hex_grid.py

Function/Class SOM file(s) Status
— To be populated —

src/cpp/parameterized/graph_builder.cpp

Function/Class SOM file(s) Status
— To be populated —

Revision History

Version Date Changes
0.1 2026-04-08 Skeleton created with file listing, dependency DAG, empty registries
1.0 2026-04-09 All 27 content files complete. Global algorithm registry populated (40 algorithms). File listing updated with per-file summaries.