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

On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

In this paper, we will compare the convergence properties of three basic reduction methods, by placing them in a general framework. It covers the reduction to tridiagonal, semiseparable and semiseparable plus diagonal form. These reductions are often used as the first step in the computation of the eigenvalues and/or eigenvectors of arbitrary matrices. In this way, the calculation of the eigenvalues using, for example, the QR-algorithm reduces in complexity. First we will investigate the convergence properties of these three reduction algorithms. It will be shown that for the partially reduced matrices at step k of any of these reduction algorithms, the lower right k ×  k (already reduced) sub-block will have the Lanczos–Ritz values, w.r.t. a certain starting vector. It will also be shown that the reductions to semiseparable and to semiseparable plus diagonal form have an extra convergence behavior a special type of subspace iteration is performed on the lower right k ×  k submatrix, which contains these Ritz-values. Secondly we look in more detail at the behavior of the involved subspace iteration. It will be shown that the reduction method can be interpreted as a nested type of multi-shift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms. Also a theoretical bound on the convergence rate is presented. Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it can become a powerful tool for certain applications.

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. Borges, C.F., Gragg, W.B.: Divide and conquer for generalized real symmetric definite tridiagonal eigenproblems. In: Proceedings of the Shanghai International Conference on Numerical Linear Algebra and Applications, pp. 70–76, Shanghai, October 1992

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

    Article  MATH  MathSciNet  Google Scholar 

  4. Cuppen J.J.M. (1981). A divide and conquer method for the symmetric tridiagonal eigenproblem. Numer. Math. 36, 177–195

    Article  MATH  MathSciNet  Google Scholar 

  5. Demmel, J.W.: Applied Numerical Linear Algebra. SIAM (1997)

  6. Eidelman Y., Gohberg I.C., Olshevsky V. (2005). The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order. Linear Algebr. Appl. 404, 305–324

    Article  MATH  MathSciNet  Google Scholar 

  7. Golub, G.H., Van Loan, C.F.: Matrix Computations. The Johns Hopkins University Press, 3rd edition (1996)

  8. Mastronardi, N., Schuermans, M., Van Barel, M., Van Huffel, S., Vandebril, R.: The Lanczos reduction to semiseparable matrices. In: Proceedings of the 17th IMACS World Congress on Scientific Computation, Applied Mathematics and Simulation, pp. 1–6, July 2005

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

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

    Article  MATH  MathSciNet  Google Scholar 

  11. Trefethen, L.N., Bau, D.: Numerical Linear Algebra. SIAM (1997)

  12. Van Barel M., Vandebril R., Mastronardi N. (2005). An orthogonal similarity reduction of a matrix into semiseparable form. SIAM J. Matrix Anal. Appl. 27(1):176–197

    Article  MATH  MathSciNet  Google Scholar 

  13. Van Camp, E.: Diagonal-plus-semiseparable matrices and their use in numerical linear algebra. Ph.D. thesis, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3001 Heverlee (Leuven), Belgium, May 2005

  14. Van Camp, E., Van Barel, M., Vandebril, R., Mastronardi, N.: An implicit QR-algorithm for symmetric diagonal-plus-semiseparable matrices. Technical Report TW419, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3000 Leuven (Heverlee), Belgium, March 2005

  15. Vandebril, R., Van Barel, M.: Necessary and sufficient conditions for orthogonal similarity transformations to obtain the Ritz values. Technical Report TW396, Katholieke Universiteit Leuven, Department Computerwetenschappen, Celestijnenlaan 200A, 3001 Heverlee (Leuven), Belgium, July 2004

  16. Vandebril, R., Van Barel, M., Mastronardi, N.: An implicit QR-algorithm for semiseparable matrices to compute the eigendecomposition of symmetric matrices. Technical Report TW367, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3000 Leuven (Heverlee), Belgium, August 2003

  17. Vandebril, R., Van Camp, E., Van Barel, M., Mastronardi, N.: Orthogonal similarity transformation of a symmetric matrix into a diagonal-plus-semiseparable one with free choice of the diagonal. Technical Report TW398, Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3000 Leuven (Heverlee), Belgium (2004)

  18. Vandebril R., Van Barel M., Mastronardi N. (2005). A note on the representation and definition of semiseparable matrices. Numer. Linear Algebr. Appl. 12(8):839–858

    Article  MathSciNet  Google Scholar 

  19. Vandebril R., Van Barel M., Mastronardi N. (2005). An implicit QR-algorithm for symmetric semiseparable matrices. Numer. Linear Algebr. Appl. 12(7):625–658

    Article  MathSciNet  Google Scholar 

  20. Watkins D.S. (1996). QR-like algorithms an overview of convergence theory and practice. Lect. Appl. Math. 32, 879–893

    MathSciNet  Google Scholar 

  21. Watkins D.S., Elsner L. (1991). Convergence of algorithms of decomposition type for the eigenvalue problem. Linear Algebr. Appl. 143, 19–47

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, K.U.Leuven, 3001, Leuven(Heverlee), Belgium

    Raf Vandebril, Ellen Van Camp & Marc Van Barel

  2. Istituto per le Applicazioni del Calcolo M. Picone, sez. Bari, 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.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vandebril, R., Camp, E.V., Van Barel, M. et al. On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form. Numer. Math. 104, 205–239 (2006). https://doi.org/10.1007/s00211-006-0017-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-006-0017-2

Keywords

Mathematics Subject Classification (1991)

Search

Navigation