← Back
Home › Systems › Numerical and mathematical computing

nonlinear-solver

nonlinear systems of equations

KINSOL, PETSc SNES

SystemTechniques · 9Primitives · 19 nonlinear-solver Halo exchangedistributed · medium: Each rank stores its block plus a border copy of its neighbours' edge cells, refreshed by small messages every step; communication scales with block surface, not volume.›Graph coloringgraphs · medium: Greedy/DSatur colouring for conflict-free assignment such as radio channelsContinuation methodsnumerics · medium: Homotopy and source or gmin stepping to make Newton converge from a far startGmresnumerics · medium: GMRES with restarts: Arnoldi, Givens rotations, for nonsymmetric sparse systemsIncomplete factorization preconditi…numerics · medium: Sparse approximate LU or Cholesky factors (ILU, IC) that precondition Krylov solvers: fewer iterations than Jacobi, less memory than a direct solve.›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.›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.›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.›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.›Collective communicationml-training · low: The family of group exchanges (broadcast, reduce, all-gather, reduce-scatter, all-to-all) and the latency-plus-bytes cost model that picks ring, tree or direct algorithms by message size and topology.›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.›Floating-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.›Multigridnumerics · low: Smooths high-frequency error on the fine grid and solves the smooth remainder on coarser grids; O(n) elliptic solves at any resolution.›Eager rendezvous protocoldistributed · low: MPI point-to-point: eager sends for small messages, rendezvous handshake for large onesRdmanetworking · low: RDMA verbs over InfiniBand/RoCE: queue pairs, memory registration, one-sided opsZero-copy I/Onetworking · low: Move bytes between files, sockets and NICs by passing page references instead of copying through user space: sendfile, splice, MSG_ZEROCOPY, kTLS.›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.›Adaptive Runge-Kutta (Dormand-Princ…numerics · low: An embedded 5(4) Runge-Kutta pair estimates each step's error for free and resizes the step to meet a tolerance; the default non-stiff solver.›PRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›+ 2 more techniques+ 3 more primitives

Similar systems

Share the most building blocks with this one.

nonlinear-optimizer 43 %cfd-fem-solver 35 %linear-solver-suite 33 %multiphysics 33 %ode-dae-solver 31 %