2. Stabilized Schur Algorithms

Shivkumar Chandrasekaran, Ali H. SayedSociety 1999 · DOI · OpenAlex

Abstract

2.1 INTRODUCTION As mentioned in Ch. 1, linear systems of equations are generally solved by resorting to the LDU factorization (or Gaussian elimination) of the coefficient matrix. But for indefinite or nonsymmetric matrices, the LDU factorization is well known to be numerically unstable if done without pivoting (see, e.g., [GV96], [Hig96], and also the discussion in Ch. 4). Moreover, since pivoting can destroy the structure of a matrix, it is not always possible to incorporate it immediately into a fast algorithm for structured matrices without potential loss of computational efficiency. It was observed in [Hei95], however, that for Cauchy-like structured matrices, pivoting can be incorporated into fast factorization algorithms without reducing the computational efficiency of the algorithms (see the discussion in Sec. 1.13). This is because for such matrices, the displacement operators are diagonal and, therefore, column and row permutations do not destroy the Cauchy-like structure. The algorithm proposed in [Hei95] was of a hybrid type, involving Schur-type and Levinson-type operations. The technique was further used in [GKO95] to incorporate pivoting into the generalized Schur algorithm. This was achieved by first transforming different kinds of matrix structure into Cauchy-like structure and then using the so-called generator recursions of the Schur algorithm with partial pivoting. Sections1.13 and 4.3 of this book review this approach to factorization.
BibTeX
@inproceedings{chandrasekaran1999stabilized,
  author = {Shivkumar Chandrasekaran and Ali H. Sayed},
  title = {{2. Stabilized Schur Algorithms}},
  booktitle = {Society},
  year = {1999},
  doi = {10.1137/1.9781611971354.ch2},
}

Loading related content...

Figure