Computational methods and algorithms

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

A. B. Kycherov^a, E. J. Oleinik<sup>b

a</sup> M. V. Lomonosov Moscow State University
^b Institute for Mathematical Modelling, Russian Academy of Sciences

Abstract: 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.

UDC: 519.6

Received: 30.10.1992

Bibliographic databases:

• 
•