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. 750-760, November 1973.
- Kailath, Morf & Sidhu, ``Some new algorithms for
recursive estimation in constant linear discrete-time systems,''
Proc. Seventh Princeton Conf. Inform. Sci. Systems,
pp. 344-352, Princeton, NJ, 1973.
- Morf, Sidhu & Kailath, ``Some new
algorithms for recursive estimation in
constant, linear, discrete-time systems,''
IEEE Transactions on Automatic Control,
vol. 19, no. 4, pp. 315-323, August 1974.
- Morf & Kailath, ``Square-root algorithms for linear
least-squares estimation,'' IEEE Trans. Automatic Control,
vol. 20, no. 4, pp. 487-497, August 1975.
- Ljung, Kailath & Friedlander, ``Scattering theory
and linear least-squares estimation -- Part I:
Continuous-time problems,'' Proc. IEEE
, vol. 64, no. 131-138,
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. 663-675, 1978.
- Morf Fast algorithms for multivariable systems,
Ph.D. dissertation, Stanford University, 1974.
- Sidhu, A shift-invariance approach to fast
estimation algorithms,
Ph.D. dissertation, Stanford University, 1975.
- Friedlander, Scattering Theory and Linear Least-Squares 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. 169-184, Academic, 1978.
- Kailath, Kung, & Morf, ``Displacement ranks of a matrix,''
Bulletin of the American Mathematical Society,
vol. 1, no. 5, pp. 769-773, Sep. 1979. See also
Journal of Mathematical Analysis and Applications,
vol. 68, pp. 395-407, 1979.
- Lev-Ari & Kailath,
``Lattice filter parametrization and modeling of
nonstationary processes,''
IEEE Transactions on Information Theory,
vol. 30, no. 1, pp. 2-16, January 1984.
- Lev-Ari & Kailath,
``Triangular factorization of structured Hermitian matrices,''
in Operator Theory: Advances and Applications,
Gohberg, editor, vol. 18, pp. 301-324, Birkhauser,
Boston, 1986.
- Kailath & Chun, ``Generalized displacement structure
for block-Toeplitz, Toeplitz-block, and Toeplitz-derived matrices,''
SIAM J. Matrix Anal. and Appl., vol. 15, no. 1, pp. 114-128, January 1994.
- Chun, Kailath, & Lev-Ari, ``Fast parallel algorithms for
QR and triangular factorization,'' SIAM J. Scient. and Stat.,
vol. 8, no. 6, pp. 899-913,
November 1987.
- Chun & Kailath, ``Divide and conquer solutions of
least-squares problems for matrices with displacement structure,''
SIAM J. Matrix Anal. and Appl., vol. 12, no. 1,
pp. 128-145, January 1991.
- Sayed & Kailath, ``Fast algorithms for
generalized displacement structures and lossless
systems,''
Linear Algebra and Its Applications, vol. 219, pp. 49-78,
April 1995. See also Proc. MTNS, vol. 2, pp. 27-32, Kobe, Japan, 1991.
Lev-Ari and Kailath, ``A State-space approach to factorization of lossless transfer
functions and structured matrices," Linear Algebra and its Applications,
pp. 162-164, 273-295, Feb. 1992 - Ackner and Lev-Ari, ``The Schur algorithm for matrix-valued
meromorphic functions," SIAM J. Matrix Anal. and Appl., vol. 15,
pp. 140-150, Jan. 1994
- Sayed, H. Lev-Ari, and Kailath, ``Time-variant displacement structure and
triangular arrays," IEEE Trans. Acoust. Speech Signal Process., vol. 42, pp. 1052-1062,
May 1994.
- Sayed, Constantinescu, & Kailath,
``Time-variant displacement structure and interpolation problems,''
IEEE Transactions on Automatic Control, vol. 39, no. 5, pp.
960-976, May 1994.
- Sayed & Kailath, ``A look-ahead block Schur algorithm for
Toeplitz-like matrices," SIAM J. Matrix Anal. and Appl., vol. 16,
pp. 388-414, Apr. 1995.
- Lev-Ari, Nonstationary Lattice-Filter 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. 312-316, Jan. 1995. See also Linear Algebra and Its
Applications, 230, pp. 127-150, 1995.
- Di Fiore and Zellini, ``Matrix decompositions using
displacement rank and classes of commutative matrix algebras,"
Linear Algebra and its Applications, 229
(1-3) pp. 49-99, 1995.
- Bevilacqua, Di Fiore, and Zellini, ``h-space structure in matrix
displacemnet formulas," Calcolo, vol. 33, pp. 11-36,
1996.
- T. Boros, A. H. Sayed, H. Lev-Ari, and T. Kailath, ``A generalized
Schur-type algorithm for the joint factorization of a structured matrix
and its inverse,'' Calcolo, vol. 33, pp. 131-145, Jan-Jun 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. 191-208, 1996.
- Kailath and Olshevsky, ``Displacement Structure Approach to Polynomial
Vandermonde and
Related Matrices,'' Linear Algebra and Its Applications,
261 (1997), 49-90.
- Heinig, ``Matrices with higher-order displacement structure, "
Linear Algebra and its Applications, 278, pp. 295-301, 1998.
- III.
- Reviews:
- Kailath, Vieira, & Morf, ``Inverses
of Toeplitz operators, innovations,
and orthogonal polynomials,''
SIAM Review, vol. 20, pp. 106-119, 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. 9-30, Birkhauser,
Boston, 1986.
- Kailath, ``Signal processing
applications of some moment problems,''
in Moments in Mathematics,
American Mathematical Society, Landau, editor,
vol. 37, pp. 71-109, 1987.
- Kailath, ``Remarks on the origin of the displacement rank
concept," J. Appl. Math. Computation, vol. 45, pp. 193-206, Sep. 1991.
- Kailath & Sayed, ``Displacement Structure: Theory
and Applications,'' SIAM Review, vol. 37, no. 3,
pp. 297-386, 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. 933-945, 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. 1-25,
Mar. 1968.
- Bruckstein & Kailath,
``An inverse scattering framework for
several problems in signal processing,''
IEEE ASSP Magazine, pp. 6-20, Jan. 1987.
- Bruckstein & Kailath,
``Inverse scattering for discrete transmission-line
models,'' SIAM Review, vol. 29,
no. 3, pp. 359-389, Sep. 1987.
- Bruckstein, Citron, & Kailath,
``Inverse scattering and minimal partial realization,''
Int. J. Control, vol. 48, no. 4, pp. 1537-1550, 1988.
- Lev-Ari, Bistritz, and Kailath,
``Generalized (bezoutians) and families of efficient root-location procedures,"
IEEE
Trans. Circuits and Systems, vol. 38, pp. 170-186, Feb. 1991.
- Sayed & Kailath, ``Structured matrices
and fast RLS adaptive filtering,''
Proc. 2nd IFAC Workshop on Algorithms and Architectures
for Real-Time Control,
pp. 211-216, Pergamon Press, Seoul, Korea, 1992.
- Sayed, Kailath, Lev-Ari, and Constantinescu, ``Recursive
solutions of rational interpolation problems via fast matrix
factorization,'' Integral Equations
and Operator Theory, vol. 20, pp. 84-118, Sep. 1994.
- Gohberg and Olshevsky,
``Fast state space algorithms for matrix Nehari and
Nehari-Takagi interpolation problems,'' Integral Equations and
Operator Theory, 20, No. 1 (1994), 44-83.
- Gohberg and Olshevsky, ``Complexity of multiplication with vectors for
structured matrices,'' Linear Algebra and Its Applications,
202 (1994), 163-192.
- Cho, Xu, & Kailath, ``Fast identification of state-space
models via exploitation of displacement structure,'' IEEE
Transactions on Automatic Control, vol. 39,
no. 10, pp. 2004-2017, October 1994.
- Sayed, Kailath, and Lev-Ari,
``Generalized Chandrasekhar recursions from the
generalized Schur algorithm'',
IEEE Transactions on Automatic Control, vol. 39, no. 11, pp.
2265-2269, Nov. 1994.
- Constantinescu, Sayed, & Kailath,
``Displacement structure and completion problems,''
SIAM J. Matrix Anal. Appl., vol. 16, no. 1, pp. 58-78,
Jan. 1995.
- Olshevsky, ``Eigenvector computation for almost unitary
Hessenberg matrices and inversion of Szego-Vandermonde matrices
via discrete transmission lines,''
Linear Algebra and Its Applications, 285 (1998), 37-67.
- Boros, Sayed, & Kailath, ``A recursive method
for solving unconstrained tangential interpolation
problems,''
IEEE Transactions on Automatic Control,
vol. 44, pp. 454-470, Mar. 1999.
- Bini & Meini, ``Effective methods for solving banded
Toeplitz systems,'' SIAM J. matrix Anal. Appl., vol. 20, no. 3,
pp. 700-719, 1999.
- Olshevsky and Shokrollahi,
``A displacement approach to efficient decoding of algebraic-geometric
codes,'' Proceedings of the 31st Annual ACM Symposium on Theory
of Computing (STOC'99), 1999, 235-244.
- 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 matrix-vector multiplication algorithms
for confluent Cauchy-like matrices with applications,'' Proc. of of the Thirty Second
ACM Symposium on Theory of Computing (STOC'00), p.573-581; ACM, New York, 2000.
- Fasino, Isospectral flows on displacement structured matrix spaces, ----,
2000
- Heinig and Olshevsky, ``The Schur-type 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 Levinson-Durbin algorithm
for Toeplitz systems and equations," SIAM J. Sci. Statist. Computing,
vol. 1, pp. 303-319, 1980.
- Brent, ``Stability of fast algorithms for structured linear
systems,'' in Fast Reliable Algorithms for Matrices with
Structure, Kailath & Sayed, editors, pp. 103-116, 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. 40-57, 1995.
- Chandrasekaran & Sayed,
``Stabilizing the generalized Schur algorithm,''
SIAM J. Matrix Analysis and Applications, vol. 17,
no. 4, pp. 950-983, Oct. 1996.
- Chandrasekaran & Sayed,
``A fast stable solver for nonsymmetric Toeplitz and
quasi-Toeplitz systems of
linear equations,''
SIAM J. Mat. Anal. and Appl., vol. 19, no. 1,
pp. 107-139, Jan. 1998.
- Stewart & Van Dooren, ``Stability issues in the
factorization of structured matrices,'' SIAM J.
Matrix Anal. Appl., vol. 18, pp. 104-118, 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. 95-114, 1995.
- Gohberg, Kailath, & Olshevsky, ``Fast Gaussian elimination
with partial pivoting for matrices with displacement structure,''
Math. Comp., vol. 64, pp. 1557-1576, 1995.
- Kailath and Olshevsky, ``Diagonal Pivoting for Partially Reconstructible Cauchy-like Matrices,
With Applications to Toeplitz-like Linear Equations and to Boundary
Rational Matrix Interpolation Problems,''
Linear Algebra and Its Applications, 254 (1997), 251-302.
- Gohberg and Olshevsky, ``The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related
matrices,'' Journal of Complexity, 13(2) (1997), 208-234.
- Boros, Kailath, and V.Olshevsky,
``Fast Björck-Pereyra-type algorithm for parallel solution of Cauchy
linear equations,'' Linear Algebra and Its Applications, 302-303 (1999), p.265-293.
- VI.
- Books:
- Heinig & Rost, Algebraic Methods for Toeplitz-like Matrices and Operators, Akademie-Verlag, 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, Time-Varying 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.
|