Stability of the Partitioned Inverse Method  (Higham and Pothen)

======================================================================
SIAM Journal on Scientific Computing
Volume 15-1, January 1994, pp.  139-148
(C) 1994 by Society for Industrial and Applied Mathematics
All rights reserved


Title:            Stability of the Partitioned Inverse Method for 
                  Parallel Solution of Sparse Triangular Systems

Author:           Nicholas J. Higham and Alex Pothen

AMS Subject
Classifications:  65F05, 65F50, 65G05

Key words:        sparse matrix, triangular system, substitution 
                  algorithm, parallel algorithm, rounding error 
                  analysis, matrix inverse

----

ABSTRACT

Several authors have recently considered a parallel method for solving 
sparse triangular systems with many right-hand sides.
The method employs a partition into sparse factors of the product form 
of the inverse of the coefficient matrix. It is shown here that while 
the method can be unstable, stability is guaranteed if a certain 
scalar that depends on the matrix and the partition is small
and that this scalar is small when the matrix is well conditioned.
Moreover, when the partition is chosen so that the factors have the
same sparsity structure as the coefficient matrix, the backward error 
matrix can be taken to be sparse.


======================================================================

SIAM
3600 University City Science Center
Philadelphia, PA  19104-2688, USA

Phone:  215-382-9800, 800-447-7426 (USA only)
Fax:  215-386-7999
E-mail:  journals@siam.org