## Error analysis of a fast partial pivoting method for structured
matrices

157. D. R. Sweet and R. P. Brent,
Error analysis of a fast partial pivoting method for structured matrices,
* Proceedings SPIE, Volume 2363, Advanced Signal Processing Algorithms*,
(edited by F. Luk), SPIE,
Bellingham, Washington, 1995, 266-280.

Longer version:
Error analysis of a partial pivoting method for structured matrices,
Technical Report TR-CS-95-03, Computer Sciences Laboratory,
ANU, June 1995, 20 pp.
arXiv:1005.0667v1

Related talk presented at a * Workshop on Numerical Methods for Structured
Matrices in Filtering and Control*, Santa Barbara, August 1996.

Conference Paper:
dvi (33K),
pdf (230K),
ps (97K).

Technical Report:
dvi (38K),
pdf (242K),
ps (143K).

Transparencies (Santa Barbara, August 1996):
dvi (21K),
pdf (235K),
ps (152K).

## Abstract

Many matrices that arise in the solution of signal processing problems have
a special {\em displacement structure}. For example, adaptive filtering
and direction-of-arrival estimation yield
matrices of Toeplitz type.
A recent method of Gohberg, Kailath and Olshevsky (GKO)
allows fast Gaussian elimination with partial pivoting for such structured
matrices.
In this paper, a rounding error analysis is performed on the
Cauchy and Toeplitz variants of the GKO method.
It is shown the error growth depends on the growth
in certain auxiliary vectors, the *generators*,
which are computed by the
GKO algorithms. It is also shown that in certain circumstances, the growth in
the generators can be large, and so the error growth is much larger than would
be encountered with normal Gaussian elimination with partial pivoting.
A modification
of the algorithm to perform a type of row-column pivoting is proposed;
it may ameliorate this problem.

## Comments

The GKO algorithm, which is based on an identity of Heinig
[*IMA Volumes in Mathematics and its Applications* 69 (1994), 95-114],
is described in
Gohberg, Kailath and Olshevsky
[* Math. Comp.* 64 (1995), 1557-1576].
For subsequent attempts by Ming Gu and Michael Stewart
to improve the stability of
the GKO algorithm,
and results on the stability of the generalised Schur algorithm,
see [177]
and the references given there.

Go to next publication

Return to Richard Brent's index page