Quality Balancing Heuristics with Three Variants of Sloan Algorithm

O. Medek and P. Tvrdík (Czech Republic)


Algorithms, Domain decomposition, Reordering of vari ables, Parallel solver.


We use a parallel direct solver based on the Schur complement method for solving large sparse linear systems arising from the finite element method. A domain decom position of a problem is performed using a graph partition ing. It results in sparse submatrices. An envelope method is used to store these submatrices in the memory and to fac torize them. Prior to the solution, the variables of each sub matrix are reordered by the Sloan algorithm to minimize qualities: memory requirements and the factorization time. These qualities are usually disbalanced. In this paper, we describe results of integrating our recently developed Qual ity Balancing (QB) heuristics and our modification of the Sloan algorithm, called Boundary Sloan algorithm (BSA), to balance the qualities. We discuss the issues of behaviour of the QB heuristics and evaluate the results of implemen tation of 3 variants of the Sloan algorithm within the QB heuristics. We show that the BSA outperforms previous ordering methods in terms of optimality of balancing, min imizing the qualities and running time of the QB heuristics.

Important Links:

Go Back