Direct solver

In principle, the task of solving a linear algebraic systems seems trivial, as with Gauss elimination a solution method exists which allows one to solve a problem of dimension N (i.e. N equations with N unknowns) at a cost of O(N ) elementary operations [85]. Such solution methods which, apart from roundoff errors and machine accuracy, produce an exact solution of an equation system after a predetermined number of operations, are called direct solvers. However, for problems related to the solution of partial differential equations, direct solvers are usually very inefficient Methods such as Gauss elimination do not exploit a special feature of the coefficient matrices of the corresponding linear systems, namely that most of the entries are zero. Such sparse matrices are characteristic of problems originating from the discretization of partial or ordinary differential equations. As an example, consider the discretization of the one-dimensional Poisson equation... 

Matrix A is a 3N x 3N dense matrix. For a small number of unknowns, direct solvers are practical, especially in the case of multiple sources. One can use different types of iterative methods, discussed in Chapter 4, for the solution of this problem. However, if N is large, the storage of A is extremely memory consuming, not to mention the complexity of direct matrix inversion. 

TK Solver has two methods of solving equations. (1) The Direct Solver is just what it sounds like values are substituted for variables, and both sides of an expres-... 

For one-dimensional problems the direct TDMA algorithm is an efficient solver. In these cases the solver is computationally inexpensive and has the advantage that it requires a minimum amount of storage. For direct solvers, the number of operations to be performed to obtain the solution of a system of equations can be determined beforehand. However, for multi-dimension problems the TDMA algorithm is applied line by line on a selected plane... 

The answer to this question is mainly driven by the computational cost of solving the kinetic equation due to the large number of independent variables. In the simplest example of a 3D velocity-distribution function n t, x, v) the number of independent variables is 1 + 3 + 3 = 1. However, for polydisperse multiphase flows the number of mesoscale variables can be much larger than three. In comparison, the moment-transport equations involve four independent variables (physical space and time). Furthermore, the form of the moment-transport equations is such that they can be easily integrated into standard computational-fluid-dynamics (CFD) codes. Direct solvers for the kinetic equation are much more difficult to construct and require specialized numerical methods if accurate results are to be obtained (Filbet Russo, 2003). For example, with a direct solver it is necessary to discretize all of phase space since a priori the location of nonzero values of n is unknown, which can be very costly when phase space is not bounded. 

The dense linear system in Eq. 16, without any sparsification, could be very expensive to solve for large-scale systems. The computational time of a direct solver, for example, the Gaussian elimination, grows as the cube of the number of unknowns. For the resonator example, there are near 60,000 unknowns in the discretization shown in Fig. 3. Gaussian elimination would require more than 300,000 gigaflops to solve. In addition, the memory required to store the matrix grows as the square of the number of unknowns, and for the resonator example, it would require more than 40 gigabytes. 

What about the solution of the linear algebraic systems. Direct solvers such as MA28 from the Harwell Library perform very well in ID. After testing a lot of different iterative schemes in 2D the BICGSTAB-algorithm [12] preconditioned by SSOR turned out to perform best for the current reaction-diffusion system. 

The direct solvers listed in Table 11.1 solve the assembled set of equations by the Gaussian elimination method [1, 8] and deliver solutions often faster than the iterative solvers for ID and 2D problems. Direct solvers can be used for 3D models if the degrees of freedom is less than 10 . Iterative solvers, on the other hand, are used in models with degrees of freedom above 10 and in the solution of 3D problems, for which the memory requirements of the direcrt solvers are excessive. The readers are directed to Ref. [15] for further details of the solvers listed in Table 11.1. 

Finally, it should be noted that the multigrid method can be used as either an iterative process or as a direct solver (the so-called full multigrid or nested iteration method ). 

Some of the conclusions drawn are that, for our specific finite element models (non-symmetric, using penalty method for some connections, possible softening behavior), direct solvers outperform the iterative solver significantly. As expected direct solver were not as scalable as iterative solvers, however, specifics of our finite element models (dealing with soil-structure interaction) resulted in poor initial performance of iterative solvers, that, even with excellent performance scaling, could not catch up with the efficiency of direct solvers. IT is also important to note that parallel direct solvers, such as MUMPS and SPOOLES provided the best performance and would be recommended for use with finite element models that, as ours did, feature non-symmetry, are poorly conditioned (they are ill-posed due to use of penalty method) and can be negative definite (for softening materials). 

Zone, O. Vanderstraeten, O. Keunings, R. A parallel direct solver for implicit finite element problems based on automatic domain decomposition. In Massively Parallel Processing Applications and Development, Dekker, L., Smit, W., Zuidervaart, J.C., Eds. Elsevier, Amsterdam, 1994 809-816. 

Direct versus iterative solutions. The mechanics of setting up the necessary system for direct solvers, that is, for algorithms that obtain pressures in a single pass using a full matrix solver, have been discussed by Peaceman (1977), Aziz and Settarri (1979), and Thomas (1982). Even for the coarse mesh considered, the resulting 121 x 121 matrix is large and requires monumental inversion efforts. Usually, the unknowns are cleverly ordered, and cleaner... 

Iterative methods. Since an objective of this book is the development of portable tools, we will not discuss direct solvers. Suffice it to say that such solvers, the most notorious being Gaussian elimination, are well documented in the literature (e g., see Carnahan, Luther, and Wilkes, 1969). We will, by contrast, emphasize iterative techniques, since these require minimal computer resources and allow the greatest flexibility. As we will show, they are also very useful in designing smart and robust algorithms. For reasons that will become obvious, let us rewrite Equation 7-15 in the form... 

Direct solvers. In Chapter 7, we explained why direct solvers impose... 

In contrast with domain methods such as Finite Element Method (FEM) or Finite Differential Method (FDM), Boundary Element Method (BEM) discretises only the boundary of the domain. Because of this reduction of the dimensionality BEM was expected to be advantageous in large-scale problems. However, the application of this method has so far been limited to relatively small problems. This was because coefficient matrices in BEM are full and unsymmetrical, due to which both the operation count and the memory requirements for the matrix equation buildup are of the order of 0 N ), where N is the number of unlmowns. The operation count even increases to 0(A ) as one attempts to solve the matrix equations with conventional direct solvers. In particular, the full matrix property leads to a serious exhaustion of the memory of a computer and is an obstacle for applications of BEM to large-scale problems. On the other hand, coefficient matrices in domain methods are banded and both computational complexity for matrix buildup and memory requirements are 0(iV). 

---