Skip to main content
SpringerLink
Log in

Linear complexity algorithms for semiseparable matrices

  • Published:
Integral Equations and Operator Theory Aims and scope Submit manuscript

Abstract

Linear complexity algorithms are derived for the solution of a linear system of equations with the coefficient matrix represented as a sum of diagonal and semiseparable matrices. LDU-factorization algorithms for such matrices and their inverses are also given. The case in which the solution can be efficiently update is treated separately.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anderson, B.D. and Moore, J.B., “Optimal Filtering”, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1979.

    Google Scholar 

  2. Carayanis, G., Kalouptsidis, N. and Manolakis, D., “Fast Recursive Algorithms for a Class of Linear Equations”, IEEE Trans. ASSP, Vol. ASSP-30, no. 2, pp. 227–239, 1982.

    Google Scholar 

  3. Gevers, M. and Kailath, T., “An Innovations Approach to Least-Squares Estimation, Part VI: Discrete-Time Innovations Representations and Recursive Estimation”, IEEE Trans. on Autom. Contr., Vol. AC-18, 6, pp. 588–600, Dec. 1973.

    Google Scholar 

  4. Gohberg, I. and Kaashoek, M., “Time Varying Linear Systems with Boundary Conditions and Integral Operators, I: The Transfer Operator and its Properties, Int. E. Op. Theory, Vol. 7, no. 3, pp. 325–391, 1984.

    Google Scholar 

  5. Gohberg, I., Kailath, T., and Koltracht, I., “Linear Systems of Equations with Recursive Structure”, Lin. Alg. and Appl. 1985, (to appear).

  6. Gohberg, I., Kailath, T. and Koltracht, I., “Fast Matrix Factorization”, preliminary report, 1984.

  7. Gohberg, I. and Koltracht, I., “Numerical Solutions of Integral Equations, Fast Algorithms and Krein-Sobolev Equations”, Numerische Mathematik, 1985 (to appear).

  8. Kailath, T., “Fredholm Resolvents, Wiener-Hopf Equations, and Riccati Differential Equations”, IEEE Trans. on Inform. Theory, IT-15, no. 6, pp. 665–672, November 1969.

    Google Scholar 

  9. Kailath, T., “Some New Algorithms for Recursive Estimation in Constant Linear Systems”, IEEE Trans. on Inform. Theory, Vol. 19, no. 6, pp. 750–760, 1973.

    Google Scholar 

  10. Kailath, T., “Linear Systems”, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980.

    Google Scholar 

  11. Kailath, T., Morf, M. and Sidhu, G.S., “Some New Algorithms for Recursive Estimation in Constant Linear Discrete-Time Systems”, Proc. Seventh Princeton Conf. on Inform. Sci. & Systs., Princeton, N.J., pp. 344–352, March 1973.

  12. Krishna, H. and Morgera, S., “Linear Complexity Fast Algorithms for a Class of Linear Equations”, ICASSP, San Diego, CA, 1984.

    Google Scholar 

  13. Picinbono, B., “Fast Algorithms for Brownian Matrices”, IEEE Trans. ASSP, Vol. ASSP-31, pp. 512–514, April 1983.

    Google Scholar 

Download references

Author information

Author notes

  1. I. Koltracht

    Present address: Dept. of Math. and Stat., University of Calgary, T2N 1N4, Calgary, AB, Canada

Authors and Affiliations

  1. Dept. of Math. Sci., Tel-Aviv University, Tel-Aviv, Israel

    I. Gohberg

  2. Department of Electrical Engineering, Stanford University, 94305, Stanford, CA, USA

    T. Kailath

Authors
  1. I. Gohberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. Kailath
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. I. Koltracht
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported in part by the U.S. Army Research Office, under Contract DAAG29-83-K-0028, and the Air Force Office of Scientific Research, Air Force Systems Command under Contract AF83-0228.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gohberg, I., Kailath, T. & Koltracht, I. Linear complexity algorithms for semiseparable matrices. Integr equ oper theory 8, 780–804 (1985). https://doi.org/10.1007/BF01213791

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01213791

Keywords

Search

Navigation