Keywords: direct solution, mesh coarsening, preprocessing, fill-in reduction, node amalgamation, graph compression, super-element.

A new solution strategy is proposed to improve the overall efficiency of the direct solution of problems arising from finite element analysis. The adjacent elements in the finite element mesh are merged systematically to form a coarser model compromising super-elements. The coarsened mesh is used in the preprocessing phase of the solver instead of the original mesh. The time required for preprocessing the original mesh may be comparable to the time required for the factorization [1]. The use of the coarsened mesh considerably cuts down the size of the graphs used in the preprocessing phase, and consequently the time required for the preprocessing is reduced.

In addition to the improvements in the preprocessing phase, the coarsening reduces the runtime of the factorization phase. The larger dense matrix blocks obtained by the coarsening make dense matrix operations more efficient. Moreover, the number of additional assembly operations performed in the multifrontal method reduces by assembling merged finite elements at once. These properties of the coarsening method resemble the node amalgamation techniques proposed in the past studies [2,3]. Contrary to the node amalgamation, the coarsening method can be applied to the original finite element mesh before the preprocessing takes place. This gives the opportunity to perform the condensation steps for the merged elements in parallel with the preprocessing phase. This new level of parallelism can be exploited to improve the overall solver performance.

The coarsening scheme is evaluated for two-dimensional meshes. After verifying the large reduction in the size of various graphs used by preprocessing algorithms, the execution times of three fill-in reduction algorithms are presented for the original and coarsened meshes. The coarsening method gives speed-ups as high as eight without any significant degradation in the quality of the orderings produced.

Finally, the performance parameters influencing the efficiency of multifrontal solver are identified. The improvement in the factorization phase is demonstrated by the performance parameters and runtime of a multifrontal code. Although the multifrontal solver is used for the test runs, the proposed strategy is expected to yield similar results for the state-of-the-art direct solvers since they also use similar fill-in reduction algorithms and perform the factorization on dense matrix blocks [4].

1

I.S. Duff, J.A. Scott, "Towards an automatic ordering for a symmetric sparse direct solver", Technical Report RAL-TR-2006-001, Rutherford Appleton Laboratory, 2006.

2

I.S. Duff, J.K. Reid, "The multifrontal solution of indefinite sparse symmetric linear systems", ACM Transactions on Mathematical Software, 9, 302-335, 1983. doi:10.1145/356044.356047

3

C. Ashcraft, "The influence of relaxed supernode partitions on the multifrontal method", ACM Transactions on Mathematical Software, 15(4), 291-309, 1989. doi:10.1145/76909.76910

4

N.I.M. Gould, J.A. Scott, Y. Hu, "A Numerical Evaluation of Sparse Direct Solvers for the Solution of Large Sparse Symmetric Linear Systems of Equations", ACM Transactions on Mathematical Software, 33(2), 10, 2007. doi:10.1145/1236463.1236465

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 £95 +P&P)