Profile reduction for sparse matrices using an ant system

![CDATA[The analysis of many problems in structural engineering involves the solution of simultaneous equations arising from the finite element (FE) method. Such equations usually involve a sparse coefficient matrix and for large structures the greater part of the computer execution time may be devoted for solving these equations. Hence some appropriate specified patterns for the solutions of the corresponding equations have been provided, such as banded form, profile form and partitioned form. These patterns are constructed by suitable nodal ordering of their graph models. In FE analysis, for the case of a general problem with m degrees of freedom per node, there are m coupled equations produced for each node. In this case re-sequencing is usually performed on the nodal numbering of the corresponding graph models to reduce the bandwidth, profile or wavefront of such sparse matrices, because the size of this problem is m fold smaller than that for an m degree of freedom numbering. When the skyline method is adopted for the solution then profile reduction becomes an important issue [1]. Since the nature of this problem is NP-complete, many approximate methods and heuristics are developed using graph theory, algebraic graph theory and genetic algorithms. In this paper a new ant algorithm based on the ant system (AS) developed by Dorigo, as a combinatorial optimization tool, is proposed to determine an optimal assignment for the nodal ordering problem to reduce the profile of associated sparse matrices. In this algorithm, a local search procedure is also included to further improve the profiles.]]