[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Orthogonal similarity transformation of a symmetric matrix into a diagonal-plus-semiseparable one with free choice of the diagonal

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

In this paper we describe an orthogonal similarity transformation for transforming arbitrary symmetric matrices into a diagonal-plus-semiseparable matrix, where we can freely choose the diagonal. Very recently an algorithm was proposed for transforming arbitrary symmetric matrices into similar semiseparable ones. This reduction is strongly connected to the reduction to tridiagonal form. The class of semiseparable matrices can be considered as a subclass of the diagonalplus- semiseparable matrices. Therefore we can interpret the proposed algorithm here as an extension of the reduction to semiseparable form.

A numerical experiment is performed comparing thereby the accuracy of this reduction algorithm with respect to the accuracy of the traditional reduction to tridiagonal form, and the reduction to semiseparable form. The experiment indicates that all three reduction algorithms are equally accurate. Moreover it is shown in the experiments that asymptotically all the three approaches have the same complexity, i.e. that they have the same factor preceding the n 3 term in the computational complexity. Finally we illustrate that special choices of the diagonal create a specific convergence behavior.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bini, D.A., Gemignani, L., Pan, V.Y.: QR-like algorithms for generalized semiseparable matrices. Technical Report 1470, Department of Mathematics, University of Pisa, 2004

  2. Chandrasekaran, S., Gu, M.: A divide and conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semi-separable matrices. Numerische Mathematik 96(4), 723–731 (2004)

    Article  MathSciNet  Google Scholar 

  3. Cuppen, J.J.M.: A divide and conquer method for the symmetric tridiagonal eigenproblem. Numerische Mathematik 36, 177–195 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  4. Dewilde, P., van der Veen, A.-J.: Time-varying systems and computations. Kluwer academic publishers, Boston, June 1998

  5. Eidelman, Y., Gohberg, I.C.: Inversion formulas and linear complexity algorithm for diagonal plus semiseparable matrices. Comput. Math. Appl. 33(4), 69–79 (1996)

    Article  MathSciNet  Google Scholar 

  6. Fasino, D.: Rational Krylov matrices and QR-steps on Hermitian diagonal-plus- semiseparable matrices. To appear in Numerical Linear Algebra with Applications 12(8), 743–754 (2005)

    Article  MathSciNet  Google Scholar 

  7. Fasino, D., Gemignani, L.: Direct and inverse eigenvalue problems, for diagonal-plus- semiseparable matrices. Numer. Algorithms 34, 313–324 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. Fasino, D., Mastronardi, N., Van Barel, M.: Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form. Contemporary Math. 323, 105–118 (2003)

    MATH  MathSciNet  Google Scholar 

  9. Gantmacher, F.R., Krein, M.G.: Oscillation matrices and kernels and small vibrations of mechanical systems. AMS Chelsea Publishing, Providence, Rhode Island, revised edition, 2002

  10. Golub, G.H., Van Loan, C.F.: Matrix Computations. The Johns Hopkins University Press, third edition, 1996

  11. Graybill, F.A.: Matrices with applications in statistics. Wadsworth international group, Belmont, California, 1983

  12. Mastronardi, N., Chandrasekaran, S., Van Huffel, S.: Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form. BIT 41(1), 149–157 2003

    Article  MathSciNet  Google Scholar 

  13. Mastronardi, N., Van Barel, M., Van Camp, E.: Divide and conquer algorithms for computing the eigendecomposition of symmetric diagonal-plus-semiseparable matrices. Numer. Algorithms 39(4), 379–398 (2005)

    Article  MathSciNet  Google Scholar 

  14. Mastronardi, N., Van Barel, M., Vandebril, R.: Computing the rank revealing factorization by the semiseparable reduction. Technical Report TW418, Katholieke Universiteit Leuven, Dept. Computer Science, Celestijnenlaan 200A, 3001 Heverlee (Leuven), Belgium, May 2005

  15. Meurant, G.: A review of the inverse of symmetric tridiagonal and block tridiagonal matrices. SIAM J. Matrix Anal. Appl. 13, 707–728 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  16. Parlett, B.N.: The symmetric eigenvalue problem, volume 20 of Classics in Applied Mathematics. SIAM, Philadelphia, 1998

  17. Roy, S.N., Greenberg, B.G., Sarhan, A.E.: Evaluation of determinants, characteristic equations and their roots for a class of patterned matrices. J. Royal Stat. Soc. Series B. Methodological 22, 348–359 (1960)

    MATH  Google Scholar 

  18. Van Barel, M., Fasino, D., Gemignani, L., Mastronardi, N.: Orthogonal rational functions and diagonal plus semiseparable matrices. In: Advanced Signal Processing Algorithms, Architectures, and Implementations XII, F. T. Luk, (ed.), volume 4791 of Proceedings of SPIE, 2002 pp 167–170

  19. Van Barel, M., Vandebril, R., Mastronardi, N.: An orthogonal similarity reduction of a matrix into semiseparable form. SIAM Journal on Matrix Analysis and its Applications, 27(1), 176–197 (2005)

    Article  Google Scholar 

  20. Van Camp, E., Mastronardi, N., Van Barel, M.: Two fast algorithms for solving diagonal-plus-semiseparable linear systems. J. Comput. Appl. Math. 164–165, 731–747 (2004)

    Google Scholar 

  21. Vandebril, R., Van Barel, M., Mastronardi, N.: An implicit QR-algorithm for symmetric semiseparable matrices. Numerical Linear Algebra with Applications 12(7), 625–658 (2005)

    Article  MathSciNet  Google Scholar 

  22. Vandebril, R., Van Barel, M., Mastronardi, N.: A note on the representation and definition of semiseparable matrices. Numerical Linear Algebra with Applications 12(8), 839–858 (2005)

    Article  MathSciNet  Google Scholar 

  23. Vandebril, R., Van Camp, E., Van Barel, M., Mastronardi, N.: On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form. Report TW436, Katholieke Universiteit Leuven, Department of Computer Science, Celestijnenlaan 200A, B-3001 Leuven (Heverlee), Belgium, Aug 2005.

  24. Watkins, D.S.: On QR algorithms for the eigenvalue problem. Nato adv. sci. inst. ser. f comput systems sci. 70, 687–693 (1991)

    MATH  MathSciNet  Google Scholar 

  25. Wilkinson, J.H.: The algebraic eigenvalue problem. Numerical mathematics and scientific computation. Oxford University Press, Great Claredon Street, Oxford OX2 6DP, 1999

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, B-3001, Leuven, Belgium

    Raf Vandebril, Ellen Van Camp & Marc Van Barel

  2. Istituto per le Applicazioni del Calcolo, CNR, via Amendola 122/D, 70126, Bari, Italy

    Nicola Mastronardi

Authors
  1. Raf Vandebril
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ellen Van Camp
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marc Van Barel
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nicola Mastronardi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marc Van Barel.

Additional information

The research was partially supported by the Research Council K.U.Leuven, project OT/05/40 (Large rank structured matrix computations), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vandebril, R., Camp, E., Barel, M. et al. Orthogonal similarity transformation of a symmetric matrix into a diagonal-plus-semiseparable one with free choice of the diagonal. Numer. Math. 102, 709–726 (2006). https://doi.org/10.1007/s00211-005-0665-7

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-005-0665-7

Keywords

Mathematics Subject Classification (2000)

Search

Navigation