Keywords: profile reduction, sparse matrices, ordering, graphs, ant system, local search.

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 [2,3,4].

In this paper a new ant algorithm based on the ant system (AS) developed by Dorigo [5], 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. Different phases of the algorithm are as follows:

1. The phase of initial data processing and preliminary calculations,
2. The phase of the construction of solution,
3. The phase of local search,
4. The phase of updating the information and statistics,
5. The phase of updating the pheromone trails.

Examples are included to illustrate the performance of the present approach. Finally the results are compared to some well-known graph theoretical profile optimization algorithms, namely King and Sloan algorithms. The results achieved by the AS show that the graph theoretical methods can be improved using this approach. The method presented in this paper may also be considered as a complementary approach, which can be incorporated in any available graph theoretical algorithm for further improvement of the results.

1

A. Jennings, "A compact storage scheme for the solution of symmetric linear simultaneous equations", Computing Journal, 9, 281-285, 1966.

2

S.W. Sloan, "An algorithm for profile and wavefront reduction of sparse matrices", International Journal for Numerical Methods in Engineering, 23, 1693-1704, 1986.

3

A. Kaveh, "Optimal Structural Analysis", John Wiley, 2nd edition, Exeter, U.K., 2006.

4

H.A. Rahimi Bondarabady, A. Kaveh, "Nodal ordering using graph theory and a genetic algorithm", Finite Elements in Analysis and Design, 40, 9-10, 1271-1280, 2004.

5

M. Dorigo, "Optimization, Learning and Natural Algorithms", (in Italian), PhD thesis, Dipartimento di Elettronica e Informazione, Politecnico di Milano, IT, 1992.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £140 +P&P)