REDUCTION TO BLOCK TRIANGULAR FORM

We consider algorithms for reducing a general sparse matrix to block triangular form. This form allows the corresponding set of linear equations to be solved as a sequence of subproblems. We discuss the assignment problem of placing entries on the diagonal as a part of the process of finding the block triangular form, though this problem is of interest in its own right. We also consider the extension of the block triangular form to rectangular and singular matrices.

Introduction

If we are solving a set of linear equations

whose matrix has a block triangular form, savings in both computational work and storage may be made by exploiting this form. Our purpose in this chapter is to explain how a given matrix may be permuted to this form, and to demonstrate that the form is (essentially) unique. Remarkably economical algorithms exist for this task, typically requiring O(n) + 0(т) operations for a matrix of order n with т entries.

We find it convenient to consider permutations to the block lower triangular form

though the block upper triangular form could be obtained with only minor modification (see Exercise 6.1).

A matrix that can be permuted to the form (6.1.2), with N > 1, is said to be reducible. If no block triangular form other than the trivial one (N = 1) can be

Direct Methods for Sparse Matrices, second edition. I. S. Duff, A. M. Erisman, and J. K. Reid. © Oxford University Press 2017. Published 2017 by Oxford University Press.

found, the matrix is called irreducible1. We expect each Bn to be irreducible, for otherwise a finer decomposition is possible.

The advantage of using block triangular forms such as (6.1.2) is that the set of equations (6.1.1) may then be solved by the simple forward substitution

(where the sum is zero for i = 1) and the permutation

We have to factorize only the diagonal blocks В a, i =1, 2,..., N. The off-diagonal blocks Bj, i > j, are used only in the multiplications Bj yj. Notice in particular that all fill-in is confined to the diagonal blocks. If row and column interchanges are performed within each diagonal block for the sake of stability and sparsity, this will not affect the block triangular structure.

There are classes of problems for which the algorithms of this chapter are not useful. For some applications, it may be known a priori that the matrix is irreducible. Matrices arising from the discretization of partial differential equations are often of this nature. In other cases, the decomposition may be known in advance from the underlying physical structure. If A is symmetric with nonzero diagonal entries, reducibility means that A may be permuted to block diagonal form. While the methods of this chapter will find this form, it is likely to be more efficient to find it via the elimination tree, see Section 12.4. Even when the form is known, the automatic methods may still be useful to avoid the need to explicitly input the problem in the required form or to verify that it has not been changed by data input errors.

Note that many areas produce reducible systems, including chemical process design (Westerberg and Berna 1979), linear programming (Hellerman and Rarick 1971), and economic modelling (Szyld 1981). Because of the speed of the block triangularization algorithms and the savings that result from their use in solving reducible systems of equations, they can be very beneficial.

 
Source
< Prev   CONTENTS   Source   Next >