LU decomposition

In the LU decomposition method, the idea is to decompose a given matrix A to a product LU. If we specify the diagonal elements of either the upper or lower triangular matrix, the decomposition will be unique. If the elements of the major diagonal of the L matrix are unity, the decomposition method is called the Doolittle method. It is called the Grout method if the elements of the major diagonal of the U matrix are unity. 

In the Doolittle method, the upper triangular matrix U is determined by the Gauss elimination process, while the matrix L is the lower triangular matrix containing the multipliers employed in the Gauss process as the elements below the unity diagonal line. More details on the Doolittle and Grout methods can be found in Hoffman (1992). 

The use of the LU decomposition method is to find solution to the linear equation Ax = b. Let the coefficient matrix A be decomposed to LU, i.e., A = LU. Hence, the linear equation will become 

Since the multiplication is associative and L L = I, the previous equation will become 

Equations B.69 and B.70 will form basic set of equations for solving for x. This is done as follows. For a given b vector, the vector b is obtained from Eq. B.70 by forward substitution since L is the lower triangular matrix. Once b is found, the desired vector x is found from Eq. B.69 by backward substitution because U is the upper triangular matrix. 

In this section we restrict considerations to an nxn nansingular matrix A. As shown in Section 1.1, the Gauss-Jordan elimination translates A into the identity matrix I. Selecting off-diagonal pivots we interchange some rows of I, and obtain a permutation matrix P instead, with exactly one element 1 in each row and in each column, all the other entries beeing zero. Matrix P is called permutation matrix, since the operation PA will interchange some rows of A.  

We can save some efforts reducing A into a triangular matrix and not all the way to the identity matrix. More generally, we will write A as 

---

The most frequently used modifications of the basic Gaussian elimination method in finite element analysis are the LU decomposition and frontal solution techniques. 

In some applications the diagonal elements of the upper triangular matrix are not predetermined to be unity. The formula used for the LU decomposition procedure in these applications is slightly different from those given in Equations (6.10) to (6.12), (Press et al., 1987). 

The right-hand side in Equation (6.18) is known and hence its solution yields the error 5x in the original solution. The procedure can be iterated to improve the solution step-by-step. Note that implementation of this algorithm in the context of finite element computations may be very expensive. A significant advantage of the LU decomposition technique now becomes clear, because using this technique [A] can be decomposed only once and stored. Therefore in the solution of Equation (6.18) only the right-hand side needs to be calculated. 

SOLVER Assembles elemental stiffness equations into a banded global matrix, imposes boundary conditions and solves the set of banded equations using the LU decomposition method (Gerald and Wheatley, 1984). SOLVER calls the following 4 subroutines. ... 

SOLVE - inserts the prescribed boundary conditions and uses an LU decomposition method to solve the assembled equations. 

SOLVES THE GT,OBAL STIFFNESS MATRIX USING LU DECOMPOSITION... 

The LU decomposition is essentially a Gaussian elimination, arranged for maximum efficiency (Ref. 112). The chief reason for doing an LU decomposition is that it takes fewer multiplications than would be needed to find an inverse. Also, once the LU decomposition has been found, it is possible to solve for multiple right-hand sides with little increase in work. The multiphcation count for a.n n X n matrix and m right-hand sides is... 

If an inverse is desired, it can be calculated by solving for the LU decomposition and then solving n problems with right-hand sides consisting of all zeroes except one entiy. Thus 4n /2> — n/2> multiplications are required for the inverse. The determinant is given by... 

LU decomposition. Efficiency is best for a small number of components C. 

Steady-state solutions are found by iterative solution of the nonlinear residual equations R(a,P) = 0 using Newton s methods, as described elsewhere (28). Contributions to the Jacobian matrix are formed explicitly in terms of the finite element coefficients for the interface shape and the field variables. Special matrix software (31) is used for Gaussian elimination of the linear equation sets which result at each Newton iteration. This software accounts for the special "arrow structure of the Jacobian matrix and computes an LU-decomposition of the matrix so that qu2usi-Newton iteration schemes can be used for additional savings. 

The case of a nonlinear observational relationship (Equation 6.3) will be examined later. Equation 6.78 yields the following linear equation which is solved by LU decomposition (or any other technique) to obtain k(J+l)... 

If you have taken a course on numerical methods, you would be pleased to know that MATLAB can do LU decomposition ... 

Therefore, given a plane truss, one may first compute the stiffness matrix, then compute the displacements, then the individual member forces. The entire process is bounded by the calculation of a matrix inversion (or LU-Decomposition), and, hence, has running time 0(m3). 

A.8 A technique called LU decomposition can be used to solve sets of linear algebraic equations. L and U are lower and upper triangular matrices, respectively. A lower triangular matrix has zeros above the main diagonal an upper triangular matrix has zeros below the main diagonal. Any matrix A can be formed by the product of LU. 

A factorization of O of this form can be carried out using standard matrix algorithms such as LU decomposition or Gaussian elimination with back-substitution [2,34,35]. The main advantage is the straightforward evaluation of the stmcture transformation corresponding to Eq. (3), which is just... 

In models of beads with full hydrodynamic interactions, for which the mobility tensor is represented by a dense matrix, the Cholesky decomposition of H requires 3N) /6 operations. Eor large N, this appears to be the most expensive operation in the entire algorithm. The only other unavoidable 0 N ) operation is the LU decomposition of the K x K matrix W that is required to solve for the K constraint forces, which requires /3 operations, or roughly... 

Since det(A) =0 if and only if A is singular, it provides a convenient way of checking singularity. Determinants have traditionally been used also for solving matrix equations (ref. 10), but both the Gauss-Jordan method and the Gaussian elimination are much more efficient. The determinant itself can easily be calculated by LU decomposition. For the decomposed matrix (1.45)... 

---