Question

Let A be a tri-diagonal matrix. Find the LU factorization of A and calculate the number of FLOPs needed for the factorization.

Answer 1

11.3 Algorithms In this section, we review three basic algorithms: the Thomas algorithm, CR, and PCR, and their two hybrid variants: CR-PCR and PCR-Thomas. 11.3.1 The Thomas Algorithm The Thomas algorithm is Gaussian elimination in the tridiagonal system case. The algorithm has two phases, forward elimination and backward substitution. In the first phase, we eliminate the lower diagonal by c'ı = 7, c'i = 0;-&; 10; i = 2, 3, ...,n d'ı = , d'i = bi--, i = 2, 3,..., n. The second phase solves all unknowns from last to first: Xn = d'n, ki = d'; - d'iXj+1,i = n - 1, ..., 2, 1. The algorithm is simple, but inherently serial and takes 2n computation steps, because the calculation of c'i, d'i, and x; depends on the result of the immediately preceding calculation of ci-1, d'i-1, and Xi+l

9.4.1 Efficiency Analysis To determine the flop count for the Thomas algorithm, note that lines 8 and 9 account for two divisions. The for loop beginning at line 10 executes n - 2 times, and each execution involves 2 divisions, 3 subtractions, and 3 multiplications, for a total of 8 (n − 2) flops. The statement at line 14 involves 2 subtractions, 1 division, and 2 multiplications, a total of 5 flops. The for loop beginning at line 17 executes n - 1 times, and each execution performs 1 subtraction and 1 multiplication, for a total of 2 (n − 1) flops. The total flop count is then 2 + 8(n − 2)+ 5 + 2(n − 1)= 10n – 11. The Thomas algorithm is linear (O (n)). As we will see in Chapter 11, the Gaussian elimination algorithm for a general n x n matrix requires approximately n flops. It is not uncommon when using finite difference methods for the solution of partial differential equations that tridiagonal systems of order 500 x 500 or higher must be solved. Standard Gaussian elimination will not take advantage of the sparsity of the tridiagonal system and will require approximately (500)% = 83333333 flops. Using the Thomas algorithm requires 10 (500) – 11 = 4989 flops, quite a savings!
I am giving the full Thomas Algorithm although you just need the LU factorization part of the tridiagonal matrix.