Heuristics and metaheuristics for accelerating the computation of simultaneous equations models through a Steiner tree

Abstract

Simultaneous equations models can be solved with a variety of algorithms. Some methods use the QR-decomposition of several matrices associated to the equations in the system. To accelerate the computation of those QR-decompositions and consequently the solution of simultaneous equations models, the QR-decomposition of a matrix associated to an equation can be obtained from that of another matrix associated to another equation which contains the variables of the first equation. A Steiner tree can be used, with nodes representing the equations in the model and with edges whose associated weight is the cost of computing the QR-decomposition of an equation from that of another equation. The Steiner tree of the graph associated to the simultaneous equations model gives the order of computation of the QR-decompositions of lowest computational cost. But the number of nodes in the graph is very large, and exact methods to obtain the Steiner tree are not applicable. In this paper, the application of heuristics and metaheuristics to approach the Steiner tree of the graph associated to a simultaneous equations model is considered. A heuristic and a genetic algorithm are presented and analyzed. The quality of the tree obtained and its usability in an algorithm to solve simultaneous equations models efficiently is experimentally studied. (C) 2013 Elsevier B.V. All rights reserved.