Home Geography Direct methods for sparse matrices

Applications of the matrix modification formula

There are many applications for using the matrix modification formula in practical problems, some more promising than others. We will briefly describe a few.

Application to stability corrections

We noted in Section 10.3 that Stewart (1974) recommended the modification formula when some of the pivots selected for sparsity and stability for a first set of numerical values were small for a subsequent matrix. If the kth pivot is too small, simply add a suitably large a to akk and proceed with the factorization using that pivot. This would then require correcting for the modification. That is, we have successfully factorized the matrix

and now must make a simple rank-one correction to solve the original problem. Since the stability is not guaranteed, iterative refinement is still needed.

Building a large problem from subproblems

When very large mathematical models are built, they are often assembled from a number of smaller models, which have been tested and validated individually. A large-scale circuit is generally made up of many smaller components. A large, complex structural analysis is created from its many substructures. Today’s large power grids represent the interconnection of many regional power systems. This can readily be seen in Figure B.10. The diagonal blocks correspond to major independent power systems in the Western Region of USA, while the relatively few entries outside the blocks on the diagonal correspond to the interconnections between these power systems. Figure 9.7.1 can be seen in this way as well. B and W represent two independent models, which are brought together through the added edges and vertices shown in the diagram.

Without the connections, the matrix has the form

There are two blocks that may be solved in two parts, with separate factors for Лц and A22. Including the connections corresponds to adding the correction

where ДАj has nonzeros in only k rows and kj columns, i = 1, 2, j = 1, 2, and k = ki + k2 is small. The modification formula may be applied directly, which allows the known factors of A11 and A22 to be used again. Alternatively, we might treat the unmodified problem as

and solve by block forward substitution, which requires a new factorization of Aii + ДЛ11 and A22 + ДЛ22, but the code that was written for the original problem can be reused. Now the modification has the rank min(k1, k2).

The astute reader will recognize another way of solving the larger connected problem taking advantage of the solved subproblems by using partitioning. We make a comparison with this approach in the next section.

Found a mistake? Please highlight the word and press Shift + Enter
 Related topics