COMPLEXITY ANALYSIS OF REORDERING ALGORITHMS FOR THE IMPLEMENTATION OF MULTIFRONTAL SOLUTION TECHNIQUE.

Solution of large order sparse system of equations need to be optimized on numerical computers in terms of memory usage and execution time. This optimization includes rearranging the equations in terms of its position and identifying submatric blocks where dense matrix operations can be defined.Direct solution methods of linear system of equation are based on factorization of coefficient matrix to set the solution. This thesis studies the effect of cholesky factorization of symmetric sparse matrices for reducing fill-ins and factorization time. The study is carried out on ISRO’s in-house developed finite element structural analysis software, FEASTSMT direct solution schemes. The reordering techniques used here are Approximate minimum degree ordering (AMD), Column approximate minimum degree ordering (COLAMD), Multiple minimum degree ordering (MMD) and METIS. Since the finite element models of launch vehicle and satellite structures result in vary large order sparse system of equations, a variation of cholesky method called multifrontal scheme based on element connectivity information is used. The studies were carried out on basic large order 1D, 2D , 3D models as well as the models involving combination of these three types. Complexity of these algorithms depends on the data structure of assembly tree, which is a relationship between submatrices. The overall execution time , average, worst and best case time complexities of the multifrontal method with respect to number of partial factorization were studied and presented in this thesis.