Improved implementation of some coloring algorithms for the determination of large and sparse Jacobian matrices

When we solve a system of nonlinear equations or nonlinear least-squares problem by Newton's method or one of its many variants, the most computationally expensive operations per iteration are the evaluation of the Jacobian and solving the associated linear system. Many real-life problems are sparse and if we know the sparsity structure of the Jacobian in advance, great computational saving can be achieved. We revisit heuristic algorithms and sparse data structures used to determine sparse Jacobian matrices. We provide a new implementation of data structures and heuristics and analyze the performance of our implementation. We provide experimental evidence of the superiority of our bucket heap data structure in terms of locality of reference to data access. Additionally, an efficient implementation of a branch-and-bound type exact coloring algorithm with new tie-breaking strategies is provided. The results are supported by extensive numerical experiments with benchmarking instances from the literature.

Authors

• Khan, Ahamad Imtiaz
• University of Lethbridge. Faculty of Arts and Science

• bucket heap data structure
• heuristic algorithms
• Jacobian matrices
• optimal coloring
• sparse data structures
• tie-breaking strategies

Identifier

hdl:10133/4978

OAI identifier oai:identifier

oai:opus.uleth.ca:10133/4978