We provide effective algorithms for solving block tridiagonal block Toeplitz systems with . m×m quasiseparable blocks, as well as quadratic matrix equations with . m×m quasiseparable coefficients, based on cyclic reduction and on the technology of rank-structured matrices. The algorithms rely on the exponential decay of the singular values of the off-diagonal submatrices generated by cyclic reduction. We provide a formal proof of this decay in the Markovian framework. The results of the numerical experiments that we report confirm a significant speed up over the general algorithms, already starting with the moderately small size . m≈102.

Efficient cyclic reduction for Quasi-Birth-Death problems with rank structured blocks

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

Abstract

We provide effective algorithms for solving block tridiagonal block Toeplitz systems with . m×m quasiseparable blocks, as well as quadratic matrix equations with . m×m quasiseparable coefficients, based on cyclic reduction and on the technology of rank-structured matrices. The algorithms rely on the exponential decay of the singular values of the off-diagonal submatrices generated by cyclic reduction. We provide a formal proof of this decay in the Markovian framework. The results of the numerical experiments that we report confirm a significant speed up over the general algorithms, already starting with the moderately small size . m≈102.
2017
Bini, DARIO ANDREA; Massei, Stefano; Robol, Leonardo
File in questo prodotto:
File Dimensione Formato  
bini-massei-robol-revised.pdf

accesso aperto

Descrizione: Post-print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 445.88 kB
Formato Adobe PDF
445.88 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/827321
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact