ABSTRACT

A block representation of the BLU factorization for block tridiagonal matrices is presented. Some properties on the factors obtained in the course of the factorization are studied. Simpler expressions for errors incurred at the process of the factorization for block tridiagonal matrices are considered.

1. Introduction

Tridiagonal matrices are connected with different areas of science and engineering, including telecommunication system analysis [1] and finite difference methods for solving partial differential equations [2-4].

The backward error analysis is one of the most powerful tools for studying the accuracy and stability of numerical algorithms. A backward analysis for the LU factorization and for the solution of the associated triangular linear systems is presented by Amodio and Mazzia [5]. BLU factorization appears to have first been proposed for block tridiagonal matrices, which frequently arise in the discretization of partial differential equations. References relevant to this application include Isaacson and Keller [6], Bank and Rose [7], Mattheij [8], Concus, Golub and Meurant [9], Varah [10], Bank and Rose [11], and Yalamov and Plavlov [12]. For a block dense matrix, Demmel and Higham [13] presented error analysis of BLU factorization, and Demmel, Higham and Shreiber [14] also extended earlier analysis.

This paper is organized as follows. We begin, in section 2 by showing the representation of BLU factorization for block tridiagonal matrices. In section 3 some properties on the factors associated with the factorization are presented. Finally, by the use of BLAS3 based on fast matrix multiplication techniques, an error analysis of the factorization is given in section 4.

Throughout, we use the “standard model” of floatingpoint arithmetic in which the evaluation of an expression in floating-point arithmetic is denoted by, with

(see Higham [15] for details). Here is the unit rounding-off associated with the particular machine being used. Unless otherwise stated, in this section an unsubscripted norm denotes.

2. Representation of BLU Factorization for Block Tridiagonal Matrices

Consider a nonsingular block tridiagonal matrix

, (1)

where, are nonsingular,

and with and

are arbitrary. We present the following factorization of. The first step is represented as follows:

whereis the identity matrix of order, and

The second step of the factorization is applied to in order to obtain a matrix with a sub-block, then

Applying the method recursively, it follows that

After steps the block is and the factorization ends, we obtain

where and. From the process of the representation obtained, we get the results as follows:

1) Taking the second step for example, if is nonsingular then we can factor and in a similar manner, and this process can be continued recursively to obtain the complete block LU factorization;

2) There exists obvious difference between partitioned LU factorization (see [15] for further details), GE and block LU factorization in this paper.

3. Some Properties on the Factors of BLU Factorization

The usual property on Schur complements under BLU factorization for block diagonal dominance by rows is similar to that of point diagonal dominance, i.e., Schur complements under BLU factorization for block diagonal dominance by rows inherit the key property on original matrices. For the factors, and, we have the following theorem.

Theorem 3.1. Let in (1) be nonsingular and block diagonally dominant by rows (columns). Then the factors, and also preserve the similar property.

Proof. By the process of the factorization, it follows that

.

Since is block diagonally dominant, by the definition of block diagonal dominance, preserves the same property as the matrix. The proof for and is as follows. The definition of block diagonal dominance, we have

Thus the matrices and are also block diagonally dominant. The result follows by induction, that is, also preserves the same property as the matrix. For the matrix U, we have

By the above proof, it follows that the matrix is also block diagonally dominant. □

The problem is whether the matrices for all and can inherit the same property as the matrix. The result is negative. Take the following block tridiagonal matrix and for example,

where and, and are matrices. Since the following inequalities

then the matrix is block diagonally dominant by rows. Thus the matrix is also block diagonally dominant by rows. However,

thus and are not block diagonally dominant by rows. □

Only if the matrix in (1) is block diagonally dominant by columns, the matrices for all and can preserve the key property of. The reason is as follows.

Based on the definition of block diagonal dominance by columns and the key property of, we have

Therefore the matrices and are also block diagonally dominant by columns. Similarly, for all block diagonally dominant by columns by induction. Then can also preserve the key property of.

4. Error Analysis

The use of BLAS3 based on fast matrix multiplication techniques affects the stability only insofar as it increases the constant terms in the normwise backward error bounds [13]. We make assumption about the underlying level-3 BLAS (matrix-matrix operations).

If and then the computed approximation to satisfies

, (2)

where denotes a constant depending on and. For conventional BLAS3 implementations, (2) holds with [13,15].

The computed solution to the triangular systems, with and, satisfies

where denotes a constant depending on and. In this section, we present the backward error analysis for the block LU factorization by applying BLAS3 based on fast matrix multiplication techniques.

Theorem 4.1. Let and be the computed BLU factors of in (1). Then

where

Proof. Applying the standard analysis of errors, we can obtain the above result. Thus we omit it. □

Let and. The multiplications and do not produce errors because of their structures. Thus the errors of and can be represented as and . Then

where and are the maximum values of

, and

, respectively, when the value ranges from

to. Although the above error bounds are similar to those of and, in the bounds for and satisfies. On the other hand, based on the structure, the error bounds for and is different from those of Theorem 4.1 and we can also obtain the bound for.

Since the factors arising in the factorization in this paper are triangular matrices, from (2) we have

where. Note that the multiplication do not produce error because of the structure of and. Then

Thus

where and.

Compared to the proof of standard analysis of errors, there is a great different in form and the simpler proof of the latter embodies whose superiority. For the former, the error bound does not include, which makes the computation easier.

Applying the result of Theorem 4.1, we have the following theorem.

Theorem 4.2. Let and be the computed BLU factors of in (1). Then

where

Proof. To save clutter we will omit “” from each bound. For the expression arising in, if is sufficiently small, the term is small with respect to the other error matrices, in first order approximation, we obtain

where

Similarly, we have

Therefore the result holds. □

From Theorems 4.1 and 4.2, the bounds for and just depend on one of factors and of elements, which make the computation of error bounds simpler.

5. Acknowledgements

The authors would like to thank the committee of CET 2011 Conference very much for their help. Moreover, this research was supported by Guangdong NSF (32212070) and the Fundamental Research Funds for the Central Universities (12KYFC007).

REFERENCES