Auxiliary Storage Methods for Solving Finite Element Systems
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.
- An incomplete nested dissection algorithm for parallel direct solution of finite element discretizations of partial differential equations
- Direct methods for solving large sparse systems of equations based on the two by two block decomposition of the matrix
- scientific article; zbMATH DE number 3900092 (Why is no real title available?)
- scientific article; zbMATH DE number 3951883 (Why is no real title available?)
- A survey of direct methods for sparse linear systems
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)