Residual, restarting and Richardson iteration for the matrix exponential

Mikhail A. Bochev

Abstract

A well-known problem in computing some matrix functions iteratively is a lack of a clear, commonly accepted residual notion. An important matrix function for which this is the case is the matrix exponential. Assume, the matrix exponential of a given matrix times a given vector has to be computed. We interpret the sought after vector as a value of a vector function satisfying the linear system of ordinary differential equations (ODE), whose coefficients form the given matrix. The residual is then defined with respect to the initial-value problem for this ODE system. The residual introduced in this way can be seen as a backward error. We show how the residual can efficiently be computed within several iterative methods for the matrix exponential. This completely resolves the question of reliable stopping criteria for these methods. Furthermore, we show that the residual concept can be used to construct new residual-based iterative methods. In particular, a variant of the Richardson method for the new residual appears to provide an efficient way to restart Krylov subspace methods for evaluating the matrix exponential.
Original languageUndefined
Place of PublicationEnschede
PublisherDepartment of Applied Mathematics, University of Twente
Number of pages20
StatePublished - Nov 2010

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherDepartment of Applied Mathematics, University of Twente
No.1928
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Fingerprint

Matrix exponential
Matrix function
Iteration
Backward error
Krylov subspace methods
Stopping criterion
Restart
System of ordinary differential equations
Initial value problem
Resolve
Ordinary differential equation
Linear systems
Computing
Coefficient

Keywords

  • MSC-65F30
  • MSC-65F60
  • MSC-65N22
  • MSC-65F10
  • EWI-18832
  • Stopping criterion
  • Residual
  • MSC-65L05
  • Restarting
  • Richardson iteration
  • Matrix exponential
  • Matrix cosine
  • Backward stability
  • Chebyshev polynomials
  • IR-74752
  • METIS-271140
  • Krylov subspace methods

Cite this

Bochev, M. A. (2010). Residual, restarting and Richardson iteration for the matrix exponential. (Memorandum / Department of Applied Mathematics; No. 1928). Enschede: Department of Applied Mathematics, University of Twente.

Bochev, Mikhail A. / Residual, restarting and Richardson iteration for the matrix exponential.

Enschede : Department of Applied Mathematics, University of Twente, 2010. 20 p. (Memorandum / Department of Applied Mathematics; No. 1928).

Research output: ProfessionalReport

@book{d93ac2ee18644046aee40b88261c07e9,
title = "Residual, restarting and Richardson iteration for the matrix exponential",
abstract = "A well-known problem in computing some matrix functions iteratively is a lack of a clear, commonly accepted residual notion. An important matrix function for which this is the case is the matrix exponential. Assume, the matrix exponential of a given matrix times a given vector has to be computed. We interpret the sought after vector as a value of a vector function satisfying the linear system of ordinary differential equations (ODE), whose coefficients form the given matrix. The residual is then defined with respect to the initial-value problem for this ODE system. The residual introduced in this way can be seen as a backward error. We show how the residual can efficiently be computed within several iterative methods for the matrix exponential. This completely resolves the question of reliable stopping criteria for these methods. Furthermore, we show that the residual concept can be used to construct new residual-based iterative methods. In particular, a variant of the Richardson method for the new residual appears to provide an efficient way to restart Krylov subspace methods for evaluating the matrix exponential.",
keywords = "MSC-65F30, MSC-65F60, MSC-65N22, MSC-65F10, EWI-18832, Stopping criterion, Residual, MSC-65L05, Restarting, Richardson iteration, Matrix exponential, Matrix cosine, Backward stability, Chebyshev polynomials, IR-74752, METIS-271140, Krylov subspace methods",
author = "Bochev, {Mikhail A.}",
note = "Author's family name can also be spelled as {"}Bochev{"}",
year = "2010",
month = "11",
series = "Memorandum / Department of Applied Mathematics",
publisher = "Department of Applied Mathematics, University of Twente",
number = "1928",

}

Bochev, MA 2010, Residual, restarting and Richardson iteration for the matrix exponential. Memorandum / Department of Applied Mathematics, no. 1928, Department of Applied Mathematics, University of Twente, Enschede.

Residual, restarting and Richardson iteration for the matrix exponential. / Bochev, Mikhail A.

Enschede : Department of Applied Mathematics, University of Twente, 2010. 20 p. (Memorandum / Department of Applied Mathematics; No. 1928).

Research output: ProfessionalReport

TY - BOOK

T1 - Residual, restarting and Richardson iteration for the matrix exponential

AU - Bochev,Mikhail A.

N1 - Author's family name can also be spelled as "Bochev"

PY - 2010/11

Y1 - 2010/11

N2 - A well-known problem in computing some matrix functions iteratively is a lack of a clear, commonly accepted residual notion. An important matrix function for which this is the case is the matrix exponential. Assume, the matrix exponential of a given matrix times a given vector has to be computed. We interpret the sought after vector as a value of a vector function satisfying the linear system of ordinary differential equations (ODE), whose coefficients form the given matrix. The residual is then defined with respect to the initial-value problem for this ODE system. The residual introduced in this way can be seen as a backward error. We show how the residual can efficiently be computed within several iterative methods for the matrix exponential. This completely resolves the question of reliable stopping criteria for these methods. Furthermore, we show that the residual concept can be used to construct new residual-based iterative methods. In particular, a variant of the Richardson method for the new residual appears to provide an efficient way to restart Krylov subspace methods for evaluating the matrix exponential.

AB - A well-known problem in computing some matrix functions iteratively is a lack of a clear, commonly accepted residual notion. An important matrix function for which this is the case is the matrix exponential. Assume, the matrix exponential of a given matrix times a given vector has to be computed. We interpret the sought after vector as a value of a vector function satisfying the linear system of ordinary differential equations (ODE), whose coefficients form the given matrix. The residual is then defined with respect to the initial-value problem for this ODE system. The residual introduced in this way can be seen as a backward error. We show how the residual can efficiently be computed within several iterative methods for the matrix exponential. This completely resolves the question of reliable stopping criteria for these methods. Furthermore, we show that the residual concept can be used to construct new residual-based iterative methods. In particular, a variant of the Richardson method for the new residual appears to provide an efficient way to restart Krylov subspace methods for evaluating the matrix exponential.

KW - MSC-65F30

KW - MSC-65F60

KW - MSC-65N22

KW - MSC-65F10

KW - EWI-18832

KW - Stopping criterion

KW - Residual

KW - MSC-65L05

KW - Restarting

KW - Richardson iteration

KW - Matrix exponential

KW - Matrix cosine

KW - Backward stability

KW - Chebyshev polynomials

KW - IR-74752

KW - METIS-271140

KW - Krylov subspace methods

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

BT - Residual, restarting and Richardson iteration for the matrix exponential

PB - Department of Applied Mathematics, University of Twente

ER -

Bochev MA. Residual, restarting and Richardson iteration for the matrix exponential. Enschede: Department of Applied Mathematics, University of Twente, 2010. 20 p. (Memorandum / Department of Applied Mathematics; 1928).