Full and partial Jacobian computation via graph coloring : algorithms and applications

摘要

Simulations and optimizations are carried out to investigate real-world problems in science and engineering. For instance, solving systems of linear equations with sparse Jacobian matrices is mandatory when using a Newton-type algorithm. The sparsity of Jacobian matrices is exploited and only a subset of the nonzero elements is determined to successfully reduce the usage of the restricting resources - memory and computational effort. This reduction is crucial to investigate real-world problems. The determination of all nonzero elements is denoted as full Jacobian computation, opposed to the partial Jacobian computation where only a subset of the nonzero elements is computed. Reducing the computational effort to determine nonzero elements with automatic differentiation is modeled by graph coloring problems. Beside the bipartite graph model for general Jacobian matrices, regular Cartesian grids are a graph class arising from stencil-based computations. In this thesis, graph coloring algorithms for full and partial Jacobian computation are introduced, for both representations. Furthermore, for regular grids, the presented algorithms even result in minimal colorings. Thereafter, several classes of Jacobian matrices are considered to assess which coloring method should be employed for which class. Iterative solvers for systems of linear equations are matrix-free and require solely access to (transposed) Jacobian matrix-vector products. These products are efficiently provided by automatic differentiation without storing the nonzero elements of the Jacobian matrix. However, when using standard preconditioning techniques to speed up the solution of the linear systems, the access to these nonzero elements is necessary. In this thesis, the preconditioning technique is restricted to a subset of the Jacobian elements which are determined using partial Jacobian computation. The bipartite graph model is employed to determine a coloring but also to carry out the symbolic factorization for the preconditioning. An initial set of nonzero elements is given; further nonzero elements are chosen without exceeding the computational effort and the available memory. A classification for these nonzero elements is introduced. Strategies and algorithms to select these elements are given. Finally, the coloring algorithms as well as the combination of preconditioning and partial Jacobian computation are applied to several applications from science and engineering. It is shown that the demands of memory and computational effort are successfully reduced.