Subspace acceleration for the crawford number and related eigenvalue optimization problems

Daniel Kressner; Ding Lu; Bart Vandereycken

doi:10.1137/17M1127545

Subspace acceleration for the crawford number and related eigenvalue optimization problems

Daniel Kressner, Ding Lu, Bart Vandereycken

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

This paper is concerned with subspace acceleration techniques for computing the Crawford number, that is, the distance between zero and the numerical range of a matrix A. Our approach is based on an eigenvalue optimization characterization of the Crawford number. We establish local convergence of order 1 + 2 ˜ 2.4 for an existing subspace method applied to such and other eigenvalue optimization problems involving a Hermitian matrix that depends analytically on one parameter. For the particular case of the Crawford number, we show that the relevant part of the objective function is strongly concave. In turn, this enables us to develop a subspace method that only uses three-dimensional subspaces but still achieves global convergence and a local convergence that is at least quadratic. A number of numerical experiments confirm our theoretical results and reveal that the established convergence orders appear to be tight.

Original language	English
Pages (from-to)	961-982
Number of pages	22
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	39
Issue number	2
DOIs	https://doi.org/10.1137/17M1127545
State	Published - 2018

Bibliographical note

Funding Information:
∗Received by the editors April 26, 2017; accepted for publication (in revised form) November 28, 2017; published electronically May 24, 2018. http://www.siam.org/journals/simax/39-2/M112754.html Funding: The work of the second author was supported by the SNSF research project Robust and Fast Solvers for Computing Extremal Quantities of Structured Pseudospectra. †Institute of Mathematics, EPFL, Lausanne CH-1015, Switzerland (daniel.kressner@epfl.ch). ‡Department of Mathematics, University of Geneva, Geneva 1211, Switzerland (Ding.Lu@unige. ch, Bart.Vandereycken@unige.ch).

Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.

Keywords

Coercivity constant
Complex approximation
Convergence analysis
Crawford number
Eigenvalue optimization
Subspace acceleration

ASJC Scopus subject areas

Analysis

Access to Document

10.1137/17M1127545

Cite this

@article{ec723a37cf1e42dc952e5ba3de9f0bd4,

title = "Subspace acceleration for the crawford number and related eigenvalue optimization problems",

abstract = "This paper is concerned with subspace acceleration techniques for computing the Crawford number, that is, the distance between zero and the numerical range of a matrix A. Our approach is based on an eigenvalue optimization characterization of the Crawford number. We establish local convergence of order 1 + 2 ˜ 2.4 for an existing subspace method applied to such and other eigenvalue optimization problems involving a Hermitian matrix that depends analytically on one parameter. For the particular case of the Crawford number, we show that the relevant part of the objective function is strongly concave. In turn, this enables us to develop a subspace method that only uses three-dimensional subspaces but still achieves global convergence and a local convergence that is at least quadratic. A number of numerical experiments confirm our theoretical results and reveal that the established convergence orders appear to be tight.",

keywords = "Coercivity constant, Complex approximation, Convergence analysis, Crawford number, Eigenvalue optimization, Subspace acceleration",

author = "Daniel Kressner and Ding Lu and Bart Vandereycken",

note = "Funding Information: ∗Received by the editors April 26, 2017; accepted for publication (in revised form) November 28, 2017; published electronically May 24, 2018. http://www.siam.org/journals/simax/39-2/M112754.html Funding: The work of the second author was supported by the SNSF research project Robust and Fast Solvers for Computing Extremal Quantities of Structured Pseudospectra. †Institute of Mathematics, EPFL, Lausanne CH-1015, Switzerland (daniel.kressner@epfl.ch). ‡Department of Mathematics, University of Geneva, Geneva 1211, Switzerland (Ding.Lu@unige. ch, Bart.Vandereycken@unige.ch). Publisher Copyright: {\textcopyright} 2018 Society for Industrial and Applied Mathematics.",

year = "2018",

doi = "10.1137/17M1127545",

language = "English",

volume = "39",

pages = "961--982",

number = "2",

}

TY - JOUR

T1 - Subspace acceleration for the crawford number and related eigenvalue optimization problems

AU - Kressner, Daniel

AU - Lu, Ding

AU - Vandereycken, Bart

N1 - Funding Information: ∗Received by the editors April 26, 2017; accepted for publication (in revised form) November 28, 2017; published electronically May 24, 2018. http://www.siam.org/journals/simax/39-2/M112754.html Funding: The work of the second author was supported by the SNSF research project Robust and Fast Solvers for Computing Extremal Quantities of Structured Pseudospectra. †Institute of Mathematics, EPFL, Lausanne CH-1015, Switzerland (daniel.kressner@epfl.ch). ‡Department of Mathematics, University of Geneva, Geneva 1211, Switzerland (Ding.Lu@unige. ch, Bart.Vandereycken@unige.ch). Publisher Copyright: © 2018 Society for Industrial and Applied Mathematics.

PY - 2018

Y1 - 2018

N2 - This paper is concerned with subspace acceleration techniques for computing the Crawford number, that is, the distance between zero and the numerical range of a matrix A. Our approach is based on an eigenvalue optimization characterization of the Crawford number. We establish local convergence of order 1 + 2 ˜ 2.4 for an existing subspace method applied to such and other eigenvalue optimization problems involving a Hermitian matrix that depends analytically on one parameter. For the particular case of the Crawford number, we show that the relevant part of the objective function is strongly concave. In turn, this enables us to develop a subspace method that only uses three-dimensional subspaces but still achieves global convergence and a local convergence that is at least quadratic. A number of numerical experiments confirm our theoretical results and reveal that the established convergence orders appear to be tight.

AB - This paper is concerned with subspace acceleration techniques for computing the Crawford number, that is, the distance between zero and the numerical range of a matrix A. Our approach is based on an eigenvalue optimization characterization of the Crawford number. We establish local convergence of order 1 + 2 ˜ 2.4 for an existing subspace method applied to such and other eigenvalue optimization problems involving a Hermitian matrix that depends analytically on one parameter. For the particular case of the Crawford number, we show that the relevant part of the objective function is strongly concave. In turn, this enables us to develop a subspace method that only uses three-dimensional subspaces but still achieves global convergence and a local convergence that is at least quadratic. A number of numerical experiments confirm our theoretical results and reveal that the established convergence orders appear to be tight.

KW - Coercivity constant

KW - Complex approximation

KW - Convergence analysis

KW - Crawford number

KW - Eigenvalue optimization

KW - Subspace acceleration

UR - http://www.scopus.com/inward/record.url?scp=85049741371&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049741371&partnerID=8YFLogxK

U2 - 10.1137/17M1127545

DO - 10.1137/17M1127545

M3 - Article

AN - SCOPUS:85049741371

SN - 0895-4798

VL - 39

SP - 961

EP - 982

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 2

ER -

Subspace acceleration for the crawford number and related eigenvalue optimization problems

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this