← Back
Home › Systems › Numerical and mathematical computing

eigensolver

large-scale eigenvalue and SVD solver

ARPACK, SLEPc

SystemTechniques · 4Primitives · 12 eigensolver Fill-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.›Incomplete 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.›Sparse 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.›Graph partitioninggraphs · medium: Split a graph into k balanced parts with few edges between them; multilevel coarsen-partition-refine (METIS, KaHIP) for quality, streaming heuristics (LDG, Fennel) for one-pass scale.›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.›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²).›PRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›CUDA and GPU languageslanguages · low: Programming GPUs: thousands of lockstep threads, bound by memory bandwidth; libraries first, Triton for fused kernels, CUDA C++ for peak speed.›PCA and SVDmachine-learning · low: Find orthogonal directions of maximum variance by an SVD of the centred data; randomized SVD gets the top k components in a few passes.›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.›Tiled matrix multiplicationml-training · low: Block GEMM into tiles held in shared memory and registers, so each byte loaded from DRAM feeds many FMAs; the core of fast GEMM.›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.›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.›Reproducible reductionnumerics · low: Order-independent floating-point sums (fixed order, Kahan, binned) for bit-for-bit reproducibilityd-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.›Gpu memory coalescing bankinghardware-os · low: Coalesced global loads, shared memory bank conflicts, L2 and HBM bandwidth on GPUs

Similar systems

Share the most building blocks with this one.

linear-solver-suite 50 %convex-optimizer 35 %structural-fem 32 %ode-dae-solver 29 %circuit-sim 28 %