Tridiagonal system block

Hindmarsh, A. C. Solution of Block-Tridiagonal Systems of Linear Algebraic Equations Lawrence Livermore National Laboratory Report UCID-30150, 1977. 

In many applications, linear systems have block-band structure. In particular, the numerical solution of partial differential equations is frequently reduced to solving block tridiagonal systems (see Section II. A). For such systems, block triangular factorizations of A and block Gaussian elimination are effective. Such systems can be also solved in the same way as usual banded systems with scalar coefficients. This would save flops against dense systems of the same size, but the algorithms exploiting the block structure are usually far more effective. 

Apart from triangular factorization and Gaussian elimination, there exist other effective direct methods for block-banded systems. For instance, the odd-even reduction (the cyclic reduction) is effective for solving symmetric block tridiagonal systems Ax=b with (2 — 1) x (2 — 1), matrices of the form... 

Hindmarsh AC (1977) Solution of block-tridiagonal systems of linear algebiaic equations. Technical Report Rept. UCID-30150, LLL... 

The Jacobian of the system is a square matrix, but importantly, because the residuals at any mesh point depend only on variables at the next-nearest-neighbor mesh point, the Jacobian is banded in a block-tridiagonal form. Figure 16.10 illustrates the structure of the Jacobian in the form used by the linear-equation solution at a step of the Newton iteration,... 

A better alternative approach is what will be called the Rudolph method [476], after the person who introduced it into electrochemical simulation. It was known before 1991 under various names, notably block-tridiagonal [280,412,470,471,528,570]. This comes from the fact that if one lumps the large matrix into a matrix of smaller matrices and vectors, the result is a tridiagonal system that is amenable to more efficient methods of solution. In the present context, we define some vectors... 

Linear systems with a block tridiagonal coefficient matrix can be solved quite efficiently... 

The residues (Nb-kNp at each node) are reduced to zero (a small positive number fixed by specifying an error tolerance at input) iteratively by computing corrections to current values of the unknowns using the Newton-Raphson method (14). Elements of the Jacobian matrix required by this method are computed from analytical expressions. The system of equations to be solved for the corrections has block tridiagonal form and is solved by use of a published software routine (1.5b... 

The coefficient matrix A of the system is the block tridiagonal of Eq. (3). With smaller spacing we may obtain a finer grid and compute the temperatures at more points on the plate. Then the size of the linear system will increase, say to equations in unknowns for larger N but its X coefficient matrix will still be block tridiagonal of the following special form (where blank spaces mean zero entries). 

Because of the stiffness which is inherent to most Chemical Engineering problems, implicit integrators are commonly used in simulations. These integration methods require multiple solutions of the underlying linear equation system. The SFD discretization (1.1) leads to block-tridiagonal matrices that can be solved very efficiently. But, as the order of approximation is only two,... 

The unknowns are taken in a large vector in the order [Rq, Pq, Co,ifo,Ri,Pi,Ci, ifi,..., RN,PN,CN,ifNV but are lumped into the vector of four-point vectors U = [Ri, Pi, Ci, ifiY, i = 0... N, to prepare for the block-tridiagonal procedure for solving the system. The system of equations (13.37) is nonlinear, and the Newton method is used to solve it. At each index i we have three 4x4 blocks in the Jacobian matrix L the left-hand block for the elements at index / — 1 M,, the middle block for index /, and Q the right-hand block for index t -I-1, that symbol chosen here in order to avoid clashes with the concentration symbol R. They produce a tridiagonal block system. For this example, three-point BDF was used, started with one BI step. 

The following technique was first suggested by Butler for strictly one-dimensional systems. We would like to present a generalization to infinite quasi-one-dimensional systems, described by the previously mentioned banded matrices. The evaluation of (38) and (37) requir the computation of a diagonal cluster matrix element of G(z). The block-tridiagonal matrix... 

The system matrix of equation (6.108) contains the two diagonal blocks /3X and j3y and the two offdiagonal blocks Ax and Ay which are both banded tridiagonal. Rather than inverting a tridiagonal block as naively suggested earlier, it is much less costly to multiply the two sides of the block matrix equation (6.108) from the left by the nonsingular block matrix... 

Note that the object was initialized as follows and we only need to point out that the system is tridiagonal blocks with 2x2 block sizes ... 

The basic algorithm is Newton s method, which exploits the structured form of the system (tridiagonal block). 

The comparison of the results obtained by direct CO and by NFC calculation of the DOS-s show even in the case of the more complicated periodic poly(gly-gly-ser) chain excellent agreement (the band limits and the peaks in the DOS-s curves agree within 0.002 a.u. 0.05 eV which was the step length applied in the NFC procedure). Therefore one can expect that also in the case of disordered chains the NFC method in its matrix block form provides highly reliable results. For quasi-lD-systems there seems to be no other method which can compete with this technique. For 2- and 3D disordered systems unfortunately there is no way to write down a tridiagonal (or triblockdiagonal) matrix and therefore the method is not applicable (for further details see the paper of Ladik at ref. /2/). 

---