Skip navigation
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?)

  1. 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.
  2. 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.
  3. 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.
  4. Morf & Kailath, ``Square-root algorithms for linear least-squares estimation,'' IEEE Trans. Automatic Control, vol. 20, no. 4, pp. 487-497, August 1975.
  5. Ljung, Kailath & Friedlander, ``Scattering theory and linear least-squares estimation -- Part I: Continuous-time problems,'' Proc. IEEE , vol. 64, no. 131-138, Jan. 1976.
  6. 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.
  7. Morf Fast algorithms for multivariable systems, Ph.D. dissertation, Stanford University, 1974.
  8. Sidhu, A shift-invariance approach to fast estimation algorithms, Ph.D. dissertation, Stanford University, 1975.
  9. Friedlander, Scattering Theory and Linear Least-Squares Estimation, Ph.D. dissertation, Stanford University, 1976.

II.
Formalisation/Theory:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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

  9. 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
  10. 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.
  11. Sayed, Constantinescu, & Kailath, ``Time-variant displacement structure and interpolation problems,'' IEEE Transactions on Automatic Control, vol. 39, no. 5, pp. 960-976, May 1994.
  12. 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.
  13. Lev-Ari, Nonstationary Lattice-Filter Modeling, Ph.D. dissertation, Stanford University, 1983.
  14. Chun, Fast Array Algorithms for Structured Matrices, Ph.D. dissertation, Stanford University, 1989.
  15. D. Pal, Fast Algorithms for Structured Matrices with Arbitrary Rank Profile, Ph.D. dissertation, Stanford University, 1990
  16. Ackner, Fast Algorithms for Indefinite Matrices and Meromorphic Functions, Ph. D. dissertation, Stanford University, 1991.
  17. Sayed, Displacement Structure in Signal Processing and Mathematics, Ph.D. dissertation, Stanford University, 1992.
  18. 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.
  19. 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.
  20. Bevilacqua, Di Fiore, and Zellini, ``h-space structure in matrix displacemnet formulas," Calcolo, vol. 33, pp. 11-36, 1996.
  21. 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.
  22. 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.
  23. Kailath and Olshevsky, ``Displacement Structure Approach to Polynomial Vandermonde and Related Matrices,'' Linear Algebra and Its Applications, 261 (1997), 49-90.
  24. Heinig, ``Matrices with higher-order displacement structure, " Linear Algebra and its Applications, 278, pp. 295-301, 1998.

III.
Reviews:

  1. Kailath, Vieira, & Morf, ``Inverses of Toeplitz operators, innovations, and orthogonal polynomials,'' SIAM Review, vol. 20, pp. 106-119, January 1978.
  2. 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.
  3. Kailath, ``Signal processing applications of some moment problems,'' in Moments in Mathematics, American Mathematical Society, Landau, editor, vol. 37, pp. 71-109, 1987.
  4. Kailath, ``Remarks on the origin of the displacement rank concept," J. Appl. Math. Computation, vol. 45, pp. 193-206, Sep. 1991.
  5. Kailath & Sayed, ``Displacement Structure: Theory and Applications,'' SIAM Review, vol. 37, no. 3, pp. 297-386, Sep. 1995.
  6. Olshevsky, ``Pivoting for structured matrices, with applications,'' www.cs.gsu.edu/ tex2html_wrap_inline138 matvro
  7. See also the papers in the previously mentioned review volume edited by Kailath and Sayed.

IV.
Some Applications:
  1. Rao & Kailath, ``Orthogonal digital filters for VLSI implementation,'' IEEE Transactions on Circuits and Systems, vol. 31, no. 11, pp. 933-945, Nov. 1984.
  2. Citron, Algorithms and Architectures for Error Correcting Codes, Ph.D. dissertation, Stanford University, 1986.
  3. Kailath, Bruckstein, and Morgan, `` Fast matrix factorization via discrete transmission lines," Linear Algebra and its Applications, vol. 75, pp. 1-25, Mar. 1968.
  4. Bruckstein & Kailath, ``An inverse scattering framework for several problems in signal processing,'' IEEE ASSP Magazine, pp. 6-20, Jan. 1987.
  5. Bruckstein & Kailath, ``Inverse scattering for discrete transmission-line models,'' SIAM Review, vol. 29, no. 3, pp. 359-389, Sep. 1987.
  6. Bruckstein, Citron, & Kailath, ``Inverse scattering and minimal partial realization,'' Int. J. Control, vol. 48, no. 4, pp. 1537-1550, 1988.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Gohberg and Olshevsky, ``Complexity of multiplication with vectors for structured matrices,'' Linear Algebra and Its Applications, 202 (1994), 163-192.
  12. 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.
  13. 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.
  14. Constantinescu, Sayed, & Kailath, ``Displacement structure and completion problems,'' SIAM J. Matrix Anal. Appl., vol. 16, no. 1, pp. 58-78, Jan. 1995.
  15. 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.
  16. Boros, Sayed, & Kailath, ``A recursive method for solving unconstrained tangential interpolation problems,'' IEEE Transactions on Automatic Control, vol. 44, pp. 454-470, Mar. 1999.
  17. Bini & Meini, ``Effective methods for solving banded Toeplitz systems,'' SIAM J. matrix Anal. Appl., vol. 20, no. 3, pp. 700-719, 1999.
  18. 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.
  19. 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.
  20. 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.
  21. Fasino, Isospectral flows on displacement structured matrix spaces, ----, 2000
  22. 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:
  1. 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.
  2. 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.
  3. 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.
  4. Chandrasekaran & Sayed, ``Stabilizing the generalized Schur algorithm,'' SIAM J. Matrix Analysis and Applications, vol. 17, no. 4, pp. 950-983, Oct. 1996.
  5. 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.
  6. Stewart & Van Dooren, ``Stability issues in the factorization of structured matrices,'' SIAM J. Matrix Anal. Appl., vol. 18, pp. 104-118, 1997.
  7. 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.
  8. Gohberg, Kailath, & Olshevsky, ``Fast Gaussian elimination with partial pivoting for matrices with displacement structure,'' Math. Comp., vol. 64, pp. 1557-1576, 1995.
  9. 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.
  10. Gohberg and Olshevsky, ``The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices,'' Journal of Complexity, 13(2) (1997), 208-234.
  11. 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:

  1. Heinig & Rost, Algebraic Methods for Toeplitz-like Matrices and Operators, Akademie-Verlag, Berlin and Birkhäuser, 1984.
  2. Bini & Pan, Matrix and Polynomial Computations, Vol. I: Fundamental Algorithms, Birkhauser, Boston, 1994; vol. II, 2001.
  3. Constantinescu, Schur Parameters, Factorization, and Dilation Problems, Birkhauser, Basel, 1996.
  4. Bini and Di Benedetto, Special Issues on Toeplitz Matrices: Structures, Algorithms and Applications, (Cortona Workshop, 1996), Calcolo, vol. 33.
  5. Dewirlde and Van Der Veen, Time-Varying Systems and Computations, Kluwer, 1998.
  6. Kailath & Sayed, editors, Fast Reliable Algorithms for Matrices with Structure, SIAM, PA, 1999.
  7. Bini, Tyrtyshnikov, & Yalamov, editors, Structured Matrices & Recent Developments in Theory and Computation, Nova Science, 2000.
  8. Olshevsky, editor, Structured Matrices in Operator Theory: Numerical Analysis, Control, Signal and Image Processing, Amer. Math. Soc., 2000.
Last modified 1/17/2013