Direct methods for solving large sparse equations based on the block two by two decomposition of the matrix

Several algorithms for reordering sparse symmetric positive definite matrix to a block two by two form are considered; a task of finding a permutation such that filling is at minimum in a block $(1,1)$ and is located mainly in blocks $(2,1)$, $(2,2)$ is posed. In this respect two algorithms from widely known sparse matrix package SPARSPAK are analyzed: QMD – a Quotient Minimum Degree and ND – nested dissection algorithms; a new one is proposed which is called $\mathrm{BND}+\mathrm{qmd}$ – Balanced ND with internal (influencing block $(1,1)$) qmd-ordering. The results of numerical experiments for a set of grid problems containing 10000–25000 unknown values are presented. These results show the usage of implicit solution scheme may provide up to 25–30% reduction of primary storage without visible increasing the number of operations required to solve triangular system.