Sparse and banded matrices

In the example above, the mathematical formulation of the problem was indeed a linear system, and we could apply Gaussian elimination directly. Most mathematical problems, however, are not expressed naturally as linear systems. Still, the availability for linear systems of rigorous existence and uniqueness conditions and an automated solution procedure 

we solve aboundary value problem from fluidmechanics numerically by converting it into a linear algebraic system. As this example makes clear, it is sometimes possible to reduce greatly the computational burden of elimination when the matrix is banded, i.e., aU nonzero elements are found near the principal diagonal. 

Example. Solving a boundary value problem from fluid mechanics 

A brief discussion of these equations is provided in the supplemental material in the accompanying website. For a more detailed treatment, see Bird et al. (2002) and Deen (1998). We wish to solve this differential eqnation subject to the no-slip boundary conditions 

This is a classic problem from fluid mechanics that is solved easily by integrating the differential eqnation twice and using the boundary conditions to obtain the constants of integration. The resulting solution is 

---

Although this algorithm is clear and simple, it presents the most ineffective way of storing the global stiffness matrix since it results in a full sparse matrix. Later in this section we will discuss how the storage space and computation time is minimized by using alternative storing schemes such as banded matrices. 

There are four methods for solving systems of linear equations. Cramer s rule and computing the inverse matrix of A are inefficient and produce inaccurate solutions. These methods must be absolutely avoided. Direct methods are convenient for stored matrices, i.e. matrices having only a few zero elements, whereas iterative methods generally work better for sparse matrices, i.e. matrices having only a few non-zero elements (e.g. band matrices). Special procedures are used to store and fetch sparse matrices, in order to save memory allocations and computer time. 

After the Broyden correction for the independent variables has been computed, Broyden proposed that the inverse of the jacobian matrix of the Newton-Raphson equations be updated by use of Householder s formula. Herein lies the difficulty with Broyden s method. For Newton-Raphson formulations such as the Almost Band Algorithm for problems involving highly nonideal solutions, the corresponding jacobian matrices are exceedingly sparse, and the inverse of a sparse matrix is not necessarily sparse. The sparse characteristic of these jacobian matrices makes the application of Broyden s method (wherein the inverse of the jacobian matrix is updated by use of Householder s formula) impractical. 

Matrices can be divided into two general categories dense and sparse matrices. The dense matrices are usually of low order and may have only few zero elements. The sparse matrices may be of high order with many zero elements. A special subcategory of sparse matrices is the group of banded matrices described above. 

Every element has not only two, but many neighbors, typically of the order 26 in a rectangular grid. Moreover, the elements cannot be sorted in a linearly connected sequence. Therefore the matrices H and S, while remaining sparse, acquire a very broad band width with a large number of zeros within the band. 

Although the Almost Band Algorithms use a large number of independent variables, far less computer time is required to obtain a solution to a given distillation problem than might be expected. The computational speed results from the use of selected techniques of sparse matrices and the characteristics of homogeneous functions. 

Finite Element Methods Applied to Many-body Perturbation Theory. - Over the past ten years, the finite element method, which is a classical tool in classical science and engineering applications, has been developed into a technique for the accurate solution of the atomic243 and molecular244,245 electronic structure problem. The piece-wise definition of the form functions employed in the finite element method prevents the computational linear dependencies which occur in the finite basis set expansion method and, moreover, leads to sparse, band structured matrices for which efficient solvers are available. 

The MATLAB elimination solver , also known as the midivide function, can handle matrices stored in sparse-matrix format. If the matrix is banded, the bandwidth is determined and the elimination algorithm modified accordingly. If the matrix is not banded, the solver attempts to reduce the bandwidth as much as possible by applying a hemistic algorithm that interchanges rows and columns. 

---