Home
Selected Bibliography on Displacement Structure
 O.
 A General Reference:
Kailath and Sayed, Fast Reliable Algorithms for Matrices with
Structure, SIAM, PA, 1999.
This edited volume has 10 survey papers (with common notation and
references) and a large bibliography of over 400 items.
The following references overlap some already in this
bibliography. However, there are some newer papers and moreover
the grouping under different headings might be of value. We emphasize
that the limitations of space, time, and personal knowledge, all bias
the selection.
 I.
 Origins:
Precursors (Schur, Livsic, Sakhnovich), (Trench, Sobolev),
(Nevanlinna?, Potapov?)
 Kailath, ``Some new algorithms for recursive
estimation in constant linear systems,''
IEEE Transactions on Information Theory,
vol. 19, no. 6, pp. 750760, November 1973.
 Kailath, Morf & Sidhu, ``Some new algorithms for
recursive estimation in constant linear discretetime systems,''
Proc. Seventh Princeton Conf. Inform. Sci. Systems,
pp. 344352, Princeton, NJ, 1973.
 Morf, Sidhu & Kailath, ``Some new
algorithms for recursive estimation in
constant, linear, discretetime systems,''
IEEE Transactions on Automatic Control,
vol. 19, no. 4, pp. 315323, August 1974.
 Morf & Kailath, ``Squareroot algorithms for linear
leastsquares estimation,'' IEEE Trans. Automatic Control,
vol. 20, no. 4, pp. 487497, August 1975.
 Ljung, Kailath & Friedlander, ``Scattering theory
and linear leastsquares estimation  Part I:
Continuoustime problems,'' Proc. IEEE
, vol. 64, no. 131138,
Jan. 1976.
 Dewilde, Vieira, & Kailath, ``On a generalized
SzegöLevinson realization algorithm for
optimal linear prediction: a network synthesis approach,''
IEEE Transactions on Circuits and Systems,
vol. 25, pp. 663675, 1978.
 Morf Fast algorithms for multivariable systems,
Ph.D. dissertation, Stanford University, 1974.
 Sidhu, A shiftinvariance approach to fast
estimation algorithms,
Ph.D. dissertation, Stanford University, 1975.
 Friedlander, Scattering Theory and Linear LeastSquares Estimation,
Ph.D. dissertation, Stanford University, 1976.
 II.
 Formalisation/Theory:
 Kailath, Ljung, & Morf, ``A new
approach to the determination of Fredholm
resolvents of nondisplacement kernels'',
in Topics in Functional Analysis,
Gohberg and Kac, editors, pp. 169184, Academic, 1978.
 Kailath, Kung, & Morf, ``Displacement ranks of a matrix,''
Bulletin of the American Mathematical Society,
vol. 1, no. 5, pp. 769773, Sep. 1979. See also
Journal of Mathematical Analysis and Applications,
vol. 68, pp. 395407, 1979.
 LevAri & Kailath,
``Lattice filter parametrization and modeling of
nonstationary processes,''
IEEE Transactions on Information Theory,
vol. 30, no. 1, pp. 216, January 1984.
 LevAri & Kailath,
``Triangular factorization of structured Hermitian matrices,''
in Operator Theory: Advances and Applications,
Gohberg, editor, vol. 18, pp. 301324, Birkhauser,
Boston, 1986.
 Kailath & Chun, ``Generalized displacement structure
for blockToeplitz, Toeplitzblock, and Toeplitzderived matrices,''
SIAM J. Matrix Anal. and Appl., vol. 15, no. 1, pp. 114128, January 1994.
 Chun, Kailath, & LevAri, ``Fast parallel algorithms for
QR and triangular factorization,'' SIAM J. Scient. and Stat.,
vol. 8, no. 6, pp. 899913,
November 1987.
 Chun & Kailath, ``Divide and conquer solutions of
leastsquares problems for matrices with displacement structure,''
SIAM J. Matrix Anal. and Appl., vol. 12, no. 1,
pp. 128145, January 1991.
 Sayed & Kailath, ``Fast algorithms for
generalized displacement structures and lossless
systems,''
Linear Algebra and Its Applications, vol. 219, pp. 4978,
April 1995. See also Proc. MTNS, vol. 2, pp. 2732, Kobe, Japan, 1991.
LevAri and Kailath, ``A Statespace approach to factorization of lossless transfer
functions and structured matrices," Linear Algebra and its Applications,
pp. 162164, 273295, Feb. 1992  Ackner and LevAri, ``The Schur algorithm for matrixvalued
meromorphic functions," SIAM J. Matrix Anal. and Appl., vol. 15,
pp. 140150, Jan. 1994
 Sayed, H. LevAri, and Kailath, ``Timevariant displacement structure and
triangular arrays," IEEE Trans. Acoust. Speech Signal Process., vol. 42, pp. 10521062,
May 1994.
 Sayed, Constantinescu, & Kailath,
``Timevariant displacement structure and interpolation problems,''
IEEE Transactions on Automatic Control, vol. 39, no. 5, pp.
960976, May 1994.
 Sayed & Kailath, ``A lookahead block Schur algorithm for
Toeplitzlike matrices," SIAM J. Matrix Anal. and Appl., vol. 16,
pp. 388414, Apr. 1995.
 LevAri, Nonstationary LatticeFilter Modeling,
Ph.D. dissertation, Stanford University, 1983.
 Chun, Fast Array Algorithms for Structured Matrices,
Ph.D. dissertation, Stanford University, 1989.
 D. Pal, Fast Algorithms for Structured Matrices with Arbitrary
Rank Profile, Ph.D. dissertation, Stanford University, 1990
 Ackner, Fast Algorithms for Indefinite Matrices and Meromorphic
Functions, Ph. D. dissertation, Stanford University, 1991.
 Sayed, Displacement Structure in Signal
Processing and Mathematics, Ph.D. dissertation,
Stanford University, 1992.
 Bozzo and Di Fiore, ``On the use of certain matrix algebras
associated with discrete trigonometric transforms in matrix displacement
decomposition," SIAM J. Matrix Anal. and Appl., vol. 16,
pp. 312316, Jan. 1995. See also Linear Algebra and Its
Applications, 230, pp. 127150, 1995.
 Di Fiore and Zellini, ``Matrix decompositions using
displacement rank and classes of commutative matrix algebras,"
Linear Algebra and its Applications, 229
(13) pp. 4999, 1995.
 Bevilacqua, Di Fiore, and Zellini, ``hspace structure in matrix
displacemnet formulas," Calcolo, vol. 33, pp. 1136,
1996.
 T. Boros, A. H. Sayed, H. LevAri, and T. Kailath, ``A generalized
Schurtype algorithm for the joint factorization of a structured matrix
and its inverse,'' Calcolo, vol. 33, pp. 131145, JanJun 1996.
 Kailath and Olshevsky, ``Displacement structure approach to
discrete transform based preconditioners
of G.Strang type and of T.Chan type,'' Calcolo, vol. 33,
pp. 191208, 1996.
 Kailath and Olshevsky, ``Displacement Structure Approach to Polynomial
Vandermonde and
Related Matrices,'' Linear Algebra and Its Applications,
261 (1997), 4990.
 Heinig, ``Matrices with higherorder displacement structure, "
Linear Algebra and its Applications, 278, pp. 295301, 1998.
 III.
 Reviews:
 Kailath, Vieira, & Morf, ``Inverses
of Toeplitz operators, innovations,
and orthogonal polynomials,''
SIAM Review, vol. 20, pp. 106119, January
1978.
 Kailath, ``A theorem of I. Schur and
its Impact on modern signal processing,''
Operator Theory: Advances and Applications,
Gohberg, editor, vol. 18, pp. 930, Birkhauser,
Boston, 1986.
 Kailath, ``Signal processing
applications of some moment problems,''
in Moments in Mathematics,
American Mathematical Society, Landau, editor,
vol. 37, pp. 71109, 1987.
 Kailath, ``Remarks on the origin of the displacement rank
concept," J. Appl. Math. Computation, vol. 45, pp. 193206, Sep. 1991.
 Kailath & Sayed, ``Displacement Structure: Theory
and Applications,'' SIAM Review, vol. 37, no. 3,
pp. 297386, Sep. 1995.
 Olshevsky, ``Pivoting for structured matrices, with
applications,'' www.cs.gsu.edu/ matvro
 See also the papers in the previously mentioned review volume edited by Kailath and
Sayed.
 IV.
 Some Applications:
 Rao & Kailath, ``Orthogonal
digital filters for VLSI implementation,''
IEEE Transactions on Circuits and Systems,
vol. 31, no. 11, pp. 933945, Nov. 1984.
 Citron, Algorithms and Architectures for
Error Correcting Codes, Ph.D. dissertation,
Stanford University, 1986.
 Kailath, Bruckstein, and Morgan, `` Fast matrix factorization via discrete
transmission lines," Linear Algebra and its Applications, vol. 75, pp. 125,
Mar. 1968.
 Bruckstein & Kailath,
``An inverse scattering framework for
several problems in signal processing,''
IEEE ASSP Magazine, pp. 620, Jan. 1987.
 Bruckstein & Kailath,
``Inverse scattering for discrete transmissionline
models,'' SIAM Review, vol. 29,
no. 3, pp. 359389, Sep. 1987.
 Bruckstein, Citron, & Kailath,
``Inverse scattering and minimal partial realization,''
Int. J. Control, vol. 48, no. 4, pp. 15371550, 1988.
 LevAri, Bistritz, and Kailath,
``Generalized (bezoutians) and families of efficient rootlocation procedures,"
IEEE
Trans. Circuits and Systems, vol. 38, pp. 170186, Feb. 1991.
 Sayed & Kailath, ``Structured matrices
and fast RLS adaptive filtering,''
Proc. 2nd IFAC Workshop on Algorithms and Architectures
for RealTime Control,
pp. 211216, Pergamon Press, Seoul, Korea, 1992.
 Sayed, Kailath, LevAri, and Constantinescu, ``Recursive
solutions of rational interpolation problems via fast matrix
factorization,'' Integral Equations
and Operator Theory, vol. 20, pp. 84118, Sep. 1994.
 Gohberg and Olshevsky,
``Fast state space algorithms for matrix Nehari and
NehariTakagi interpolation problems,'' Integral Equations and
Operator Theory, 20, No. 1 (1994), 4483.
 Gohberg and Olshevsky, ``Complexity of multiplication with vectors for
structured matrices,'' Linear Algebra and Its Applications,
202 (1994), 163192.
 Cho, Xu, & Kailath, ``Fast identification of statespace
models via exploitation of displacement structure,'' IEEE
Transactions on Automatic Control, vol. 39,
no. 10, pp. 20042017, October 1994.
 Sayed, Kailath, and LevAri,
``Generalized Chandrasekhar recursions from the
generalized Schur algorithm'',
IEEE Transactions on Automatic Control, vol. 39, no. 11, pp.
22652269, Nov. 1994.
 Constantinescu, Sayed, & Kailath,
``Displacement structure and completion problems,''
SIAM J. Matrix Anal. Appl., vol. 16, no. 1, pp. 5878,
Jan. 1995.
 Olshevsky, ``Eigenvector computation for almost unitary
Hessenberg matrices and inversion of SzegoVandermonde matrices
via discrete transmission lines,''
Linear Algebra and Its Applications, 285 (1998), 3767.
 Boros, Sayed, & Kailath, ``A recursive method
for solving unconstrained tangential interpolation
problems,''
IEEE Transactions on Automatic Control,
vol. 44, pp. 454470, Mar. 1999.
 Bini & Meini, ``Effective methods for solving banded
Toeplitz systems,'' SIAM J. matrix Anal. Appl., vol. 20, no. 3,
pp. 700719, 1999.
 Olshevsky and Shokrollahi,
``A displacement approach to efficient decoding of algebraicgeometric
codes,'' Proceedings of the 31st Annual ACM Symposium on Theory
of Computing (STOC'99), 1999, 235244.
 Bini, Meini, & Ramaswami, ``Analyzing M/G/1 paradigms through
QBDs: The role of the block structure in computing the matrix G,''
in Advances in Algorithmic Methods for Stochastic Models,
Latouche & Taylor, editors, Notable Publications, 2000.
 Olshevsky and Shokrollahi, ``Fast matrixvector multiplication algorithms
for confluent Cauchylike matrices with applications,'' Proc. of of the Thirty Second
ACM Symposium on Theory of Computing (STOC'00), p.573581; ACM, New York, 2000.
 Fasino, Isospectral flows on displacement structured matrix spaces, ,
2000
 Heinig and Olshevsky, ``The Schurtype algorithm for matrices with
Hessenberg displacement structure,'' to appear in Structured Matrices in Operator
Theory, Numerical Analysis, Control, Signal and Image Processing, Contemporary
Mathematics Series, AMS , 2000.
 V.
 Numerical Issues:
 Cybenko, `` The numerical stability of the LevinsonDurbin algorithm
for Toeplitz systems and equations," SIAM J. Sci. Statist. Computing,
vol. 1, pp. 303319, 1980.
 Brent, ``Stability of fast algorithms for structured linear
systems,'' in Fast Reliable Algorithms for Matrices with
Structure, Kailath & Sayed, editors, pp. 103116, SIMAX,
PA, 1999.
 Bojanczyk, Brent, de Hoog, & Sweet, ``On the
stability of the Bareiss and related Toeplitz factorization
algorithms,'' SIAM J. matrix. Anal. Appl.,
vol. 16, pp. 4057, 1995.
 Chandrasekaran & Sayed,
``Stabilizing the generalized Schur algorithm,''
SIAM J. Matrix Analysis and Applications, vol. 17,
no. 4, pp. 950983, Oct. 1996.
 Chandrasekaran & Sayed,
``A fast stable solver for nonsymmetric Toeplitz and
quasiToeplitz systems of
linear equations,''
SIAM J. Mat. Anal. and Appl., vol. 19, no. 1,
pp. 107139, Jan. 1998.
 Stewart & Van Dooren, ``Stability issues in the
factorization of structured matrices,'' SIAM J.
Matrix Anal. Appl., vol. 18, pp. 104118, 1997.
 Heinig, ``Inversion of generalized Cauchy matrices and
other classes of structured matrices,'' in Linear
Algebra for Signal Processing, IMA Vol. Math. Appl.,
vol. 69, pp. 95114, 1995.
 Gohberg, Kailath, & Olshevsky, ``Fast Gaussian elimination
with partial pivoting for matrices with displacement structure,''
Math. Comp., vol. 64, pp. 15571576, 1995.
 Kailath and Olshevsky, ``Diagonal Pivoting for Partially Reconstructible Cauchylike Matrices,
With Applications to Toeplitzlike Linear Equations and to Boundary
Rational Matrix Interpolation Problems,''
Linear Algebra and Its Applications, 254 (1997), 251302.
 Gohberg and Olshevsky, ``The fast generalized ParkerTraub algorithm for inversion of Vandermonde and related
matrices,'' Journal of Complexity, 13(2) (1997), 208234.
 Boros, Kailath, and V.Olshevsky,
``Fast BjörckPereyratype algorithm for parallel solution of Cauchy
linear equations,'' Linear Algebra and Its Applications, 302303 (1999), p.265293.
 VI.
 Books:
 Heinig & Rost, Algebraic Methods for Toeplitzlike Matrices and Operators, AkademieVerlag, Berlin and
Birkhäuser, 1984.
 Bini & Pan, Matrix and Polynomial Computations,
Vol. I: Fundamental Algorithms, Birkhauser, Boston, 1994; vol. II, 2001.
 Constantinescu, Schur Parameters, Factorization, and
Dilation Problems, Birkhauser, Basel, 1996.
 Bini and Di Benedetto, Special Issues on Toeplitz Matrices: Structures,
Algorithms and Applications, (Cortona Workshop, 1996), Calcolo, vol. 33.
 Dewirlde and Van Der Veen, TimeVarying Systems and Computations,
Kluwer, 1998.
 Kailath & Sayed, editors, Fast Reliable Algorithms for
Matrices with Structure, SIAM, PA, 1999.
 Bini, Tyrtyshnikov, & Yalamov, editors,
Structured Matrices & Recent Developments in Theory and
Computation, Nova Science, 2000.
 Olshevsky, editor, Structured Matrices in Operator
Theory: Numerical Analysis, Control, Signal and Image Processing,
Amer. Math. Soc., 2000.
