Premium
Near‐minimal matrix profiles and wavefronts for testing nodal resequencing algorithms
Author(s) -
Armstrong Bruce A.
Publication year - 1985
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.1620211005
Subject(s) - algorithm , benchmark (surveying) , solver , matrix (chemical analysis) , computer science , simulated annealing , set (abstract data type) , mathematics , mathematical optimization , materials science , geodesy , composite material , programming language , geography
The speeds of algorithms that are specifically designed to solve sparse matrix equations depend on the ordering of the unknowns. Because it is difficult to know what a good ordering is, many resequencing algorithms have been developed to reorder the equations in a manner that minimizes the execution time of the solver being used. There is no theoretical way of evaluating resequencing algorithms, but four widely used algorithms (Cuthill–Mckee, Gibbs–Poole–Stockmeyer, Levy, Gibbs–King) have been compared with one another on the basis of their performance on a set of benchmark test problems. This paper reports what we believe to be are minimal or near‐minimal matrix profiles and wavefronts for the benchmark problems. Comparisons of the minimal results with those produced by the widely used resequencing algorithms show that they produce profiles typically a few tens of per cent greater than minimal, but 50 per cent to 100 per cent greater on two problem types. The algorithm that produced the near‐minimal results used a simulated annealing technique, and is far too slow for general use.