Residual, restarting and Richardson iteration for the matrix exponential

Mikhail A. Bochev

    Research output: Book/ReportReportProfessional

    135 Downloads (Pure)

    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
    PublisherUniversity of Twente, Department of Applied Mathematics
    Number of pages20
    Publication statusPublished - 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

    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: University of Twente, Department of Applied Mathematics.
    Bochev, Mikhail A. / Residual, restarting and Richardson iteration for the matrix exponential. Enschede : University of Twente, Department of Applied Mathematics, 2010. 20 p. (Memorandum / Department of Applied Mathematics; 1928).
    @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",
    language = "Undefined",
    series = "Memorandum / Department of Applied Mathematics",
    publisher = "University of Twente, Department of Applied Mathematics",
    number = "1928",

    }

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

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

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

    Research output: Book/ReportReportProfessional

    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 - University of Twente, Department of Applied Mathematics

    CY - Enschede

    ER -

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