G-Pre: A Graph-Theory-Based Matrix Preconditioning Algorithm for Finite Element Simulation Solutions

Abstract

In finite element simulation and analysis, increasing simulation scales place high demands on the preconditioning and solution process of linear matrices. However, the most commonly used preconditioning methods for incomplete LU factorization usually increase data access and computation due to data padding and forward/backward operations, as well as affect parallel computing design. To address these challenges, this study proposes a graph–theory-based matrix preconditioning algorithm called G-Pre. In this method, by introducing a graph partitioning algorithm and a graph rearrangement algorithm before ILU factorization, the matrix is partitioned into regions and the elements are rearranged, which improves the ease of data access for matrix computation and facilitates parallel computation. The results of numerical experiments show that in terms of solution efficiency, the solver based on the G-Pre preconditioning algorithm achieved an average speedup ratio of 2.1 and 4.3 times that of the solver based on ILU factorization and the direct solver, respectively. At the same time, the algorithm computed the results with an error of no more than 2%. This method is a novel technique for the matrix preconditioning of finite element solvers and a powerful algorithmic tool to cope with the increasing computational demands of finite element simulations.

Keywords

• graph reordering
• factorization
• preconditioning
• matrix solving
• finite element simulation