On the decay of the off-diagonal singular values in cyclic reduction

Dario A. Bini, Stefano Massei, Leonardo Robol

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)


It was recently observed in [10] that the singular values of the off-diagonal blocks of the matrix sequences generated by the Cyclic Reduction algorithm decay exponentially. This property was used to solve, with a higher efficiency, certain quadratic matrix equations encountered in the analysis of queuing models. In this paper, we provide a theoretical bound to the basis of this exponential decay together with a tool for its estimation based on a rational interpolation problem. Numerical experiments show that the bound is often accurate in practice. Applications to solving n×n block tridiagonal block Toeplitz systems with n×n quasiseparable blocks and certain generalized Sylvester equations in O(n2log⁡n) arithmetic operations are shown.

Original languageEnglish
Pages (from-to)27-53
Number of pages27
JournalLinear Algebra and Its Applications
Publication statusPublished - 15 Apr 2017
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2016 Elsevier Inc.

Copyright 2017 Elsevier B.V., All rights reserved.


  • Block tridiagonal systems
  • Cyclic reduction
  • Exponential decay
  • Quasiseparable matrices
  • Rational interpolation
  • Sylvester equations


Dive into the research topics of 'On the decay of the off-diagonal singular values in cyclic reduction'. Together they form a unique fingerprint.

Cite this