← Back
Home › Systems › Numerical and mathematical computing

sat-smt-solver

SAT / SMT solver

Z3

SystemTechniques · 4Primitives · 13 sat-smt-solver Congruence closurecompilers · medium: Union-find over terms with congruence propagation; decides equality with uninterpreted functionsBit blastingoptimization · medium: Reduce bit-vector constraints to CNF via adder, multiplier and comparator circuitsCDCL SAT solvingoptimization · medium: Search for a satisfying assignment, learn a new constraint from every dead end, and jump back past irrelevant choices; handles industrial formulas with millions of clauses.›Dpll toptimization · medium: SMT architecture: CDCL over boolean abstraction plus theory solvers, theory propagation, Nelson-OppenHash consingdata-structures · low: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximalUnion-findgraphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Tseitin transformationoptimization · low: Linear-size CNF encoding of formulas with auxiliary variablesd-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Drat proof certificatesoptimization · low: DRAT and LRAT proofs emitted by SAT solvers and checked independentlyTwo watched literalsoptimization · low: Unit propagation for SAT that watches just two literals per clause, so backtracking costs nothing and long clauses are rarely touched.›Arena allocatorsystems · low: Allocate by bumping a pointer through big chunks and free everything at once: a few instructions per allocation for objects sharing a lifetime.›Simplex methodoptimization · low: Solves linear programs by walking along the edges of the feasible polytope from vertex to vertex, one basis swap (pivot) at a time; the workhorse behind MIP solvers.›E graphscompilers · low: Equality saturation: e-graphs compactly hold many equivalent programs, then extract the cheapestArithmetic circuitshardware-os · low: Adder and multiplier circuits: carry-lookahead, prefix adders, Booth encoding, Wallace and Dadda treesFloating-point errornumerics · low: How IEEE 754 rounding error accumulates and how to contain it: compensated (Kahan/Neumaier) and pairwise summation, error-free transformations with FMA, ULP comparisons.›LU and Cholesky factorizationnumerics · low: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).›Sparse matrices (CSR)numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›

Similar systems

Share the most building blocks with this one.

constraint-solver 21 %