Auxiliary Storage Methods for Solving Finite Element Systems

From MaRDI portal





Consider the direct solution of the system of linear equations \(Ax=b\), where A is an \(N\times N\), sparse, symmetric and positive definite matrix. This system is solved using the Cholesky method by factoring A into \(R^ TR\) where R is an upper triangular matrix. The solution vector x is then found by solving \(R^ Ty=b\) and \(Rx=y\). The authors are particularly interested in the case where A is so large that auxiliary storage must be used to store the Cholesky factor R. In this paper, the authors analyze and compare two schemes for solving such a problem. The first method uses nested dissection partitioning. In section 2, nested dissection and incomplete nested dissection orderings and partitionings for a model n by n grid problem are reviewed. In section 3 the authors describe a method which uses nested dissection partitioning in the context of large sparse linear systems. A detailed analysis of the input/output (I/0) traffic is done in section 4 for a model n by n grid problem which is partitioned using incomplete nested dissection. In particular, it is shown that using a few vectors of length \(N=n^ 2\) permits to achieve an I/0 traffic of \(O(n^ 2\) log n), which is dominated by the \(O(n^ 3)\) arithmetic computation. The second method, introduced in section 5, is an important enhancement of the previous basic strategy; it results in reducing the traffic to \(O(n^ 2\) log log n), apart from storing the Cholesky factor itself. This rection in the I/0 traffic is achieved by modifying the algorithm to exploit a certain tree structure associated with nested dissection. Finally, numerical experiments are provided in section 6 and further extensions are considered in section 7. In conclusion, this is a very important and well written contribution on the way of solving large sparse linear systems as those issued from finite element approximations. This paper is in continuation to the previous well known works of the first author and his coworkers.











This page was built for publication: Auxiliary Storage Methods for Solving Finite Element Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3732847)