What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
From MaRDI portal
Publication:5713152
DOI10.1137/S0036144504444711zbMath1076.05034MaRDI QIDQ5713152
Fredrik Manne, Alex Pothen, Assefaw Hadish Gebremedhin
Publication date: 12 December 2005
Published in: SIAM Review (Search for Journal in Brave)
symmetryfinite differencesautomatic differentiationapproximation algorithmssparsityHessiansdistance-\(k\) coloringmatrix partitioning problems
Applications of graph theory (05C90) Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)
Related Items (66)
Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring ⋮ Algorithmic differentiation techniques for global optimization in the COCONUT environment ⋮ Star colouring of bounded degree graphs and regular graphs ⋮ A polyhedral investigation of star colorings ⋮ An entropy-stable discontinuous Galerkin approximation of the Spalart-Allmaras turbulence model for the compressible Reynolds averaged Navier-Stokes equations ⋮ Acyclic colorings of graphs with bounded degree ⋮ Coloring the square of a sparse graph \(G\) with almost \(\varDelta(G)\) colors ⋮ The independent set perturbation method for efficient computation of sensitivities with applications to data assimilation and a finite element shallow water model ⋮ Developments on the Broyden procedure to solve nonlinear problems arising in CFD ⋮ Asynchronous partial update of the restricted additive Schwarz preconditioner to solve nonlinear CFD problems ⋮ Star chromatic bounds ⋮ Matrix-free preconditioning using partial matrix estimation ⋮ An aerodynamic design optimization framework using a discrete adjoint approach with OpenFOAM ⋮ The complexity of restricted star colouring ⋮ Simple decentralized graph coloring ⋮ A generic framework for approximation analysis of greedy algorithms for star bicoloring ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ A matrix-free approach to build band preconditioners for large-scale bound-constrained optimization ⋮ Probing for the Trace Estimation of a Permuted Matrix Inverse Corresponding to a Lattice Displacement ⋮ A framework for parallel second order incremental optimization algorithms for solving partially separable problems ⋮ The complexity of star colouring in bounded degree graphs and regular graphs ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Extending Hierarchical Probing for Computing the Trace of Matrix Inverses ⋮ Coloring squares of planar graphs with maximum degree at most five ⋮ The method of coloring in graphs and its application ⋮ \texttt{HORSES3D}: a high-order discontinuous Galerkin solver for flow simulations and multi-physics applications ⋮ A framework for scalable greedy coloring on distributed-memory parallel computers ⋮ Star coloring of certain graph classes ⋮ Acyclic and star colorings of cographs ⋮ Approximating Hessians in unconstrained optimization arising from discretized problems ⋮ Graph models and their efficient implementation for sparse Jacobian matrix determination ⋮ Bound constrained interval global optimization in the COCONUT environment ⋮ CasADi: a software framework for nonlinear optimization and optimal control ⋮ Graph coloring in the estimation of sparse derivative matrices: Instances and applications ⋮ The independent set perturbation adjoint method: A new method of differentiating mesh-based fluids models ⋮ Analysis of driving styles of a GP2 car via minimum lap-time direct trajectory optimization ⋮ A highly parallel implicit domain decomposition method for the simulation of the left ventricle on unstructured meshes ⋮ A probing method for computing the diagonal of a matrix inverse ⋮ Solving nonlinear equations with the Newton–Krylov method based on automatic differentiation ⋮ Acyclic improper colouring of graphs with maximum degree 4 ⋮ On efficient Hessian computation using the edge pushing algorithm in Julia ⋮ Pattern graph for sparse Hessian matrix determination ⋮ A polyhedral study of the acyclic coloring problem ⋮ On the recursive largest first algorithm for graph colouring ⋮ Higher-order reverse automatic differentiation with emphasis on the third-order ⋮ Adjoint Code Design Patterns ⋮ DSJM: A Software Toolkit for Direct Determination of Sparse Jacobian Matrices ⋮ Preconditioner updates for solving sequences of linear systems in matrix-free environment ⋮ PetIGA: a framework for high-performance isogeometric analysis ⋮ Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope ⋮ CsegGraph: a graph colouring instance generator ⋮ Implementation of sparse forward mode automatic differentiation with application to electromagnetic shape optimization ⋮ Algorithmic Differentiation of Numerical Methods ⋮ Efficient Matching for Column Intersection Graphs ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Randomized GPU Algorithms for the Construction of Hierarchical Matrices from Matrix-Vector Operations ⋮ Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs ⋮ Graph coloring by multiagent fusion search ⋮ Disjunctive ranks and anti-ranks of some facet-inducing inequalities of the acyclic coloring polytope ⋮ Computing the sparsity pattern of Hessians using automatic differentiation ⋮ Design optimization for self-propulsion of a bulk carrier hull using a discrete adjoint method ⋮ Low-Rank Update of the Restricted Additive Schwarz Preconditioner for Nonlinear Systems ⋮ Bi-Directional Determination of Sparse Jacobian Matrices: Approaches and Algorithms ⋮ PETSc TSAdjoint: A Discrete Adjoint ODE Solver for First-Order and Second-Order Sensitivity Analysis ⋮ Efficient detection of hessian matrix sparsity pattern ⋮ Fast Reverse-Mode Automatic Differentiation using Expression Templates in C++
Uses Software
This page was built for publication: What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
