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

*(Russian. English summary)*Zbl 1004.65036Summary: Several algorithms for reordering a sparse symmetric positive definite matrix to a \(2\times 2\) block form are considered; a task of finding a permutation such that the filling is at minimum in the block \((1,1)\) and is located mainly in the blocks \((2,1)\), \((2,2)\) is posed. In this respect two algorithms from the widely known sparse matrix package SPARSPAK are analyzed: QMD – a quotient minimum degree algorithm and ND – the nested dissection algorithm; a new one is proposed which is called \(\text{BND}+\text{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 that the usage of the implicit solution scheme may provide up to 25-30% reduction of primary storage without visible increasing the number of operations required to solve the triangular system.

##### MSC:

65F05 | Direct numerical methods for linear systems and matrix inversion |

65F50 | Computational methods for sparse matrices |