Pattern graph for sparse Hessian matrix determination†. (2nd November 2018)

• Record Type: Journal Article
• Authors: Hossain, Shahadat; Hakim Mithila, Nasrin
• Is Part Of: Optimization methods and software. Volume 33:Number 4/6(2018)
• Page Start: 1250
• Page End: 1263
• Publication Date: 2018-11-02
• Subjects: compression–reconstruction -- direct determination -- sparse Hessian -- multicolouring; 90C27 -- 90C30 -- 65F50 -- 49M15 -- 68P05; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1458849
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In a recent work, we have proposed the pattern graph as a unifying framework for methods that exploit sparsity by matrix compression: row compression, column compression or a combination of the two in sparse Jacobian matrix determination. Utilization of structural similarity between the matrix and its graph has been found to be beneficial. In this paper, we show that an important structural property, symmetry, can be exploited in the formulation of sparse Hessian matrix calculations using the pattern graph model. Using the notion of 'direct cover', we present a new general direct method for the determination of sparse Hessian matrices with fixed sparsity pattern and a multicolouring interpretation of it on the pattern graph associated with the matrix. A heuristic procedure for finding direct covers is sketched and some preliminary numerical test results are provided.