← Back
Home › Systems › Numerical and mathematical computing

nonlinear-optimizer

nonlinear programming and least squares

IPOPT, Ceres

SystemTechniques · 8Primitives · 18 nonlinear-optimizer Graph coloringgraphs · medium: Greedy/DSatur colouring for conflict-free assignment such as radio channelsFill-reducing orderingnumerics · medium: Permute a sparse symmetric matrix before Cholesky/LU so the factor has few new nonzeros; minimum degree, nested dissection and RCM trade quality, speed and parallelism.›Levenberg marquardtnumerics · medium: Damped Gauss-Newton nonlinear least squares for model calibrationSparse direct solvernumerics · medium: Solve sparse Ax = b exactly by reordering, symbolic analysis, numeric LLᵀ/LU and triangular solves; fill-in, not flops per entry, decides the cost.›Interior-point method (primal-dual,…optimization · medium: Follows the central path with Newton steps on the perturbed KKT system, one sparse Cholesky per iteration; Mehrotra's predictor-corrector makes it fast.›Quadratic programmingoptimization · medium: Convex QP solvers (active-set, interior-point, ADMM) for constrained optimizationBundle adjustmentrobotics · medium: Jointly refine camera poses and 3D points by sparse nonlinear least squares on reprojection errorSparse 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.›Finite differencesnumerics · low: Replace derivatives with weighted differences of grid values; simple stencils plus a stability condition (CFL) turn PDEs like heat, advection and waves into array loops.›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²).›Newton root findingnumerics · low: Linearize at the guess and jump to the tangent root; quadratic convergence near a simple root, made robust by brackets (1D) or line search.›Robust statisticsstatistics · low: Location and scale estimates (median, MAD, trimmed mean, Huber M-estimator) that stay correct when a minority of the data is garbage.›Reverse-mode automatic differentiat…ml-training · low: Record the forward computation on a tape, then sweep it backwards once to get the gradient of a scalar loss for all inputs.›Conjugate gradientnumerics · low: Krylov iteration for symmetric positive definite Ax = b using one matrix-vector product and two dot products per step; converges in about √κ iterations.›Constrained parameter transformsnumerics · low: Map constrained parameters to unconstrained space (log, logit, simplex, Cholesky) with Jacobian correctionsFloating-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.›L-BFGSnumerics · low: Quasi-Newton minimizer that approximates the inverse Hessian from the last m gradient differences via the two-loop recursion; O(m·n) memory and work per step.›d-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.›BFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Rigid-body transforms (SE(3) poses)robotics · low: Represent, compose, invert, integrate and interpolate 3D poses as unit quaternion plus translation, with exp/log maps for small motions and uncertainty.›PRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›Homogeneous transformsgeometry · low: 4x4 affine and projective matrices, homogeneous coordinates, view and projection, normal matricesQuaternion rotationsgeometry · low: Unit quaternions as 3D rotations: 4 floats, cheap composition, no gimbal lock, plus the conversions, interpolation choices and numerical care needed in practice.›+ 1 more techniques+ 2 more primitives

Similar systems

Share the most building blocks with this one.

nonlinear-solver 43 %convex-optimizer 41 %circuit-sim 29 %lp-mip-solver 25 %eigensolver 25 %