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(n 2 log n) arithmetic operations are shown.

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

BINI, DARIO ANDREA;MASSEI, STEFANO;ROBOL, LEONARDO
2017-01-01

Abstract

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(n 2 log n) arithmetic operations are shown.
2017
Bini, DARIO ANDREA; Massei, Stefano; Robol, Leonardo
File in questo prodotto:
File Dimensione Formato  
qcr-krylov-paper-laa.pdf

accesso aperto

Descrizione: Post-print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 510.67 kB
Formato Adobe PDF
510.67 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/825828
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact