Time-stepping and preserving orthonormality

D.J. Higham

Research output: Contribution to journalArticle

21 Citations (Scopus)

Abstract

Certain applications produce initial value ODEs whose solutions, regarded as time-dependent matrices, preserve orthonormality. Such systems arise in the computation of Lyapunov exponents and the construction of smooth singular value decompositions of parametrized matrices. For some special problem classes, there exist time-stepping methods that automatically inherit the orthonormality preservation. However, a more widely applicable approach is to apply a standard integrator and regularly replace the approximate solution by an orthonormal matrix. Typically, the approximate solution is replaced by the factor Q from its QR decomposition (computed, for example, by the modified Gram-Schmidt method). However, the optimal replacement-the one that is closest in the Frobenius norm-is given by the orthonormal polar factor. Quadratically convergent iteration schemes can be used to compute this factor. In particular, there is a matrix multiplication based iteration that is ideally suited to modern computer architectures. Hence, we argue that perturbing towards the orthonormal polar factor is an attractive choice, and ne consider performing a fixed number of iterations. Using the optimality property we show that the perturbations improve the departure from orthonormality without significantly degrading the finite-time global error bound fur the ODE solution. Our analysis allows for adaptive time-stepping, where a local error control process is driven by a user-supplied tolerance. Finally, using a recent result of Sun, we show how the global error bound tarries through to the case where the orthonormal QR factor is used instead of the orthonormal polar factor.
Original languageEnglish
Pages (from-to)24-36
Number of pages12
JournalBIT Numerical Mathematics
Volume37
Issue number1
Publication statusPublished - Mar 1997

Fingerprint

Time Stepping
Orthonormal
Global Error Bound
Computer architecture
Approximate Solution
Singular value decomposition
Orthonormal matrix
Sun
Iteration
QR Decomposition
Frobenius norm
Computer Architecture
Iteration Scheme
Matrix multiplication
Error Control
Lyapunov Exponent
Preservation
Replacement
Tolerance
Optimality

Keywords

  • error control
  • variable time-step
  • Lyapunov exponents
  • global error
  • polar decomposition
  • nearest orthonormal matrix
  • computer science
  • mathematics

Cite this

Higham, D.J. / Time-stepping and preserving orthonormality. In: BIT Numerical Mathematics. 1997 ; Vol. 37, No. 1. pp. 24-36.
@article{3744564ddfd740328b6e7ded02447202,
title = "Time-stepping and preserving orthonormality",
abstract = "Certain applications produce initial value ODEs whose solutions, regarded as time-dependent matrices, preserve orthonormality. Such systems arise in the computation of Lyapunov exponents and the construction of smooth singular value decompositions of parametrized matrices. For some special problem classes, there exist time-stepping methods that automatically inherit the orthonormality preservation. However, a more widely applicable approach is to apply a standard integrator and regularly replace the approximate solution by an orthonormal matrix. Typically, the approximate solution is replaced by the factor Q from its QR decomposition (computed, for example, by the modified Gram-Schmidt method). However, the optimal replacement-the one that is closest in the Frobenius norm-is given by the orthonormal polar factor. Quadratically convergent iteration schemes can be used to compute this factor. In particular, there is a matrix multiplication based iteration that is ideally suited to modern computer architectures. Hence, we argue that perturbing towards the orthonormal polar factor is an attractive choice, and ne consider performing a fixed number of iterations. Using the optimality property we show that the perturbations improve the departure from orthonormality without significantly degrading the finite-time global error bound fur the ODE solution. Our analysis allows for adaptive time-stepping, where a local error control process is driven by a user-supplied tolerance. Finally, using a recent result of Sun, we show how the global error bound tarries through to the case where the orthonormal QR factor is used instead of the orthonormal polar factor.",
keywords = "error control, variable time-step, Lyapunov exponents, global error, polar decomposition, nearest orthonormal matrix, computer science, mathematics",
author = "D.J. Higham",
year = "1997",
month = "3",
language = "English",
volume = "37",
pages = "24--36",
journal = "BIT Numerical Mathematics",
issn = "0006-3835",
number = "1",

}

Higham, DJ 1997, 'Time-stepping and preserving orthonormality', BIT Numerical Mathematics, vol. 37, no. 1, pp. 24-36.

Time-stepping and preserving orthonormality. / Higham, D.J.

In: BIT Numerical Mathematics, Vol. 37, No. 1, 03.1997, p. 24-36.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Time-stepping and preserving orthonormality

AU - Higham, D.J.

PY - 1997/3

Y1 - 1997/3

N2 - Certain applications produce initial value ODEs whose solutions, regarded as time-dependent matrices, preserve orthonormality. Such systems arise in the computation of Lyapunov exponents and the construction of smooth singular value decompositions of parametrized matrices. For some special problem classes, there exist time-stepping methods that automatically inherit the orthonormality preservation. However, a more widely applicable approach is to apply a standard integrator and regularly replace the approximate solution by an orthonormal matrix. Typically, the approximate solution is replaced by the factor Q from its QR decomposition (computed, for example, by the modified Gram-Schmidt method). However, the optimal replacement-the one that is closest in the Frobenius norm-is given by the orthonormal polar factor. Quadratically convergent iteration schemes can be used to compute this factor. In particular, there is a matrix multiplication based iteration that is ideally suited to modern computer architectures. Hence, we argue that perturbing towards the orthonormal polar factor is an attractive choice, and ne consider performing a fixed number of iterations. Using the optimality property we show that the perturbations improve the departure from orthonormality without significantly degrading the finite-time global error bound fur the ODE solution. Our analysis allows for adaptive time-stepping, where a local error control process is driven by a user-supplied tolerance. Finally, using a recent result of Sun, we show how the global error bound tarries through to the case where the orthonormal QR factor is used instead of the orthonormal polar factor.

AB - Certain applications produce initial value ODEs whose solutions, regarded as time-dependent matrices, preserve orthonormality. Such systems arise in the computation of Lyapunov exponents and the construction of smooth singular value decompositions of parametrized matrices. For some special problem classes, there exist time-stepping methods that automatically inherit the orthonormality preservation. However, a more widely applicable approach is to apply a standard integrator and regularly replace the approximate solution by an orthonormal matrix. Typically, the approximate solution is replaced by the factor Q from its QR decomposition (computed, for example, by the modified Gram-Schmidt method). However, the optimal replacement-the one that is closest in the Frobenius norm-is given by the orthonormal polar factor. Quadratically convergent iteration schemes can be used to compute this factor. In particular, there is a matrix multiplication based iteration that is ideally suited to modern computer architectures. Hence, we argue that perturbing towards the orthonormal polar factor is an attractive choice, and ne consider performing a fixed number of iterations. Using the optimality property we show that the perturbations improve the departure from orthonormality without significantly degrading the finite-time global error bound fur the ODE solution. Our analysis allows for adaptive time-stepping, where a local error control process is driven by a user-supplied tolerance. Finally, using a recent result of Sun, we show how the global error bound tarries through to the case where the orthonormal QR factor is used instead of the orthonormal polar factor.

KW - error control

KW - variable time-step

KW - Lyapunov exponents

KW - global error

KW - polar decomposition

KW - nearest orthonormal matrix

KW - computer science

KW - mathematics

UR - http://www.springerlink.com/openurl.asp?genre=issue&eissn=1572-9125&volume=37&issue=1

UR - http://www.csc.kth.se/BIT/

M3 - Article

VL - 37

SP - 24

EP - 36

JO - BIT Numerical Mathematics

JF - BIT Numerical Mathematics

SN - 0006-3835

IS - 1

ER -